haskell - 从树中提取特定类型

Question

我已经建立了一棵树，我想从中收集所有叶子类型:

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)