[Haskell-cafe] MultiCase alternative

[Oleg]

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

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

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