遅延評価

id:Uuutokuda:20051117:1132202387に関して。
このソースコード、まずOcamlの方を見てみる。書いたのはk.inabaさん。D言語を操ったりするらしい。zipperについてよく分からないのでなんとも言いがたいのだけど、多分遅延評価は使っていないのではないかと思う。
で、次にHaskellのコードなのだが、Haskellなのでもちろん遅延評価なのだが、別にこのソースは遅延評価の特性を使ってはいない。副作用もないようなこんなソースコードでは、別に遅延評価をする価値もないし、遅延評価をして結果が変わるわけもない。そもそも、遅延評価かどうかが大きくかかわってくる場合というのは、今書いた「副作用がある場合」というのが一つ。そしてもう一つは再起にかかわるループが止まらないケースがありうる場合の二つだ。つまり、Haskellで書いた場合にはループがとまるのに、Ocamlで書いた場合に止まらないということがありうる。で、この場合は副作用なんかは無い訳で、遅延評価の特性を使っているかどうかをチェックするには、Ocamlでそのまま書いてやればいいことになる。
やってみよう。まず元のソースは以下。

data Tree a = Leaf a | Branch [Tree a]

fringe :: Tree a -> [a]
fringe (Leaf x)    = [x]
fringe (Branch cs) = foldr ((++) . fringe) [] cs

samefringe :: Eq a => Tree a -> Tree a -> Bool
samefringe t u = fringe t == fringe u

これを逐語訳してみる。まず、dataの宣言。

type 'a tree = Leaf of 'a | Blanch of ('a tree) list;;

明らか。ただ、Haskellの方が直感的に見えるのだけども・・・・
で、次にfringeの定義を書く。

let rec fringe = function
         Leaf(x) -> [x]
       | Blanch(x::y) -> (List.append (fringe x) (fringe (Blanch(y))))
       | Blanch([ ]) -> [ ];;

これは単なるマッチング。このマッチング文法は正直、Ocamlの方が綺麗だと思う。で、Haskellのfoldr関数の仕様がよくわからないのだけども、まあ、Haskellではそれぞれにfringeを適用してからリストを結合しているようなので、Ocamlでも同じようなことをやってみた。
そして、最後にその比較を行うわけで

let rec samefringe x y = (fringe x) = (fringe y);;

ということになる。Haskellでは==によってリストが同じかどうかを比較できる。Ocamlの場合は、==はポインタ比較となってしまうので、=で内容比較を行う。
これで完成したOcamlのソースを実行すると・・・・あら不思議・・・でもなんでもなくて、ちゃんと比較できる。

type 'a tree = Leaf of 'a | Blanch of ('a tree) list;;

let rec fringe = function
         Leaf(x) -> [x]
       | Blanch(x::y) -> (List.append (fringe x) (fringe (Blanch(y))))
       | Blanch([ ]) -> [ ];;

let rec samefringe x y = (fringe x) = (fringe y);;


samefringe
     (Blanch [Blanch [Leaf 1; Leaf 2]; Blanch [Leaf 3; Leaf 4; Leaf 5]])
     (Blanch [Blanch [Blanch [Leaf 1]; Leaf 2];
                     Blanch[Leaf 3; Blanch [Leaf 4;Blanch [Leaf 5]]]]);;

ということで、このソースは遅延評価の特性は別に使っていないことが分かる。おしまい。