Opened 8 years ago

Last modified 11 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@…, rwbarton, gershomb, sergv, zardoz, osa1, gkaracha, mpickering, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


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.


Attachments (1)

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

Download all attachments as: .zip

Change History (20)

comment:1 Changed 8 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 7 years ago by aavogt

Attachment: QQ.hs added

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

comment:2 Changed 7 years ago by aavogt

Cc: vogt.adam@… added


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 7 years ago by igloo

Milestone: _|_

comment:4 Changed 4 years ago by lpsmith

Cc: leon.p.smith@… added
difficulty: Unknown

comment:5 Changed 3 years ago by rwbarton

Cc: rwbarton added

comment:6 Changed 3 years ago by gershomb

Cc: gershomb added

comment:7 in reply to:  2 Changed 3 years ago by aavogt

Replying to aavogt:

I've since uploaded that QQ to hackage:

comment:8 Changed 2 years ago by sergv

Cc: sergv added

comment:9 Changed 2 years ago by zardoz

Cc: zardoz added

comment:10 Changed 22 months ago by osa1

Cc: osa1 added

comment:11 Changed 22 months ago by osa1

If we could come up with a nice syntax for function definitions with or-patterns this would be really useful for GHC's own code too.

Often we have to re-compile GHC many times and test on some programs to discover all the places we need to update after adding a new data constructor, because of "catch-all" code like this:

f A = ...
f B = ...
f unexpected = pprTrace "f" (ppr unexpected)

With or patterns, we could do this instead:

f A = ...
f B = ...
f unexpected@(C{} | D{} | E{}) = pprTrace "f" (ppr unexpected)

(just made up a syntax)

This would be very convenient, because now I get a warning after adding data constructor D - instead of discovering this code after a runtime failure. And what happens if I couldn't discover this code because I couldn't come up with an example program that makes GHC run this function? So it's a bit tricky and annoying right now, and it's costing us time because of recompilations and tests.

comment:12 Changed 22 months ago by goldfire

Yes yes yes this would be wonderful. Would you like to design and implement it? :)

comment:13 Changed 19 months ago by gkaracha

Cc: gkaracha added

comment:14 Changed 15 months ago by mpickering

Cc: mpickering added

comment:15 Changed 14 months ago by Iceland_jack

Regarding syntax, could it use data constructor syntax with a magic module

import GHC.OrPatterns ( (:|:) ) -- ( pattern (:|:) ) ?

f A = ...
f B = ...
f unexpected@(C{} :|: D{} :|: E{}) = pprTrace "f" (ppr unexpected)

like Edward's suggestion in Records/OverloadedRecordFields/OverloadedLabels

import GHC.ImplicitValues( p, q, area )

import qualified GHC.OrPatterns as OR ( (:|:) )

f (C{} OR.:|: D{} OR.:|: E{}) = ...

comment:16 Changed 12 months ago by osa1

If anyone's interested, I started writing a proposal for this: any help on fleshing out the design would be appreciated.

comment:17 Changed 12 months ago by Iceland_jack

What about where | starts a guard? This parses just fine

f = \case
  True | False -> ...

One option is to mandate parentheses in that case ((True | False) -> ...) or to use some messier syntax :|, :|: ... I don't think or-patterns are common enough that will matter greatly.

comment:18 Changed 12 months ago by osa1

Good point. I think we may require parens around or patterns. So the parsing rule would be like:

pat ::= '(' or-pattern-or-pat ')'
     |  ... (where none of the productions accept '|')

    ::= pat '|' or-pattern-or-pat
     |  pat

I personally dislike messier syntax like :| and :|:, because I'm hoping to use this syntax instead of _ patterns, and I may need to chain a lot of constructors.

f (T1 ...) = ...
f (T2{} | T3{} | T4{}) = ...


f (T1 ...) = ...
f (T2{} :|: T3{} :|: T4{}) = ...

Second one looks really bad IMHO. In addition, :|: is a valid operator syntax, but | is a reserved operator.

comment:19 Changed 11 months ago by RyanGlScott

Cc: RyanGlScott added
Note: See TracTickets for help on using tickets.