哈斯克爾樹列表

哈斯克爾我們走吧！好了，所以這裏是目前使用的代碼示例：哈斯克爾樹列表

data Tree a = Node (Tree a) (Tree a) | Leaf a | Empty deriving (Show) 
main = do 
let my_tree = Node (Node (Leaf [1,2,4,9]) (Leaf [3,5,5,8,5])) (Leaf [2,7,5,5,2]) 
cc my_tree 
bb my_tree 
aa my_tree 
cc my_tree 
print("Done")

只需在創建樹保存詮釋名單和需要3個職能工作AA，BB，CC：

CC - 簡單地輸出一棵樹
BB - 廣告，每個值+2
AA - 輸出列表就像每個值：長度，最小值，最大值]

現在有，做這一切的代碼幾乎是完美的，我把它放在鍵盤（問我，如果你想）：http://codepad.org/ ??????? 現在你可以看到AA最後輸出也是一棵樹
它可能是一個速戰速決，但我不能算出它 - 這樣AA將輸出不是樹，但一個[這些]列表：

[length param,minimum param,maximum param]

換句話說，有人知道如何將它作爲列表輸出，而不是在樹內？
所以在輸出代替：

Node (Node (Leaf [4,1,9]) (Leaf [6,0,8])) (Leaf [5,2,7])

將

[[4,1,9],[6,0,8],[5,2,7]]

我相信有些事情在這裏修改：

fmap3 ff (Node l r) = Node (fmap2 ff l) (fmap2 ff r) 
fmap3 ff (Leaf x) = Leaf (ff x)

任何人？

來源

2010-11-08 Florian Dardenua

這是功課？ – Paul 2010-11-08 17:57:30

您正在嘗試執行減少操作：將樹變成單個值（三次：長度，最大值，最小值）。這不能用map函數完成，因爲按照定義，map總是將樹變成樹。

典型的歸約算法使用函數將兩個簡化結果「合併」在一起，並遞歸合併樹中任何位置獲得的結果。所以，你就做這樣的事：

reduce ff (Node l r) = ff (reduce ff l) (reduce ff r) 
reduce ff (Leaf x) = x

一旦做到這一點，你可以使用地圖功能把你的（其他）到值的樹被還原樹，並應用減少功能。

cc tree = [ reduce (+) (fmap2 length tree) , 
      reduce (min) (fmap2 minimum tree) , 
      reduce (max) (fmap2 maximum tree) ]

編輯：你已經改變了你的問題，而我回答。您可以使用上述縮減函數和列表級聯功能++來完成此操作，但列表級聯在性能方面並不很性感。

有通過遍歷與蓄能器參數把一棵樹到列表中的慣用方式：

traverse init (Node l r) = traverse (traverse init r) l 
traverse init (Leaf x) = x : init 

cc tree = traverse [] (fmap2 h tree)

來源

2010-11-08 18:03:37

啊我明白了..好吧，我現在就試試吧！現在我只是嘗試了第一部分：http：//codepad.org/1XPYIMOH – 2010-11-08 18:19:06

似乎它輸出所有樹的最大值，最小值，長度，現在嘗試第二部分 – 2010-11-08 18:19:25

完美！現在，想出如何按照第三個參數的升序對最終結果進行排序（最大值） – 2010-11-08 18:22:27

這一個工程

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

treeToList :: (Ord a) => Tree a -> [a] 
treeToList EmptyTree = []   
treeToList (Node root left right) = treeToList left ++ [root] ++ treeToList right

來源

2014-01-17 16:58:17

哈斯克爾樹列表

回答

相關問題