javascript - 使用折叠映射任意 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)
  }
}

它已经过测试并且有效。

(我用来构造/证明上面的 javascript 的伪 Haskell 实现:

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));

希望对您有所帮助。