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

问题描述

一些背景：我在Haskell中有以下类型的foldT函数（比如foldr但树）。

  foldT ::（a  - > b  - > b  - > b） - > b  - >树a  - > b 
  

这个foldT仅将类型（a - > b - > b - > b）作为输入函数。

我试图找到一种方法将我的树转换为一个列表，并且不能找出一种方法来使我的追加函数采取形式（a - > b→b→b）。

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

  append xyz = append x：y：z 
  

任何帮助将不胜感激。

谢谢！

解决方案

，我会假定你的树是...

 数据树a =叶|节点a（Tree a）（Tree a）
  

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

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

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

  foldT ::（a  - > b  - > b  - > b） - > b  - >树a  - > b 
  

您想要将它变成一个列表，所以函数的结果类型必须为<$
$ b

  treeToList :: Tree a  - > [a] 
  

这给了我们一个关于如何继续的好主意：

  treeToList t = foldT fzt 
  

With：

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

现在，继续争论。 z 是代替无值 Leaf s的内容，所以它必须是 [] 。至于 f ，它必须将从左右分支创建的子列表与直接在 Node 中的值相结合。假设按顺序遍历，我们有：

pre code> treeToList t = foldT（\ xlr - > l ++ x： r）[] t

或者，没有提及 t ：

  treeToList = foldT（\ xlr  - > l ++ x：r）[] 
  

就是这样。一个警告是反复使用左嵌套的（++）（在这种情况下会发生 foldT > walking递归地沿着分支）可能变得相当低效。在你关心性能的情况下，值得考虑实现连接函数的其他方式，比如差异列表。

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

>

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 

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

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 

Any help would be appreciated.

Thank you!

解决方案

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

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

... 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

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

With:

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

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

Or, without mentioning t:

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

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.: 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-&gt;的函数b - &gt; b - &gt; b折叠树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！