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.)