## totally insane? 純粋関数的に1パスで木の全てのノードを最小値に書き換える &dagger;

http://obfuscatedcode.wordpress.com/2008/02/16/functional-pearl-trees/

```data Tree a = Leaf a          -- The leaf holds data of any type.
| Branch (Tree a) (Tree a) deriving (Show)

replaceMin :: Tree Int -> Tree Int
replaceMin t = let (t', m) = rpMin (t, m) in t'

rpMin :: (Tree Int, Int) -> (Tree Int, Int)
rpMin (Leaf a, m) = (Leaf m, a)
rpMin (Branch l r, m) = let (l', ml) = rpMin (l, m)
(r', mr) = rpMin (r, m)
in (Branch l' r', ml `min` mr)```

### OCaml版 &dagger;

```open Lazy
let ( !\$ ) = force

type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
let rec rp_min = function
| Leaf a, m -> Leaf m, a
| Branch (l,r), m ->
let l', ml = rp_min (l, m) in
let r', mr = rp_min (r, m) in
Branch (l', r'), lazy (min !\$ml !\$mr)

let replace_min t =
let rec t'_m _ = rp_min (t, lazy !\$(snd (t'_m ()))) in
fst (t'_m ())```
• この場合 t'_m が 2回走るため 実質 2パス

### OCaml版 (変数への代入を使う方法) &dagger;

```type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree
let rec map f = function
| Leaf l -> Leaf (f l)
| Branch (l, r) -> Branch (map f l, map f r)

let replace_min t =
let m = ref 0 in
map (fun a -> m := min !a !m; m) t```
• この場合 replace_min : int ref tree -> int ref tree になってしまう…

### OCaml版 その3 (変数への代入と遅延評価を使う方法) &dagger;

```type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree;;
let rec rp_min : (int tree * int ref) -> (int tree 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 : int tree -> int tree になった！ がこれは1パスではないような気も

### OCaml版 その4 (高階関数を使う方法) &dagger;

```type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree

let rec repMin t =
match t with
| Leaf    a  -> ((fun m -> Leaf m), a)
| Branch (l,r) ->
let (lf, lm) = repMin l in
let (rf, rm) = repMin r in
((fun m -> Branch (lf m,rf m)), min lm rm)
let replace_min t =
let (f,m) = repMin t in
f m ```

### F#版？ &dagger;

```#light
type tree<'T> = Leaf of 'T | Branch of tree<'T> * tree<'T>
with override t.ToString() =
match t with
|Leaf v
->sprintf "(Leaf %A)" v
|Branch (lhs,rhs)
-> sprintf "(Branch %s %s)" (lhs.ToString()) (rhs.ToString())

let rec rp_min =
function Leaf a, m -> Leaf m, a
|Branch (l,r), m
-> let l', ml = rp_min (l, m)
let r', mr = rp_min (r, m)
Branch (l', r'), lazy (min (ml.Force()) (mr.Force()))

let replace_min t = let rec t'_m () = rp_min (t, lazy ((snd (t'_m ())).Force()))
fst (t'_m ())```
```let rec force_nodes  =
function Leaf (lv: Lazy<'T>)
-> (Leaf(lv.Force()))
|Branch (lhs,rhs)
-> Branch( (force_nodes lhs), (force_nodes rhs))

let tree_before = Branch(Branch(Leaf(lazy 2), Branch(Leaf(lazy 1), Branch(Leaf(lazy 3), Leaf(lazy 5)))), Leaf(lazy 4))
let tree_after = replace_min( tree_before )
printfn "Before: %O" (force_nodes tree_before)
printfn "After : %O" (force_nodes tree_after)```

## StateT &dagger;

これは、permutationを返す関数：

```permutation' :: [[Int]] -> Int -> [Int] -> [[Int]]
permutation' result 0 _ = result
permutation' result n cand =
do a <- cand
permutation' (map (a:) result) (n-1) [x|x<-cand,x/=a]```

`permutation' [[]] [1,2,3] 2`

のように使う。

これをStateTを使ってわざと分かりにくくしてみる：

```permutation :: [[Int]] -> Int -> StateT [Int] [] [[Int]]
permutation result 0 = return result
permutation result n =
do cand <- get
a <- lift cand
put [x|x<-cand,x/=a]
permutation (map (a:) result) (n-1) ```

これは

`runStateT (permutation [[]] 2) [1,2,3]`

のように使う。

• Thx. 勉強になります。 -- げんま? 2007-04-24 (火) 12:45:05
• 使い方は、permutation' [[]] 2 [1,2,3] ではないでしょうか? <-元職業プログラマ -- 2008-07-10 (木) 22:46:11