从树中提取特定类型

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 []))))

我在上述变量的GHCI（:t）中获得的类型是：

Tree [Int]

数据结构如下：

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

我试图孤立叶子，这样我会得到：

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

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

Answer 1

虽然存在其他方法，但最简单的方法是使用递归。这里的基本案例是Empty和Leaf。在Empty的情况下，我们返回一个空列表，如果是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)

Answer 2

一种更先进的技术，可以节省您手动编写和维护递归函数的工作，就是使用通用编程库，如lens的Plated module。

以下是Plated的工作原理：您描述了如何识别值的子项 - 与值本身具有相同类型的直接子结构 - 通过编写Plated class的实例，并且库的各种高阶函数负责递归地查找子项的子项和等等。对于Tree数据类型，只有Branch构造函数有子项（左右子项），因此这些是我们应用f的唯一地方。

instance Plated (Tree a) where
    plate f (Branch x l r) = Branch x <$> f l <*> f r
    plate f t = pure t

（如果你愿意派生Data那么你甚至不必写plate。）

Plated的universe函数现在可以递归搜索树的子节点，子节点的子节点等等，返回一个惰性列表，该列表生成树中的每个节点。它的工作方式大致如下：

universe :: Plated a => a -> [a]
universe t = t : [descendant | child <- toListOf plate t, descendant <- universe child]

因此，要查找所有叶子，您只需要筛选此列表以搜索Leaf构造函数。

leaves :: Tree a -> [a]
leaves t = [x | Leaf x <- universe t]

任务完成！

Answer 3

正如@BenjaminHodgson在评论中指出的那样，以下解决方案是有效的，但不能在其他类型类中实现一致的实现。例如，使Tree成为Traversable的一个实例将导致traverse函数的实现，该函数必然接触Tree的所有元素。我将其留作学习目的，但不要使用此解决方案。

使用Foldable typeclass：

import qualified Data.Foldable as F

instance F.Foldable Tree where
    foldMap f Empty = mempty
    foldMap f (Branch x l r) = foldMap f l `mappend`
                               foldMap f r
    foldMap f (Leaf x) = f x

对于你的tree：

Prelude> foldr (\x acc -> x: acc) [] tree
[[0,1],[0,2],[0,3],[0],[1,2],[1,3],[1],[2,3],[2],[3],[]]