module Repmin where

data Tree = Leaf Int | Fork Tree Tree
     deriving Show

{-
The straightforward solution:
-}

tmin :: Tree -> Int 
tmin (Leaf n) = n 
tmin (Fork l r) = min (tmin l) (tmin r)

replace :: (Tree, Int) -> Tree 
replace(Leaf _, m) = Leaf m 
replace (Fork l r, m) = Fork (replace (l, m)) (replace (r,m))

transform :: Tree -> Tree
transform t = replace (t, tmin t)

{- 
The circular version 
-}

repmin_c :: (Tree, Int) -> (Tree, Int) 
repmin_c (Leaf n, m) = (Leaf m, n) 
repmin_c (Fork l r, m) = (Fork t1 t2, min m1 m2)
    where (t1, m1) = repmin_c (l, m) 
          (t2, m2) = repmin_c (r, m)

transform_c :: Tree -> Tree 
transform_c t = nt
    where 
        (nt, m) = repmin_c (t, m)

{-
The higher-order version
-}
repmin_ho :: Tree -> (Int -> Tree, Int) 
repmin_ho (Leaf n)   = (\m -> Leaf m, n) 
repmin_ho (Fork l r) = (\m -> Fork (t1 m) (t2 m), min m1 m2)
    where (t1, m1) = repmin_ho l
          (t2, m2) = repmin_ho r

transform_ho :: Tree -> Tree 
transform_ho t = nt m
    where 
        (nt, m) = repmin_ho t