haskell - Haskell 树上折叠的变化

Question

给定一棵树定义为:

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 的等效项:

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

我认为这些将相当简单，因为它们的定义非常精确地模仿 foldr 和 foldl 的定义。我假设我所要做的就是以类似的方式插入类似的值，所以我会编写一个匿名函数，一个带有我的树的基本状态和需要处理的树的累加器。 lambda 函数必须根据正在进行的折叠类型而变化。

这是我的想法:

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

我不太确定在这种情况下应该如何传递原始树。

看起来左边的折叠只是相同的变体，其中 lambda 函数中的值被重新排序并以不同的方式进行评估。

有人可以帮助我了解如何在这里找到解决方案吗？

Answer 1

我们可以通过折叠成内函数来从遵循数据类型的树形折叠中恢复线性的、累加器传递的折叠，如下所示:

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

<小时/>

更详细的解释:

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

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

(.) :: (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]的树，右侧折叠将该树变成组合

(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，对整个链没有影响，因为

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

所以

id . f = f = f . id

即id 充当“零”元素 w.r.t.函数组合操作，就像 0 与 + 操作一样(顺便说一下，这被称为'monoid'由 . 和 id 组成，或由 0 和 + 组成)。

<小时/>

以下是我们为树创建有序遍历列表的方法:

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

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

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

该树的右侧折叠将被创建为

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