如何编写 a-> 类型的函数b->b->b 用于折叠一棵树 [英] How to write a function of type a-> b -> b -> b for folding a tree

问题描述

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

Some background: I have a foldT function (like foldr but for trees) of the following type in Haskell.

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

这个 foldT 只接受 type (a -> b -> b -> b) 作为输入函数.

This foldT only takes type (a -> b -> b -> b) as an input function.

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

I am trying to find a way to convert my tree into a list, and cannot figure out a way to make my append function take the form (a -> b -> b -> b).

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

The following is ineffective because it is not the correct type:

append x y z = append x:y:z 

任何帮助将不胜感激.

谢谢！

推荐答案

由于你还没有发布它，我假设你的树是......

As you haven't posted it, I will assume your tree is...

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

... 并且 a ->b->b->foldT 的 b 参数采用 Node 构造函数的字段，其顺序与声明的顺序相同.

... and that the a -> b -> b -> b argument to foldT takes the fields of the Node constructor in the same order they were declared.

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

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

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

Let's begin tackling this by following the types:

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

你想把它展平成一个列表，所以你的函数的结果类型必须是[a]:

You want to flatten it into a list, so the result type of your function must be [a]:

treeToList :: Tree a -> [a]

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

That give us a good idea on how to continue:

treeToList t = foldT f z t

与:

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

现在，继续讨论.z 是代替无价值的 Leaf 插入的内容，因此它必须是 [].至于f，它必须将左右分支创建的子列表与Node中直接的值结合起来.假设按顺序遍历，我们有:

Now, onward to the arguments. z is what will be inserted in lieu of the valueless Leafs, and so it must be []. As for f, it must combine the sublists created from the left and right branches with the value directly in the Node. Assuming an in-order traversal, we have:

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

或者，不提t:

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

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

And that's it. One caveat is that repeatedly using left-nested (++) (which will happen in this case, as foldT walks down the branches recursively) can get quite inefficient. In a situation in which you would care about performance it would be worth considering alternative ways of implementing the concatenating function, such as difference lists.

P.S.:关于术语的说明.说一个函数类似于 foldr 但用于树"是模棱两可的，因为有两种众所周知的函数类似于 foldr.首先，您有 Foldable 类的方法(参见 Benjamin Hodgson 的答案)，它无论您做什么，都可以在折叠树时将其展平为列表.然后是更强大的catamorphisms，比如你正在使用的foldT，它可以利用树形结构.

P.S.: A note about terminology. Saying that a function is "like foldr but for trees" is ambiguous, as there are two well-known kinds of functions analogous to foldr. First, you have the methods of the Foldable class (cf. Benjamin Hodgson's answer), which flatten the tree into a list as they fold it, no matter what you do. Then there are the more powerful catamorphisms, such as the foldT you are using, which are able to make use of the tree structure.

这篇关于如何编写 a-> 类型的函数b->b->b 用于折叠一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！