What have you found for these years?

2009-12-10

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)))

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0