Opened 4 years ago

Last modified 3 months ago

#3919 new feature request

Or-patterns as GHC extension

Reported by: BjornEdstrom Owned by:
Priority: normal Milestone:
Component: Compiler Version:
Keywords: Cc: vogt.adam@…, leon.p.smith@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets:

Description

Or-patterns is a way of grouping together patterns that match to the same value. A construct like

 fun 0 _ = E
 fun _ 0 = E

Could more concisely be written as, for example

 fun 0 _
  || _ 0 = E

As a concrete example why this is beautiful and how it could look, see Red-black trees in a functional setting, C. Okasaki [1].

I don't know enough about GHC internals to know the obvious way to implement this, but I would gladly give it a try given pointers in the right direction.

[1] http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps

Attachments (1)

QQ.hs (1.6 KB) - added by aavogt 4 years ago.
quasiquoter or patterns, when the TH AST can represent -XViewPatterns

Download all attachments as: .zip

Change History (5)

comment:1 Changed 4 years ago by simonpj

I think this would be a worthwhile thing to do. Or patterns are well studied in the ML community -- many papers on pattern-match compilation deal with them.

Whether we agreed to incorporate such a change into the HEAD of GHC would depend on

  • whether the implementation is modular (ie not complicating everything else) and
  • whether the syntax works smoothly with the rest of the language.
  • whether a consensus emerged that the extra complexity cost was paid for by the benefit.

I don't have time to say much more now, but here are some thoughts and pointers

  • Syntax is always surprisingly tricky, because Haskell's syntactic space is very crowded. Remember, for example that (||) is an existing operator symbol; are you going to steal it?
  • Your example gives an 'or' between two whole equations. You might also want to have an 'or' in a nested way, thus:
         f [ (Left x, True) || (Right y, False) ] = ...
    
    Here the or-pattern is embedded compositionaly inside a larger pattern.
  • You need to check that the two disjuncts bind the same variables.

Places you'd need to change in the compiler

  • Data type for patterns: HsPat
  • Parser: parser.y.pp
  • Renamer: RnPat
  • Typecheck: TcPat
  • Desugarer: Match

and probably some more besides.

Changed 4 years ago by aavogt

quasiquoter or patterns, when the TH AST can represent -XViewPatterns

comment:2 Changed 4 years ago by aavogt

  • Cc vogt.adam@… added

Hello.

Please see attached preliminary quasiquoter. It doesn't work because TH can't represent ViewPatterns.

It probably does the right thing that each option binds the same variables, though variables in any Exp (with -XViewPatterns) would have to be ignored.

Maybe this isn't an efficient approach since repeated patterns may not be shared? Keep in mind that I'm not familiar with how 'or' patterns can be compiled.

comment:3 Changed 4 years ago by igloo

  • Milestone set to _|_

comment:4 Changed 3 months ago by lpsmith

  • Cc leon.p.smith@… added
  • Difficulty set to Unknown
Note: See TracTickets for help on using tickets.