5
3

More than 5 years have passed since last update.

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

Posted at

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` は実際に値が必要になるまではサンク（未評価の値）になっている。

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

5
3
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
5
3