javascript - 为什么我需要一个列表折叠来实际解构具有这种树变态的树？

Question

catamorphism 可以解构一个值

[1,2,3].reduce((acc, x) => acc + x, 0); // 6

或维护结构并像底层类型的身份一样行事：

[1,2,3].reduce((acc, x) => acc.concat([x]), []); // [1,2,3]

对于列表（或 JS 中的数组），变态和折叠（可折叠容器的）重合。

但是，对于树木，它们不会：

const treeCata = f => ([x, xs]) =>
  f(x) (arrMap(treeCata(f)) (xs));

const arrMap = f => xs =>
  xs.map((x, i) => f(x, i));

const arrFold = f => acc => xs =>
  xs.reduce((acc, x) => f(acc) (x), acc);

const log = x => (console.log(x), x);

const Node = (x, xs) => ([x, xs]);
const Node_ = x => xs => ([x, xs]);

const tree = Node(1, [
  Node(2, [
    Node(3, []),
    Node(4, [])
  ]),
  Node(5, [])
]);

const foo = treeCata(Node_) (tree);

const bar = treeCata(x => xs => x + arrFold(y => z => y + z) (0) (xs)) (tree);

log(foo);
log(bar);

作为身份的角色按预期工作。然而，解构涉及更多。事实上，我需要一个列表折叠来执行它。我实际上可以看到有一层解构，因为否则列表折叠对于非线性树来说是不够的。但是仍然不得不使用另一个折叠似乎很奇怪。

我只能猜测这种行为与使用的变质的简洁定义有关。它只考虑产品的单个案例Tree a = Node a [Tree a]。如果我完全接受类型和区分Node/Array构造函数和空数组情况的代数结构，也许会更有希望。

但这是否意味着treeCata不是适当的变态？它缺少什么？

标签： javascriptrecursionfunctional-programmingtreecatamorphism

Answer 1

我认为你的很好，对于你定义treeCata的类型来说是一个有效的变态。Tree a = Node a [Tree a]底层函子是TreeF a b = Node a [b]所有代数都必须处理的结构。catamorphism 只为您处理递归，而不是您的节点子节点的列表结构。如果是这样，它将对您隐藏信息，并且您将无法使用初始代数重建树。

当然，您可能想在TreeF. 由于您的节点不为空，一个特别有趣的可能是

// fold :: Semigroup a => TreeF a a -> a
// fold1 :: (a -> a -> a) -> TreeF a a -> a
const fold1 = f => ([x, xs]) => arrFold(f)(x)(xs)

有了这个，您确实可以将 sum 函数定义为

const treeSum = treeCata(fold1((x, y) => x+y));

正如@Aadit 所说，这是让我们从结构折叠中推导出遍历折叠的函数。

const treeCata = f => ([x, xs]) =>
  f([x, arrMap(treeCata(f))(xs)]);

const arrMap = f => xs =>
  xs.map((x, i) => f(x, i));

const arrFold = f => acc => xs =>
  xs.reduce((acc, x) => f(acc) (x), acc);

const treeF_fold1 = f => ([x, xs]) => arrFold(f)(x)(xs);

const treeSum = treeCata(treeF_fold1(x => y => x+y));

const Node = (x, xs) => ([x, xs]);
const Node_ = x => xs => ([x, xs]);

const tree = Node(1, [
  Node(2, [
    Node(3, []),
    Node(4, [])
  ]),
  Node(5, [])
]);

console.log(treeCata(Node_)(tree));
console.log(treeSum(tree));