如何编写 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 是用来代替无价值的 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.: 关于术语的注释。说一个函数是 "like foldr but for trees" 是有歧义的，因为有两种众所周知的函数类似于 foldr。首先，你有 Foldable class 的方法（参见），无论你做什么，它都会在折叠树时将其展平成一个列表。还有更强大的catamorphisms，比如你用的foldT，可以利用树结构

Answer 2

每次开始的第一件事就是开始匹配模式 :) 在这一点上，它几乎是机械的！

假设你有：

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

让我们开始匹配模式吧！ :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z ...

第一个 Tree 构造函数是什么？是 Leaf!

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf = ...

我们可以放什么？我们需要 b 类型的东西……而且我们只有一种方法可以得到它。通过使用 z :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf = z

因此，机械地，我们可以继续下一个可能的模式：

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf           = z
foldT f z (Node t1 x t2) =

好吧，我们可以做到 z，但这有点无聊。我们可能想使用 t1、x 和 t2。我们可以使用 f，它需要 a 类型的东西...我们有 x :: a :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf           = z
foldT f z (Node t1 x t2) = f x ??? ???

f 还有两个参数，类型为 b，那么你认为我们可以放什么？我们可以把 z 放两次，但这有点无聊。我们怎样才能从 t1 和 t2 得到 b？

Answer 3

如果你想把树转成列表那么这个函数就比较简单了，所以基本上如果你有树结构，例如：

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

然后你必须从树中提取值并将第一个值添加到一个空列表中，然后在列表的帮助下递归地将相同的方法应用于树的其他分支 (++)运算符将所有结果附加到一个列表中，即：

toList :: Tree a -> [a]
toList Leaf                    =    []
toList (Node left value right) =    [value] ++ toList left ++ toList right

然后折叠它，首先：

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

函数签名在这里缺少一个参数让我们看一下签名：a（第一个参数）-> b（第二个）-> b（第三个）-> b（return type) 该函数采用 3 个参数/参数，但是 您提供的签名 只有 1 个 b 类型（我猜这是你的累加器），所以基本上这就是你正在寻找的函数签名：

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

现在我们可以使用这个签名，然后让我们转到函数：

foldT :: (a -> b -> b) -> b -> Tree a -> b
foldT f acc Leaf                    =   acc
foldT f acc (Node left value right) =   foldT f (foldT f (f value acc) left) right

虽然我认为我不应该给你答案，你应该多练习一下递归数据结构，这样你才能更好地理解如何遍历它们。

PS：如果你要给我投反对票，请至少解释一下原因！

Answer 4

糟糕，你为什么要写代码？ GHC 可以自动填写您要查找的 the Foldable class, which contains the toList 的实例。

{-# LANGUAGE DeriveFoldable #-}
import Data.Foldable

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

treeToList :: Tree a -> [a]
treeToList = toList

由于 Node 构造函数的字段顺序，treeToList 的这个定义将执行 pre-order traversal。

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

How to write a function of type a-> b -> b -> b for folding a tree

haskell

tree

append

fold