Opened 7 years ago

Last modified 2 weeks 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 7 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

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

comment:2 follow-up: 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 6 years ago by igloo

  • Milestone set to _|_

comment:4 Changed 3 years ago by lpsmith

  • Cc leon.p.smith@… added
  • difficulty set to Unknown

comment:5 Changed 2 years ago by rwbarton

  • Cc rwbarton added

comment:6 Changed 20 months ago by gershomb

  • Cc gershomb added

comment:7 in reply to: ↑ 2 Changed 20 months ago by aavogt

Replying to aavogt:

I've since uploaded that QQ to hackage:

comment:8 Changed 19 months ago by sergv

  • Cc sergv added

comment:9 Changed 13 months ago by zardoz

  • Cc zardoz added

comment:10 Changed 11 months ago by osa1

  • Cc osa1 added

comment:11 Changed 11 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 11 months ago by goldfire

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

comment:13 Changed 9 months ago by gkaracha

  • Cc gkaracha added

comment:14 Changed 4 months ago by mpickering

  • Cc mpickering added

comment:15 Changed 4 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 4 weeks 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 4 weeks 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 4 weeks 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 2 weeks ago by RyanGlScott

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