母語

差點忘記，scm 老師「昨天」秀了一個 Haskell 的炫技，只用一次 traversal 就把一棵樹裡面的值全部換成最小值。我看到題目的時候一直覺得很怪，怎麼想都要兩次啊，果然 Haskell 不是我的母語 XD。詳情在此，以下是摘要。

data ETree a = Tip a | Bin (ETree a) (ETree a)
               deriving Show

foldet :: (b -> b -> b) -> (a -> b) -> ETree a -> b
foldet f g (Tip x) = g x 
foldet f g (Bin t u) = f (foldet f g t) (foldet f g u)

mineTree :: Ord a => ETree a -> a
mineTree = foldet min id

repeTree x = foldet Bin (const x)
-- or mapet (const x)

-- spec: repmin x = split (repeTree x) mineTree
repmin x = foldet (\p q -> (Bin (fst p) (fst q), min (snd p) (snd q)))
                  ((,) (Tip x)) 

repbymin t = let (t', m) = repmin m t in t'

關鍵當然是 Haskell 的 lazy evaluation。其實我還不是完全理解怎麼運作的，要再想一下 XD。

--
要想像這就是未經訓練的痛苦 XD。