遅延評価マジック

Haskell

前回の OCaml-Nagoyaで Haskellの遅延評価とvalue recursionを使ったネタの記事を紹介したら皆けっこうおもしろがってくれた。 で、OCaml や SML といった 遅延評価モジュールがある言語ではどう書く？ というネタで さらに少し盛り上がった。

rp_min は lazy する場所を別にすればほぼ同じ。 問題は いかに value recursion をやるかということだけど…

let replace_min t : int t tree = 
  let rec v = rp_min (t, lazy !$(snd v))
  in fst v;;

これはNG。(ここで 型tはLazy.t , !$はLazy.force)

This kind of expression is not allowed as right-hand side of `let rec'

ということらしい。 そもそも value recursion は 循環するデータ構造を書く為のものらしいので、まあしょうがない。
だからといって

let replace_min t =
  let rec t'_m _ = rp_min (t, lazy !$(snd (t'_m ()))) in
  fst (t'_m ())

こう書くとt'_m は つごう 2回呼ばれてしまうので 結局 2パスになってしまう。

参照を使って、 replace_min : int tree -> int ref tree とかやってもいいのだけど、できたら型シグネチャだけでもpurely functionalっぽくしたい。

で考えたのが以下、 replace_min : int tree -> int tree 、かつ1パス。 …と調子こいたはいいけど…最後にforceしてまわるので結局2パスか！？よくわからん

let ( !$ ) = Lazy.force;;

type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree;;
let rec rp_min : (int tree * int ref) -> (int tree Lazy.t * int) = function
  | Leaf a, m -> (lazy (Leaf !m)), a
  | Branch (l,r), m ->
      let l', ml = rp_min (l, m) in
      let r', mr= rp_min (r, m) in
      lazy (Branch (!$l', !$r')), min ml mr;;

let replace_min t : int tree =
  let cell = ref 0 in
  let t', m = rp_min (t,cell) in
  cell := m; !$t';;

replace_min (Branch (Leaf 1, Branch (Leaf 3,Leaf 2)));;

ref 0 で代入した 0 は使われないのがポイントといえばそうかもしれない。 Haskellの場合はこのcellにボトムか何かが入ってると思えばいい。

- : int tree = Branch (Leaf 1, Branch (Leaf 1, Leaf 1))

うごく。