如何编写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)

...并且该a -> b -> b -> b参数以与声明它们相同的顺序foldT获取Node构造函数的字段.

我试图找到一种方法将我的树转换为列表

让我们按照以下类型开始解决这个问题:

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是什么将代替无价值的Leafs 插入,所以它必须是[].至于f它必须将从左右分支创建的子列表与直接在其中的值组合在一起Node.假设有序遍历,我们有:

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

或者,没有提到t:

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

就是这样.一个警告是,重复使用左嵌套(++)(在这种情况下会发生,因为foldT递归地向下走分支)可能会变得非常低效.在您关心性能的情况下,值得考虑实现连接函数的替代方法,例如差异列表.

PS:关于术语的说明.说一个函数"像折叠器但是对于树"是不明确的,因为有两种众所周知的函数类似于foldr.首先,你有Foldable类的方法(参见Benjamin Hodgson的答案),无论你做什么,它都会将树折成一个列表.然后有更强大的catamorphisms,例如foldT你正在使用的,它们能够利用树结构.