[Haskell-cafe] MultiCase alternative

ok at cs.otago.ac.nz ok at cs.otago.ac.nz
Sun Jun 18 06:42:26 UTC 2017


> What evil lurks in the heart of OR-patterns?
>
> Let Pi be the pattern (i,_) | (_,i)
In SML,

 fun f P1 ... Pn (0,0) = true
   | f _  ... _  _     = false

 fun g () = f (1,1) (2,2) ... (n,n) (1,1)


> (So far it has taken 3 minutes on a fast machine to not
> finish compiling these 3 lines of code...  I fear the worst.)

I killed it after 24 minutes on a 3.2 GHz machine.
In Haskell,
ok n (x,y) = x == n || y == n
f (ok 1 -> True) ... (ok n -> True) (0,0) = true
f       _                  _          _   = false
g () = f (1,1) (2,2) ... (n,n) (1,1)
compiled and ran in a flash.
(Yes, I know that the Haskell version is "committed choice"
and the SML/NJ version is "backtracking search", but that's
the point: the *syntax* of OR-patterns may be simple but
sorting out the *semantics* is not.)





More information about the Haskell-Cafe mailing list