javascript - 左关联二叉树折叠

Question

使用正常的右关联树折叠，我可以通过重新排列提供的函数 f 中的串联来定义前序/中序/后序:

const treeFoldr = f => acc => function go(t) {
  if (t[TAG] === "Leaf") return acc;
  else return f(t.v) (go(t.l)) (go(t.r));
};

const TAG = Symbol.toStringTag;

const N = (l, v, r) => ({[TAG]: "Node", l, v, r});
const L = {[TAG]: "Leaf"};

const foo = N(
  N(
    N(L, 4, L),
    1,
    N(L, 5, L)
  ),
  0,
  N(
    L,
    2,
    N(L, 3, L)
  )
);

const r1 = treeFoldr(
  x => acc1 => acc2 => {return [x].concat(acc1).concat(acc2)}) ([]) (foo); // pre-order

const r2 = treeFoldr(
  x => acc1 => acc2 => {return acc1.concat([x]).concat(acc2)}) ([]) (foo); // in-order
  
const r3 = treeFoldr(
  x => acc1 => acc2 => {return acc1.concat(acc2).concat([x])}) ([]) (foo); // post-order

console.log(r2); // in-order [4,1,5,0,2,3]

现在我想对于左关联折叠也应该可以实现同样的效果，其中 f 的结果将传递到下一个递归 go 调用。但我能想到的只是这个硬编码的预购折叠:

treeFoldl = f => acc => function go(t) {
  if (t[TAG] === "Leaf") return acc;
  
  else {
    acc = f(acc) (t.v);
    acc = go(t.l);
    return go(t.r);
  }
};

为了获得所需的设计，我必须以某种方式合并两个累加器(因为 f 的签名)和左/右节点的递归调用，但我没有一个线索如何。

这可能很容易，但我就是只见树木不见森林..

[编辑]

根据评论中的要求，这里是 treeFoldl 的纯版本:

const treeFoldl = f => init => t => function go(acc, u) {
  if (u[TAG] === "Leaf") return acc;
  
  else {
    const acc_ = go(f(acc) (u.v), u.l);
    return go(acc_,   u.r);
  }
} (init, t);

Answer 1

With the normal right associative tree fold I can define pre-/in-/post-order just by rearranging the concatenation in the supplied function f

您定义的不是 foldR 函数。它实际上是一个catamorphism对于您的树结构(另请参阅 this answer )，并且具有您可以用它实现任何内容的优势。您可以实现fmap，构建相同形状的新树。或者您可以实现线性左折叠和右折叠:

// cata :: ((b, a, b) -> b), () -> b) -> Tree a -> b
const cata = (onNode, onLeaf) => tree => {
  if (t[TAG] === "Leaf")
    return onLeaf();
  else
    return onNode(
      cata(onNode, onLeaf)(t.l),
      t.v,
      cata(onNode, onLeaf)(t.r)
    );
};

// foldR :: ((a, b) -> b) -> b -> Tree a -> b
const foldR = f => init => t => cata(
  (l, v, r) => acc => l(f(v, r(acc)),
  () => acc => acc
)(t)(init);

// foldL :: ((b, a) -> b) -> b -> Tree a -> b
const foldL = f => init => t => cata(
  (l, v, r) => acc => r(f(l(acc), v),
  () => acc => acc
)(t)(init);

如果没有变形，实现应该如下所示:

// foldR :: ((a, b) -> b) -> b -> Tree a -> b
const foldR = f => init => t => {
  if (t[TAG] === "Leaf")
    return init;
  else {
    const acc1 = foldR(f)(init)(t.r);
    const acc2 = f(t.v, acc1);
    return foldR(f)(acc2)(t.l);
  }
};

// foldL :: ((b, a) -> b) -> b -> Tree a -> b
const foldL = f => init => t => {
  if (t[TAG] === "Leaf")
    return init;
  else {
    const acc1 = foldL(f)(init)(t.l);
    const acc2 = f(acc1, t.v);
    return foldL(f)(acc2)(t.r);
  }
};

它们都没有前序或后序变体，关于树形状的信息在缩减函数中丢失。线性折叠始终是有序的，只是左右变体之间的关联性不同。