AvgTree in Haskell

想到之前在 flolac 聽到穆老師講過一個很神奇的 tree traversal,
大概的感覺就是先做出一個假想值，然後把這假想值用在各種地方，
先把結構建好，然後需要取得值時，忽然間就得到答案了。
有一種其實在哪裡都可以是全知全能的感覺...

google 半天找到這個（抱歉，幫你訂正了 evaluation 的拼法）
Two examples of lazy evaluation

照著上面的感覺自己寫了一次，在想應該就是這個吧？
原本我們會需要先把值都算出來，然後再重新把整棵樹建出來。
現在這樣只要先假設我們有最後的值，就能一邊算一邊建立。
事實上，正確的思考法或許是，我們根本就沒有在「計算」，
而是本來就有那樣一個答案在那裡，宣告出來，就可以直接用了。

噢，其實我上一篇就有提到嘛。
1306. 11-30 powerset (2)
自己都忘了........ @@... 去翻才忽然發現。

另一題則來自嵐達網：先寬度標記
看來我該找時間試試的。（以下的程式基本上跟文章裡的是一模一樣的）

module AvgTree where

data Tree a = Leaf a
            | Node a (Tree a) (Tree a)
            deriving Show

avgTree :: (Fractional a) => Tree a -> Tree a
avgTree t = result where
  (result, sum, count) = avgTree' t
  avg = sum / count
  avgTree' (Leaf n) = (Leaf avg, n, 1)
  avgTree' (Node n a b) = (Node avg left right,
                           n + suma + sumb,
                           1 + counta + countb) where
    (left,  suma, counta) = avgTree' a
    (right, sumb, countb) = avgTree' b

--              Node 6.0 (Leaf 6.0) (Node 6.0 (Leaf 6.0) (Leaf 6.0))
test = avgTree (Node 6   (Leaf 7)   (Node 8   (Leaf 9)   (Leaf 0)))