Richard A. O'Keefe wrote:

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

From personal experience, OR patterns are quite handy when handing an AST where many of the alternatives are to be handled the same. That said, supporting OR patterns in MetaOCaml was responsible for some of

I can't speak for SML, but I was curious to try your example in OCaml, which also supports OR patterns. Here is how it looks in OCaml: let f = function ((1,_)|(_,1)), ((2,_)|(_,2)), ((3,_)|(_,3)), ((4,_)|(_,4)), ((5,_)|(_,5)), ((6,_)|(_,6)), ((7,_)|(_,7)), ((8,_)|(_,8)), (0,0) -> true | _ -> false ;; let g () = f ((1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(1,1)) ;; let _ = g ();; It compiled instantly. I was curious what it is compiled to. Enclosed in the result, in an intermediate language called Lambda (before optimizations). It seems the size of the code is linear in n. Not too bad. BTW, match/1207 is the identifier called match with the timestamp 1207. The timestamps tell distinct identifiers with the same given name apart. Also, 1a means true and 0a means false (and also unit and the empty list). the most complex code there. ocamlc -c -dlambda p.ml (setglobal P! (let (f/1199 = (function param/1206 (let (match/1207 =a (field 0 param/1206)) (catch (catch (if (!= (field 0 match/1207) 1) (if (!= (field 1 match/1207) 1) (exit 1) (exit 2)) (exit 2)) with (2) (let (match/1227 =a (field 1 param/1206)) (catch (if (!= (field 0 match/1227) 2) (if (!= (field 1 match/1227) 2) (exit 1) (exit 4)) (exit 4)) with (4) (let (match/1245 =a (field 2 param/1206)) (catch (if (!= (field 0 match/1245) 3) (if (!= (field 1 match/1245) 3) (exit 1) (exit 6)) (exit 6)) with (6) (let (match/1261 =a (field 3 param/1206)) (catch (if (!= (field 0 match/1261) 4) (if (!= (field 1 match/1261) 4) (exit 1) (exit 8)) (exit 8)) with (8) (let (match/1275 =a (field 4 param/1206)) (catch (if (!= (field 0 match/1275) 5) (if (!= (field 1 match/1275) 5) (exit 1) (exit 10)) (exit 10)) with (10) (let (match/1287 =a (field 5 param/1206)) (catch (if (!= (field 0 match/1287) 6) (if (!= (field 1 match/1287) 6) (exit 1) (exit 12)) (exit 12)) with (12) (let (match/1297 =a (field 6 param/1206)) (catch (if (!= (field 0 match/1297) 7) (if (!= (field 1 match/1297) 7) (exit 1) (exit 14)) (exit 14)) with (14) (let (match/1305 =a (field 7 param/1206)) (catch (if (!= (field 0 match/1305) 8) (if (!= (field 1 match/1305) 8) (exit 1) (exit 16)) (exit 16)) with (16) (let (match/1311 =a (field 8 param/1206)) (if (!= (field 0 match/1311) 0) (exit 1) (if (!= (field 1 match/1311) 0) (exit 1) 1a)))))))))))))))))) with (1) 0a))) g/1201 = (function param/1205 (apply f/1199 [0: [0: 1 1] [0: 2 2] [0: 3 3] [0: 4 4] [0: 5 5] [0: 6 6] [0: 7 7] [0: 8 8] [0: 1 1]]))) (seq (apply g/1201 0a) (makeblock 0 f/1199 g/1201))))