哈斯克尔树列表 - 序遍历

考虑下面的树结构在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

哈斯克尔树列表 - 序遍历

回答

相关问题