haskell - 如何编写 a-> b -> b -> b 类型的函数来折叠树

Question

一些背景:我在Haskell中有一个以下类型的foldT函数(类似于foldr，但用于树)。

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b 

此foldT仅将类型(a -> b -> b -> b)作为输入函数。

我正在尝试找到一种方法将我的树转换为列表，但无法找到一种方法使我的追加函数采用 (a -> b -> b -> b) 的形式。

以下内容无效，因为它不是正确的类型:

append x y z = append x:y:z 

如有任何帮助，我们将不胜感激。

谢谢!

Answer 1

由于您尚未发布，我假设您的树是...

data Tree a = Leaf | Node a (Tree a) (Tree a)

...并且 foldT 的 a -> b -> b -> b 参数采用 Node 构造函数的字段按照声明的顺序。

I am trying to find a way to convert my tree into a list

让我们开始通过以下类型来解决这个问题:

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b

您想将其展平为列表，因此函数的结果类型必须为[a]:

treeToList :: Tree a -> [a]

这给了我们如何继续的好主意:

treeToList t = foldT f z t

与:

f :: a -> [a] -> [a] -> [a]
z :: [a]
t :: Tree a

现在，进入论点。 z 是将插入代替无值(value)的 Leaf 的内容，因此它必须是 []。至于f，它必须将从左右分支创建的子列表与直接在Node中的值组合起来。假设按顺序遍历，我们有:

 treeToList t = foldT (\x l r -> l ++ x : r) [] t

或者，不提及t:

 treeToList = foldT (\x l r -> l ++ x : r) []

就是这样。需要注意的是，重复使用左嵌套 (++) (在这种情况下会发生，因为 foldT 递归地沿着分支走)可能会变得非常低效。在您关心性能的情况下，值得考虑实现连接函数的替代方法，例如 difference lists .

P.S.:关于术语的说明。说一个函数“类似于foldr，但用于树”是不明确的，因为有两种众所周知的函数类似于foldr。首先，您拥有 Foldable 类的方法(参见 Benjamin Hodgson's answer )，无论您做什么，它们都会在折叠树时将树扁平化为列表。然后还有更强大的变形，例如您正在使用的foldT，它们能够利用树结构。