4

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不是适当的变态？它缺少什么？

4

2 回答 2

2

我认为你的很好，对于你定义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));

于 2020-12-05T12:11:56.443 回答
1

褶皱有两种。

  1. 用于对数据结构执行归纳的结构折叠。
  2. 遍历折叠，用于遍历和汇总数据结构的元素。

结构折叠直观地将数据结构的每个数据构造函数替换为给定函数。

Node_(1)([
    Node_(2)([
        Node_(3)([]),
        Node_(4)([])
    ]),
    Node_(5)([])
])

/*
          |
          | treeCata(fNode)
          v
*/

fNode(1)([
    fNode(2)([
        fNode(3)([]),
        fNode(4)([])
    ]),
    fNode(5)([])
])

但是，遍历折叠会遍历数据结构的各个元素并对其进行汇总。

Node_(1)([
    Node_(2)([
        Node_(3)([]),
        Node_(4)([])
    ]),
    Node_(5)([])
])

/*
          |
          | foldrTree(add)(0)
          v
*/

[1, 2, 3, 4, 5].reduceRight(add, 0);

在 Haskell 中，Foldable类型类实现了遍历折叠。Foldable 类型类的最小完整定义是foldr方法。所以，让我们为树实现它。

// Node : a -> [Tree a] -> Tree a
const Node_ = value => children => ({ value, children });

// treeCata : (a -> [b] -> b) -> Tree a -> b
const treeCata = fNode => function fold({ value, children }) {
    return fNode(value)(children.map(fold));
};

// treeElems : Tree a -> [a]
const treeElems = treeCata(x => xss => [x].concat(...xss));

// foldrTree : ((b, a) -> b) -> b -> Tree a -> b
const foldrTree = cons => empty => tree =>
    treeElems(tree).reduceRight(cons, empty);

// add : (Number, Number) -> Number
const add = (x, y) => x + y;

// tree : Tree Number
const tree = Node_(1)([
    Node_(2)([
        Node_(3)([]),
        Node_(4)([])
    ]),
    Node_(5)([])
]);

console.log(foldrTree(add)(0)(tree));

经验法则：

  1. 当您想对数据结构执行归纳时，请使用结构折叠。
  2. 当您想要总结数据结构的元素时，请使用遍历折叠。
于 2020-12-05T10:22:24.223 回答