哈斯克尔,树列表的列表 [英] Haskell, list of lists from a tree
问题描述
数据树a = NodeT a(树a)(树a) EmptyT
我需要创建一个函数,它返回列表的列表,其中列表的每个元素表示树的一个级别。例如,从这个:
1
/ \
2 3
/ \\ \\ / \
4 5 6 7
对此:[[1],[ 2,3],[4,5,6,7]]
函数必须具有以下形式:
f ::树a - > [[a]]
如何使用递归来做到这一点?
任何人?
谢谢
您递归地计算级别并始终合并两个子树中的列表(因此所有在同一深度的片段合并在一起)。
f :: Tree a - > [[a]]
f EmptyT = []
f(NodeT a t1 t2)= [a]:merge(f t1)(f t2)
merge :: [ a]] - > [[a]] - > [[a]]
merge [] ys = ys
合并xs [] = xs
merge(x:xs)(y:ys)=(x ++ y):merge xs ys
如果树是完整的(从根到列表的所有路径长度相同),那么你可以使用 zipWith(++)
作为 merge
。
I have this data structure for a tree:
data Tree a = NodeT a (Tree a) ( Tree a) | EmptyT
I need to create a function that returns a list of lists where each element of the list represents a level of the tree. For instance, from this:
1
/ \
2 3
/ \ / \
4 5 6 7
to this: [[1],[2,3],[4,5,6,7]]
The function must have the following form:
f :: Tree a -> [[a]]
How to do it using recursion?
anyone?
Thanks
You recursively compute the levels and always merge lists from two subtrees point-wise (thus all the slices in the same depth get merged together).
f :: Tree a -> [[a]]
f EmptyT = []
f (NodeT a t1 t2) = [a] : merge (f t1) (f t2)
merge :: [[a]] -> [[a]] -> [[a]]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = (x ++ y) : merge xs ys
If the tree were complete (all the paths from the root to a list are of the same length) then you could use zipWith (++)
as merge
.
这篇关于哈斯克尔,树列表的列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!