Haskell树上的褶皱变化 [英] Variations of folds on Haskell Trees

问题描述

给出一棵定义为的树:

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

我要使用该功能:

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ b Leaf         = b
foldTree f b (Node lt x rt) = f (foldTree f b lt) x (foldTree f b rt)

为了能够创建普通foldr和foldl的等价物，如下所示:

To be able to create equivalents of the normal foldr and foldl as:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeL :: (b -> a -> b) -> b -> Tree a -> b

我认为这些定义非常简单，因为它们的定义几乎完全模仿了foldr和foldl的定义.我假设我将要做的就是以类似的方式类似地插入值，因此我将编写一个匿名函数，一个具有我的树的基本状态以及需要处理的树的累加器. lambda函数必须根据完成的折叠类型而有所不同.

I thought these would be fairly straightforward since their definitions mimic those of foldr and foldl pretty much exactly. I assumed that all I would have to do would be plug in the values analogously in a similar manner so I would write an anonymous function, an accumulator with the base state of my tree and the tree that needs to be processed. The lambda function would have to vary based on the type of fold being done.

这是我想出的:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeR f acc t =  foldTree (\x acc -> f x acc) acc t

我得到了错误:

Couldn't match type ‘a’ with ‘a -> b’ 
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foldTreeR :: forall a b. (a -> b -> b) -> b -> Tree a -> b
        at Folds.hs:294:14
      Expected type: Tree (a -> b)
        Actual type: Tree a

在这种情况下，我不确定如何传递原始树.

I am not really sure how I should pass in the original tree in this case.

似乎左折只是对lambda函数中的值进行了重新排序以及对其进行了不同计算而产生的相同变化.

It seems the left fold will just be a variation of the same with the values within the lambda function re-ordered as well as evaluated differently.

有人可以帮助我了解如何在此处找到解决方案吗?

Could someone help me understand how a solution can be reached here?

推荐答案

我们可以通过折叠成 endofunctions 从数据类型跟随的树形折叠中恢复线性的，累加器传递的折叠这个:

We can recover the linear, accumulator-passing folds from the data type-following tree-shaped folds by folding into endofunctions, like this:

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

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

foldTreeR :: (a -> r -> r) -> r -> Tree a -> r
foldTreeR cons z t = foldTree g id t z           -- b ~ r -> r
  where
  g lt a rt = lt . cons a . rt 

左折:

foldTreeL :: (acc -> a -> acc) -> acc -> Tree a -> acc
foldTreeL conj z t = foldTree g id t z           -- b ~ acc -> acc
  where
  g lt a rt = rt . flip conj a . lt

---

更详细的解释:

---

More detailed explanations:

cons a和flip conj a都具有r -> r类型(或acc -> acc，这是相同的).这是参数类型和结果相同的函数类型.

Both cons a and flip conj a have type r -> r (or acc -> acc, which is the same). This is the type of functions with the types of argument and result being the same.

这类功能称为内在功能， endo 表示其域和共域(箭头右侧和左侧的类型)的相同性.这样，它们很容易 compose :可以参与(.)操作，即函数组合，其组合的结果与操作数的类型相同:

Such functions are known as endofunctions, endo indicative of the sameness of their domain and codomain (the types on the right and left side of the arrow). As such, they compose easily: can participate in (.) operation, i.e. function composition, with the result of composition having the same type as the types of operands:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

-- and for endofunctions,
-- ((f :: r -> r) . (g :: r -> r)) :: r -> r

对于顺序遍历为[a,b,c,...,n]的树，右折将其变成合成

For a tree with an in-order traversal of [a,b,c,...,n], the right fold turns that tree into a composition

(cons a . cons b . cons c . ..... . cons n) z

-- which is the same as
-- cons a (cons b (cons c ... (cons n z) ... ))

并且左折将其变成

(conj' n . ..... . conj' c . conj' b . conj' a) z

其中

conj' a acc = flip conj a acc = conj acc a     -- by definition of `flip`

-- so the above composition chain is the same as
-- conj (... (conj (conj (conj z a) b) c) ...) n

在该链上散布了一些id，每个Leaf都变成了id，对整个链没有影响，因为

with some ids sprinkled around that chain, each Leaf being turned into an id, having no effect on the whole chain, because

(id . f) x = id (f x) = f x = f (id x) = (f . id) x

如此

id . f = f = f . id

即id用作零"元素就像0与+操作一样(顺便说一下，这是由.和id组成的'monoid'，或0和+).

i.e. id serving as a 'zero' element w.r.t. to the function composition operation, just like 0 does with the + operation (this, by the way, is referred to as 'monoid' being formed by . and id, or by 0 and +).

这是我们如何为树创建该顺序遍历列表的方法:

Here's how we'd create that in-order traversal list for a tree:

inorder :: Tree a -> [a]
inorder t = foldTree g [] t
  where
  g lt a rt = lt ++ [a] ++ rt

因此，列表[a,b,...,n]实际上是创建为

So the list [a,b,...,n] is actually created as

[] ++ [a] ++ [] ++ [b] ++ [] ++ ... ++ [n] ++ []

，该树的右折将被创建为

and the right fold of that tree would be created as

(id . cons a . id . cons b . id . .... . cons n . id) z

这篇关于Haskell树上的褶皱变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！