使用折叠映射任意 n 元树

Question

我想要一些通用工具来处理树木。我正在使用 JavaScript，所以我几乎没有什么可以强加的，而且我正在使用我无法更改的现有数据结构。我设法定义了以下内容：

reduceTree :: (T a -> [T a]) -> (b -> T a -> b) -> b -> T a -> b
reduceTree(getChildren, f, accumulator, tree)

（我使用 Haskell 类型签名，因为它们更易于阅读）

这个getChildren函数是必需的，因为我的树是任意的，我不知道它是如何构造的。

reduceTree 效果很好。但我也想有一个 mapTree 函数，最好重用我的 reduceTree 函数，但我被卡住了。有些不对劲，但我不知道是什么。

编辑

我的reduceTree实现：

export function reduceTree(getChildren, f, accumulator, tree) {
  const children = getChildren(tree);
  if (!children || children.length === 0) {
    return f(accumulator, tree)
  } else {
    const childrenResult = children.reduce(
      (accumulator, subTree) => reduceTree(getChildren, f, accumulator, subTree),
      accumulator
    );
    return f(childrenResult, tree)
  }
}

它已经过测试并且有效。

（我的伪 Haskell 实现我曾经 construct/prove 上面的 javascript：

reduceTree f a (Node val []) = f a val
reduceTree f a (Node val xs) = f (fold (reduceTree f) acc) val

)

Answer 1

我看到你的树数据结构定义如下：

data T a = Node a [T a]

如果是这种情况，那么树数据结构的折叠将是：

reduceTree :: (a -> [b] -> b) -> T a -> b
reduceTree f = let g (Node a xs) = f a (map g xs) in g

您现在可以使用 reduceTree 定义 mapTree，如下所示：

mapTree :: (a -> b) -> T a -> T b
mapTree f = reduceTree (Node . f)

全部转换为JavaScript:

const Node = (a, xs) => ({a, xs});

const reduceTree = (f, node) => {
    const g = node => f(node.a, node.xs.map(g));
    return g(node);
};

const mapTree = (f, node) => reduceTree((a, xs) => Node(f(a), xs), node);

const tree = Node(2, [ Node(3, [ Node(11, [])
                               , Node(13, []) ])
                     , Node(5, [])
                     , Node(7, [ Node(17, [])
                               , Node(19, []) ]) ]);

console.log(mapTree(x => 2 * x, tree));

希望对您有所帮助。

Answer 2

TL;DR：您的伪代码已损坏。一种修复方法是

reduceTree :: (b -> a -> b) -> b -> T a -> b
reduceTree f acc (Node val []) = f acc val
reduceTree f acc (Node val ts) = 
    Data.List.foldl (\acc tree -> reduceTree f acc tree) (f acc val) ts

这意味着你的 Javascript 应该是

export function reduceTree(getChildren, f, accumulator, tree) {
  const children = getChildren(tree);
  if (!children || children.length === 0) {
    return f(accumulator, tree)
  } else {
    const childrenResult = children.reduce(
      (accumulator, subTree) => reduceTree(getChildren, f, accumulator, subTree),
      f(accumulator,tree)  // referring to `tree` only for its stored node value, yes?
    );
    return childrenResult;
  }
}

大概 Javascript 在列表中的 reduce 是 left 折叠（根据维基百科，它是这样）。

进行前序树遍历，相当于这个post底部的tfoldl函数。虽然用它实现 map 并不完全有效，

tmap f t = reduceTree (\acc val -> Node (f val) ???) ??? t

因为 Node :: a -> [T a] -> T a 的类型不正确，无法使其适合上面的 reducer 类型，b -> a -> b（它需要类型 a -> [b] -> b）。

这是因为这种线性折叠本质上是将结构拉平，将其视为线性序列。

接下来是一些无关的阐述。

Haskellhas it the exact same way as the reduceTree function in 。

John Hughes 在他著名的论文 "Why Functional Programming Matters" 中也有几乎相同的方法，因为

foldTree :: (a -> b -> r) -> (r -> b -> b) -> b -> Tree a -> r 
foldTree f g z (Node x t) = f x . foldr g z . map (foldTree f g z) $ t

对于 "reduce tree"，他使用了一个等效但更冗长的公式，他称之为 redtree。它认为

foldTree f g z = reduceTree (\a rs -> f a (foldr g z rs))

所以两者相当。那么，

map h = reduceTree (Node . h) 
      = reduceTree (\a rs -> Node (h a) rs) 
      = foldTree (Node . h) (:) []

缺少 "zero" 即初始累加器值来自数据定义中缺少第二个子句，data T a = Node a [T a] 而不是列表的 List a = Nil | Cons a (List a)。

后者的 fold reducer 函数采用 Nil 或 Cons a r 到 r，因此它必须具有 "zero"，即提供给它的默认值；对于前者，它需要 Node a [r] 到 r，所以没有 Nil 的情况需要处理（参见 recursion-schemes）。

此类型正在关注 from user Bergi in the comments, the Haskell package containers defines a Foldable instance，

data T a = Node a [T a]

等同于 foldr（为方便起见，使用翻转参数），

tfoldr :: (a -> b -> b) -> T a -> b -> b 
tfoldr f (Node x ts) z = f x $ Data.List.foldr ($) z [tfoldr f t | t <- ts]

确实通过状态/累加器进行线程化！也可以写成

tfoldr :: (a -> b -> b) -> T a -> b -> b 
tfoldr f (Node x ts) z = f x . Data.List.foldr (.) id [tfoldr f t | t <- ts] $ z

以您更容易实施的为准。这是实现 post-order 树遍历；对于通常的预序遍历使用

tfoldl :: (a -> b -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f x z
                 -- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f x z))) ...)

其中(f >>> g) x = g (f x)，或

tfoldl :: (b -> a -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f z x
                 -- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f z x))) ...)

相当于此 post 开头的代码，直至参数的顺序。

另请参阅：

使用折叠映射任意 n 元树

Map an arbitrary n-ary Tree with fold

javascript

tree

haskell

functional-programming

fold

编辑