Haskell-从根到叶的列表

Question

代码假设返回树中从根到叶的每条路径的列表，按从左到右的顺序。具有一个子节点(一个 Tip 和一个 Bin)的节点不被视为叶节点。

我尝试编写类似的代码

paths :: Tree a -> [[a]]
paths Tip = [[]]
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)

但似乎返回的路径包括带有一个子节点的节点。这将导致 Bin (Bin Tip 3 Tip) 4 Tip 上的 [[4,3],[4]] 等路径。

Answer 1

这是因为您的 paths Tip = [[]] 返回一个包含 一个 元素的列表:一个空列表。

这意味着，对于 Bin Tip 4 (Bin Tip 3 Tip) 来说，剩余路径 将返回 [[]]，并且在该列表前面添加 4，因此也会生成 [4]。

如果将其更改为 paths Tip = []，则可以解决问题，因为这样它将不会产生元素:

paths :: Tree a -> [[a]]
<b>paths Tip = []</b>
paths (Bin Tip x Tip) = [[x]]
paths (Bin left x right) = map (x:) (paths left ++ paths right)