哈斯克尔，树列表的列表 [英] 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屋！