haskell - 折叠树函数

Question

我正在尝试为树编写一个折叠函数:

data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving (Eq, Ord, Show)

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ base Leaf = base
foldTree fn base (Node left a right) = fn a (foldTree fn acc right)
         where acc = foldTree fn base left

这段代码几乎可以工作。但并非总是如此。例如，它不会重建与原始树完全相同的树。

Answer 1

GHC 擅长折叠东西。您的类型的结构本身包含足够的信息，使您所需的有序遍历策略对机器来说是显而易见的。要调用魔法咒语，请说出“deriving Foldable!”，GHC 将为您编写函数。

{-# LANGUAGE DeriveFoldable #-}
data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving Foldable

现在我们有了

foldTree = foldr

这里的一个有趣的推论是，您可以通过改变类型的形状来改变遍历顺序。

<小时/>

当我们在这里时，请注意您的要求。您想要使用 foldr 实现一个函数，它将一棵树分开并以完全相同的方式将其重新组合在一起，相当于 id。 这是不可能的。 foldr 提供对 Foldable 结构元素的顺序访问，删除树中元素的精确位置等信息。最好的情况是，您可以构建一个列表形状的树，其中元素沿着右脊柱出现:

toListShapedTree = foldr (Node Leaf) Leaf

你想要的是一个变形:

cata :: (b -> a -> b -> b) -> b -> BinaryTree a -> b
cata node leaf Leaf = leaf
cata node leaf (Node l x r) = node (cata node leaf l) x (cata node leaf r)

注意 node 参数的额外参数!此规范允许折叠函数访问 Node 构造函数的参数。与Foldable不同，结构的变形类型是特定于该结构的。通过将所有内容视为列表，我们不会丢失信息。现在你可以写:

cataId = cata Node Leaf

如果您执意要使用 foldr 来实现此目的，一种策略可能是随身携带位置信息。第一 label each element with its position ，然后在折叠中使用该数据来重建树。对我来说似乎很辛苦。