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

我们可以通过折叠成 endofunctions 从数据类型-跟随树形折叠中恢复线性、累加器传递折叠，如下所示：

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 作为 'zero' 元素 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

Answer 2

这是您自己想出的解决方案。

我们有

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

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

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

所以给定 g 和 z 这个函数通过将 t 的子树变成 Tree a 值变成 b 值=20=]s 并通过 g.

将它们与树的 a 组合

我们可以 map 使用 foldTree 覆盖这些树吗？是：

mapTree :: (a -> c) -> Tree a -> Tree c
mapTree f t = foldTree g z t
  where
  -- we need to create a Node with the mapped element inside it
  -- already having the transformed sub-trees. Well, 
  -- creating Tree values is the job of that type's data constructors:
  g lt a rt = Node lt (f a) rt      -- f is applied to the element `a`
  -- and all leaves are transformed into the same value, which is:
  z = Leaf

所以现在我们有 mapTree (f :: a -> c) :: Tree a -> Tree c。这对我们有什么帮助？

我们想要什么？我们要

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
-- i.e.
foldTreeR (cons :: a -> r -> r) (nil :: r) :: Tree a -> r

所以我们有 cons，这样 cons (x :: a) :: r -> r。

如果我们 将此 cons 映射到树上会怎样？类型 a -> r -> r 实际上是 a -> (r -> r)，实际上我们刚刚看到 cons 将 (x :: a) 转换为 r -> r（ 阅读它：将值 x 或类型 a 为类型 r -> r):

mapTree (cons :: a -> r -> r) :: Tree a -> Tree (r -> r)

我们为什么要那个？我们可以用现在树节点中的所有 r -> r 函数做什么？好吧，我们可以通过中序遍历将树变成其节点中值的列表：

inorder :: Tree d -> [d]
inorder t = foldTree (\l a r -> l ++ a : r) [] t

所以我们可以

inorder . mapTree (cons :: a -> r -> r) :: [r -> r]
          -----------------
          Tree a -> Tree (r -> r)
--------
Tree (r->r) -> [r->r]

我们可以组合该列表中的所有这些函数，线性，以安排从右到左的结果传递是的操作...右折！

foldTreeR_ :: (a -> r -> r) -> r -> Tree a -> r
foldTreeR_ cons z t = foldr ($) z (inorder $ mapTree cons t)
           -- or, equivalently,
           --         foldr (.) id (inorder $ mapTree cons t) z

就是这样。

如果我们内联所有内容并简化生成的定义，我们就会得到另一个答案中的那个。

左折叠也一样。试试吧。

Haskell 棵树上的褶皱变化

Variations of folds on Haskell Trees

binary-tree

haskell

functional-programming

fold