treeFold函数中的递归 [英] Recursion in treeFold function

问题描述

我有树数据类型:

data Tree a = Node
  { rootLabel :: a,        -- label value
    subForest :: [Tree a]  -- zero or more child trees
  }

{-- Node (a) [] ..or...  Node (a1) [ Node (a2) [..], Node (a3) [..] ] --}

并且我需要编写treeFold函数，我认为我需要第一个函数来制作带有标签值的东西，第二个函数需要func1的两个结果，并得出一些最终结果，依此类推.我开始编写递归函数treeFold，为具有0个子树的最小Tree编写函数，但由于子树列表不为空，我无法完成我的函数.

and i need to write treeFold function, i think that i need first function that make something with label value and second function that takes two results of func1 and make some final result and so on. I start writing the recursion function treeFold, write function for minimal Tree with 0 child trees, but i can't finish my function for not empty list of child's trees.

我需要获取第一个孩子和孩子列表的其余部分，并从中创建新树，以便将此新树用于递归调用吗?

treeFold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
treeFold func1 _ (Node a1 []) = func1 a1   
treeFold func1 func2 (Node a1 [y]) = func2 (func1 a1) (treeFold func1 func2 y) 
treeFold func1 func2 (Node a1 [y1,y2]) = func2 (func1 a1) (treeFold func1 func2 (y1

推荐答案

不幸的是，术语折叠"有点重载.

Unfortunately, the term "fold" is a bit overloaded.

如果您希望fold函数捕获结构递归的一些概念，我认为对于这种类型的树，您不希望它接受两个参数(除了tree参数之外) ).

If you want your fold function to capture some notion of structural recursion, I don't think, for this type of trees, you want it to take two arguments (in addition to the tree argument).

这种折叠函数的类型来自于数据类型的构造函数的类型.

The type of such a fold function follows from the types of the constructors of your datatype.

在您的情况下，您的数据类型

In your case, your datatype

data Tree a = Node {rootLabel :: a, subForest :: [Tree a]}

只有一个构造函数:

Node :: a -> [Tree a] -> Tree a

因此，除了要折叠的树之外，您的fold函数将仅接受一个参数.通过用一个新的类型变量(例如b:

Hence, in addition to the tree you are folding, your fold function will only take one argument. The type of this argument is obtained by replacing all occurrences of Tree a in the constructor type by a fresh type variable, say b:

           a  -> [Tree a] -> Tree a

           |        |          |
           |        |          |
          \ /      \ /        \ /
           -        -          -

           a  -> [   b  ] ->   b

类型变量b也构成函数的返回类型.也就是说，你得到

The type variable b also constitutes the return type of your function. That is, you get

treeFold :: (a -> [b] -> b) -> Tree a -> b

实施

此功能的实现也遵循数据类型的定义.通过将fold函数递归应用于Node的Tree a类型的部分，可以获取必须传递给折叠的第一个参数的b类型的值.这里有些棘手的是，这些部分存储在列表中，因此您还需要映射到该列表:

Implementation

The implementation of this function follows from the definition of your datatype as well. You obtain the b-typed values that you have to pass to the first argument of your fold by recursively applying your fold function to the Tree a-typed parts of a Node. What is a bit tricky here is that those parts are stored in a list, so you also need to map over that list:

treeFold f (Node x xss) = f x (map (treeFold f) xss)

或者，可以说更好一些:

or, arguably a bit nicer:

treeFold f = h
  where
    h (Node x xss) = f x (map h xss)

关键思想是用函数f的应用程序替换树值中构造函数Node的所有应用程序，该函数作为第一个参数传递给treeFold.

The key idea is that you replace all applications of the constructor Node in your tree value by applications of the function f that is passed as the first argument to treeFold.

例如，您现在可以使用treeFold定义一个对树中所有元素求和的函数:

For example, you can now use treeFold to define a function that sums all elements in a tree:

total :: Num a => Tree a -> a
total =  treeFold (\n ns -> n + sum ns)

或仅返回一棵树包含多少元素的函数:

Or a function that simply returns how many elements a tree contains:

size :: Tree a -> Int
size =  treeFold (\_ ns -> 1 + sum ns)

减少量

另一种折叠形式是对数据结构进行(左或右偏置)归约的折叠.实际上，这些折叠通常需要另外两个参数:

Reductions

Another brand of folds are those that perform a (left- or right-biased) reduction of a data structure. Those folds indeed typically take two additional arguments:

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldl :: (b -> a -> b) -> b -> Tree a -> b

例如，可以根据辅助功能flatten

These functions you can for example implement in terms of an auxiliary function flatten

flatten :: Tree a       -> [a]
flatten    (Node x xss) =  x : concatMap flatten xss

并通过重用Prelude中的列表功能foldr和foldl:

and by reusing the list functions foldr and foldl from the Prelude:

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr    op               e =  foldr op e . flatten

treeFoldl :: (b -> a -> b) -> b -> Tree a -> b
treeFoldl    op               e =  foldl op e . flatten

例如:

total = treeFoldl (+) 0
size  = treeFoldr (const succ) 0

更多变化

根据要概括的概念，会有更多变化.例如，有人可能会争辩说，为了捕获结构递归，不需要/不希望在子森林上进行映射，而最终会出现类似

More variations

Depending on what concept you want to generalise, there are more variations. One could argue, for instance, that for capturing structural recursion, mapping over the subforest is not needed/desirable and wind up with something like

treeFold' :: (a -> c -> b) -> (c, b -> c -> c) -> Tree a -> b
treeFold' node (nil, cons) = h
  where
    h (Node x xss) = node x (foldr (cons . h) nil xss)

然后

total = treeFold' (+) (0, (+))
size  = treeFold' (const succ) (0, (+))

这篇关于treeFold函数中的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！