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

作为身份的 Angular 色按预期工作。然而，解构涉及更多。事实上，我需要一个列表折叠来执行它。我实际上可以看到有一层解构，因为否则列表折叠对于非线性树来说是不够的。但是仍然不得不使用另一个折叠似乎很奇怪。
我只能猜测这种行为与使用的变质的简洁定义有关。产品Tree a = Node a [Tree a]只考虑一个案例.如果我完全接受类型的代数结构并区分Node，也许会更有希望。/Array构造函数和空数组的情况。
但这是否意味着 treeCata是不是一个适当的变态？它缺少什么？

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