从树中提取特定类型

Question

我已经构建了一棵树,我想从中收集所有Leaf类型:

Branch [] (Branch [0] (Leaf [0,1]) (Branch [0] (Leaf [0,2]) (Branch
[0] (Leaf [0,3]) (Leaf [0])))) (Branch [] (Branch [1] (Leaf [1,2])
(Branch [1] (Leaf [1,3]) (Leaf [1]))) (Branch [] (Branch [2] (Leaf
[2,3]) (Leaf [2])) (Branch [] (Leaf [3]) (Leaf []))))

我:t在上述变量的GHCI()中得到的类型是:

Tree [Int]

数据结构如下:

data Tree a = Empty | Leaf a | Branch a (Tree a) (Tree a)

我试图孤立ONLY叶子,这样我会获得:

[ [0,1], [0,2] .. [3], [] ]

我一直试图filter在结果上运行,但这不起作用.我已经尝试使用该函数Data.Foldable.toList,但它也会拉入所有分支并导致大量列表中包含多个重复项,并且无法判断它是分支还是叶子.

Answer 1

尽管存在其他方法，但最简单的方法可能是使用递归。这里的基本情况是Empty和Leaf。如果是 an Empty，我们返回一个空列表，如果是 a Leaf，我们可以返回一个包含一个元素的列表：包裹在叶子中的元素，所以：

leave_elements :: Tree a -> [a]
leave_elements Empty = []
leave_elements (Leaf x) = [x]
leave_elements (Branch ...) = ...

我们仍然需要填写大小写Branch，在这里我们看到构造函数中的三个元素：a，我们可以忽略它，以及两个子树。我们可以在子树上递归调用leave_elements，并追加子树叶子数据的列表。例如：

leave_elements :: Tree a -> [a]
leave_elements Empty = []
leave_elements (Leaf x) = [x]
leave_elements (Branch _ l r) = leave_elements l ++ leave_elements r

对于给定的示例树，这会产生：

Prelude> leave_elements (Branch [] (Branch [0] (Leaf [0,1]) (Branch [0] (Leaf [0,2]) (Branch [0] (Leaf [0,3]) (Leaf [0])))) (Branch [] (Branch [1] (Leaf [1,2]) (Branch [1] (Leaf [1,3]) (Leaf [1]))) (Branch [] (Branch [2] (Leaf [2,3]) (Leaf [2])) (Branch [] (Leaf [3]) (Leaf [])))))
[[0,1],[0,2],[0,3],[0],[1,2],[1,3],[1],[2,3],[2],[3],[]]

我们还可以通过使用递归传递的尾部来提高性能：

leave_elements :: Tree a -> [a]
leave_elements = go []
    where go tl Empty = tl
          go tl (Leaf x) = (x:tl)
          go tl (Branch _ l r) = go (go tl r) l

或者我们可以使用Data.DList：

import Data.DList

leave_elements :: Tree a -> [a]
leave_elements = toList . go
    where go Empty = empty
          go (Leaf x) = singleton x
          go (Branch _ l r) = append (go l) (go r)