The Little Schemer の collector を OCaml で

The Little Schemer を買って割と簡単に読み進めていたら p.137 の multirember&co 関数のところで分からなくなったので OCaml で書き直してみた。

元の Scheme コードはこれ（わからん！）。

(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat)
       (col (quote ()) (quote ())))
      ((eq? (car lat) a)
       (multirember&co a
         (cdr lat)
         (lambda (newlat seen)
           (col newlat
             (cons (car lat) seen)))))
      (else
        (multirember&co a
          (cdr lat)
          (lambda (newlat seen)
            (col (cons (car lat) newlat)
              seen)))))))

(define a-friend
  (lambda (x y)
    (null? y)))

この multirember&co 関数は「引数 lat : list を (a.) lat から要素 a : atom に一致するものを取り除いたリストと (b.) 取り除かれた分の a のリストの2つに分けて、それら2つのリストを引数として関数 col を呼んでその値を返す関数」のはず…
a-friend 関数は col として与える関数の一例で、a を取り除いた後のリストが null かどうかを返す。

OCaml で書き直すとこうなった。

let rec multirember_and_co a lat col =
  match lat with
  | [] -> (1)
    col [] [] 
  | x::xs when x = a -> (2)
    multirember_and_co a xs (fun newlat seen -> col newlat (x::seen))
  | x::xs -> (3)
    multirember_and_co a xs (fun newlat seen -> col (x::newlat) seen)
;;

let a_friend x y = y = [] ;;

こっちのほうが大分読める。OCaml の複雑な yacc ファイルはすべて括弧を減らす為にあるのだということが分かります。

これがどのように動くかということを手作業で追ってみた。※ここからはパターンマッチのマッチ節を上から順に (1) , (2), (3) として指し示します

まず lat が空リストの場合。

multirember_and_co "tuna" [] a_friend
|
+-> (1) a_friend [] []

これは空リストのパターンにマッチしておわり。col として与えられた a_friend に [] [] を引数として与えてその結果を返す。

次に lat が a と一致する要素1つのみからなるリストの場合。

multirember_and_co "tuna" ["tuna"] a_friend
|
+-> (2) multirember_and_co "tuna" [] (fun newlat seen -> a_friend newlat ("tuna"::seen))
        |
        +-> (1) (fun newlat seen -> a_friend newlat ("tuna"::seen)) [] [] 
                 ||
                a_friend [] ("tuna"::[])
                 ||
                a_friend [] ["tuna"]

最初の呼び出しで ["tuna"] の car 部分と "tuna" が一致するので (2) にマッチして multirember_and_co を再帰呼び出しする。そのときの lat は [] （=["tuna"] の cdr 部分）で col は (fun newlat seen -> a_friend newlat ("tuna"::seen)) となる。

multirember_and_co "tuna" [] (fun newlat seen -> a_friend newlat ("tuna"::seen))

次の呼び出しでは lat は空リストになっているので (1) にマッチする。ここでは col として与えられた (fun newlat seen -> a_friend newlat ("tuna"::seen)) に [] [] を引数として与えて呼び出す。

(fun newlat seen -> a_friend newlat ("tuna"::seen)) [] []

newlat と seen を [] で置き換えると a_friend [] ("tuna"::[]) で、これは a_friend [] ["tuna"] というのと同じことになる。

さらに lat が a と一致する要素と一致しない要素の両方を持っている場合。

multirember_and_co "tuna" ["and;" "tuna"] a_friend
|
+-> (3) multirember_and_co "tuna" ["tuna"] (fun newlat seen -> a_friend ("and"::newlat) seen)
        |
        +-> (2) multirember_and_co "tuna" [] (fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen))
                |
                +-> (1) (fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen)) [] [] 
                         ||
                        (fun newlat seen -> a_friend ("and"::newlat) seen) [] ("tuna"::[])
                         ||
                        a_friend ("and"::[]) ("tuna"::[])
                         ||
                        a_friend ["and"] ["tuna"]

最初の呼び出しでは ["and;" "tuna"] の car は "and" であり "tuna" と一致しないので (3) にマッチする。multirember_and_co を再帰呼び出しするが、ここでは lat は ["tuna"] （=["and;" "tuna"] の cdr 部）で col は (fun newlat seen -> a_friend ("and"::newlat) seen) となる。

multirember_and_co "tuna" ["tuna"] (fun newlat seen -> a_friend ("and"::newlat) seen)

次の呼び出しでは lat = ["tuna"] の car 部分と "tuna" が一致するので (2) にマッチして multirember_and_co を再帰呼び出しする。今度は lat は [] で col は (fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen)) となる（無名関数が二重になる）。

multirember_and_co "tuna" [] (fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen))

さらに次の呼び出しでは lat は空リストになったので (1) にマッチする。ここで col として与えられた (fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen)) に引数として [] [] を与えて呼び出すことになる。

(fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen)) [] []

まずは外側の関数の newlat と seen を [] に置き換えると (fun newlat seen -> a_friend ("and"::newlat) seen) [] ("tuna"::[]) となる。

(fun newlat seen -> (fun newlat seen -> a_friend ("and"::newlat) seen) newlat ("tuna"::seen)) [] [] 
 ||
(fun newlat seen -> a_friend ("and"::newlat) seen) [] ("tuna"::[])

ここからさらに newlat を [] 、 seen を "tuna"::[] で置き換えると a_friend ("and"::[]) ("tuna"::[]) となる。

(fun newlat seen -> a_friend ("and"::newlat) seen) [] ("tuna"::[])
 ||
a_friend ("and"::[]) ("tuna"::[])

これは a_friend ["and"] ["tuna"] というのと同じことだ。

で、こういう場合の col に当たるものを collector と呼んで、リストから一度に複数の値を掻き集める場合に使うのだとか。