哈斯克爾樹列表 - 序遍歷

考慮下面的樹結構在Haskell：哈斯克爾樹列表 - 序遍歷

data Tree = Leaf Int | Node Int Tree Tree deriving Show

我怎樣才能得到哈斯克爾返回序中的數據的列表？

例如給出一棵樹：

Node 1 (Leaf 2) (Leaf 3)

返回類似：

preorder = [1,2,3]

來源

2012-02-29 Gravy

一旦你滿意，不要忘記接受答案。 – 2012-03-17 10:10:11

好吧，抱歉晚答覆，但我得到這個工作如下：

preorder(Leaf n) = [n] 
preorder(Node n treeL treeR) = [n] ++ preorder treeL ++ preorder treeR'code'

然而，這並不正常工作對我而言仍然

preorder (Leaf n) = [n] 
preorder (Node n a b) = n:(preorder a) ++ (preorder b)

來源

2012-03-19 03:26:14 Gravy

使用模式匹配

preorder (Leaf n) = [n] 
preorder (Node n a b) = n:(preorder a) ++ (preorder b)

來源

2012-02-29 00:57:07

我得到以下錯誤：不能匹配預期類型'[T0]「與實際類型'樹」在模式：節點捉住在方程'預購」序（節點NAB）= N：（預購a）++（預購b） – Gravy 2012-02-29 01:00:53

@Gravy這是奇怪的。嘗試添加一個顯式類型簽名'preorder :: Tree - > [Int]'。對我來說，你會有一個錯誤是沒有意義的。 – 2012-02-29 02:10:52

這很奇怪我只是測試它，似乎工作。你確定你正確地複製了一切嗎？ – mck 2012-02-29 02:14:13

你可以瞄準一個更通用的解決方案，讓您的數據類型的Foldable一個實例。在hackage有一個非常類似的例子，但是實現了後序訪問。如果你想支持預購參觀你將不得不寫這樣的事：

import qualified Data.Foldable as F 

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

instance F.Foldable Tree where 
    foldr f z (Leaf x) = f x z 
    foldr f z (Node k l r) = f k (F.foldr f (F.foldr f z r) l)

有了這個，你就可以使用每一個上Foldable類型作品的功能，如elem，foldr，foldr ，sum，minimum，maximum等（見here供參考）。

特別是，你正在尋找能與toList來獲得該列表。下面是你可以通過具有實例聲明寫什麼一些例子：

*Main> let t = Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5) 
*Main> F.toList t 
[1,2,3,4,5] 
*Main> F.foldl (\a x -> a ++ [x]) [] t 
[1,2,3,4,5] 
*Main> F.foldr (\x a -> a ++ [x]) [] t 
[5,4,3,2,1] 
*Main> F.sum t 
15 
*Main> F.elem 3 t 
True 
*Main> F.elem 12 t 
False

來源

2012-02-29 11:51:42

哈斯克爾樹列表 - 序遍歷

回答

相關問題