repMin を遅延評価を使わずに書く

遅延評価（または循環プログラミング？）の面白さを説明する例として repMin がある（Repmin Problem - Circular programming - Haskell）。

葉として整数値を持つ木があるとき、すべての葉を葉の最小値で置き換えるという問題だ。

repMin.hs

data Tree
    = Leaf Int
    | Branch Tree Tree
    deriving Show

単純な解法では、まず木を一度走査して葉の最小値を見つけ出し、もう一度走査してすべての葉をその値で置き換える。

repMin.hs

repMin :: Tree -> Tree
repMin tree = repLeaf (findMin tree) tree
  where
    findMin (Leaf n) = n
    findMin (Branch t1 t2) = findMin t1 `min` findMin t2
    repLeaf n (Leaf _) = Leaf n
    repLeaf n (Branch t1 t2) = Branch (repLeaf n t1) (repLeaf n t2)

しかし、次のようにすると木の走査を一回にできる。

repMin.hs

repMin' :: Tree -> Tree
repMin' tree = t
  where
    (m, t) = replace m tree
    replace m (Leaf n) = (n, Leaf m)
    replace m (Branch t1 t2) =
      let
        (m1, t1') = replace m t1
        (m2, t2') = replace m t2
      in (m1 `min` m2, Branch t1' t2')

(m, t) = replace m tree の両辺に m が現れているのがミソだ。ここで、最小値 m は実際に値が必要になるまではサンク（未評価の値）になっている。

正格評価の言語の例として、 OCaml で、遅延評価を使わず同じくひとつの再帰関数で書いてみる。

type tree
  = Leaf of int
  | Branch of tree * tree

let rep_min tree =
  let rec replace = function
    | Leaf n -> (n, fun m -> Leaf m)
    | Branch (t1, t2) ->
      let (m1, c1) = replace t1
      and (m2, c2) = replace t2
      in (min m1 m2, fun m -> Branch (c1 m, c2 m))
  in
  let (m, c) = replace tree in
  c m

Haskell 版で「最小値（を表すサンク）」と「葉を最小値で置き換えた木（を表すサンク）」を返していたのを、「最小値」と「値を受け取ると元の木の葉をその値で置き換えた木を返す関数」を返すようにする。「最小値」を計算しつつ、『「最小値」を使う計算』を陽に自分で組み立ててやる。