gpt4 book ai didi

javascript - 左关联二叉树折叠

转载 作者:行者123 更新时间:2023-12-05 09:29:59 24 4
gpt4 key购买 nike

使用正常的右关联树折叠,我可以通过重新排列提供的函数 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);

最佳答案

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

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

关于javascript - 左关联二叉树折叠,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70117412/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com