Haskell,来自树的列表列表 [英] Haskell, list of lists from a tree
问题描述
我有一个树的数据结构:
I have this data structure for a tree:
数据树 a = NodeT a (树 a) ( 树 a) |空T
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
到这个:[[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]]
如何使用递归来实现?
有人吗?
谢谢
推荐答案
您递归计算层级,并始终逐点合并来自两个子树的列表(因此相同深度的所有切片合并在一起).
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
如果树是完整的(从根到列表的所有路径的长度都相同),那么您可以使用 zipWith (++)
作为 merge
.
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
.
这篇关于Haskell,来自树的列表列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!