左結合二叉樹折疊-有解無憂

使用正常的右關聯樹折疊，我可以通過重新排列提供的函式中的串聯來定義前序/中序/后序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);

uj5u.com熱心網友回復：

使用正常的右關聯樹折疊，我可以通過重新排列提供的函式中的串聯來定義前序/中序/后序 f

你在那里定義的不是一個foldR函式。它實際上是一個catamorphism您的樹狀結構（也看到這個答案），并具有正是這種好處是可以實作與任何事。您可以實作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);

沒有 catamorphism，實作應該是這樣的：

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

這些都沒有前序或后序變體，關于樹形的資訊會丟失到減少函式中。線性折疊總是有序的，只是左右變體之間的關聯性不同。

uj5u.com熱心網友回復：

妄想

鑒于用戶提供的各種折疊功能 -

遍歷	用戶提供 `f`
預購	`l => v => r => [v].concat(l).concat(r)`
為了	`l => v => r => l.concat([v]).concat(r)`
后序	`l => v => r => l.concat(r).concat([v])`

如果我們希望我們的愿望成真，我們可以推斷出l，并r 必須已經是陣列，否則Array.prototype.concat不可用。

鑒于你的樹 -

這些折疊函式的本質是將f復合節點值展平為單個陣列值。在第一個節點之后，無論f選擇何種遍歷，輸出都是[0]，現在是下一個節點的累加器 -

分叉蓄能器

               f([], 0, [])
             /              \
            /                \
    f([0], 1, [0])     f([0], 2, [0])
    /            \    /              \
   ...           ... ...             ...

在這里，我們應該已經能夠看到一個問題。累加器已變平，“左”和“右”與零相關的位置丟失了資訊。更糟糕的是，累加器已經分叉，我們需要一些合并解決方案來協調這種分裂。合并解決方案如何在不強制執行某種排序以確保其預期結果的情況下作業？

有序折疊

如果你說，“不，我們不會分叉累加器”，而是將呼叫排序f，我們是否先折疊左分支？我們是否先折疊正確的分支？

              f(..., 0, ...)
             /              \
            /                \
    f(..., 1,          f(..., 2, ...))
    /                                \
   ?               ???                ?

即使我們可以設法對進行這些有效呼叫f，首先選擇左分支或右分支也是排序。

元回圈評估器

所以我們現在已經兩次陷入死胡同了。好的，讓我們回到開始，假設我們可以改變用戶提供的遍歷 -

遍歷	用戶提供 `f`
預購	`l => v => r => [v, l, r]`
為了	`l => v => r => [l, v, r]`
后序	`l => v => r => [l, r, v]`

在這種結構中，l且r不再限制為陣列，而是他們可能是任何東西。它們可以是物件、識別符號或其他型別的哨兵，可以treeFoldL識別并用于指導其不斷增長的計算程序。如你所知，只要有足夠的工程，我們就可以讓它做任何我們想做的事——

例如，考慮這個inorder遍歷 -

[ L, 0, R ]
[ ...[L, 1, R], 0, R ]
[ L, 1, R, 0, R ]
[ ...[L, 4, R], 1, R, 0, R ]
[ L, 4, R, 1, R, 0, R ]
[ ...[], 4, R, 1, R, 0, R ]
[ 4, R, 1, R, 0, R ]
[ 4, ...[], 1, R, 0, R ]
[ 4, 1, R, 0, R ]
[ 4, 1, ...[L, 5, R], 0, R ]
[ 4, 1, L, 5, R, 0, R ]
[ 4, 1, ...[], 5, R, 0, R ]
[ 4, 1, 5, ...[], 0, R ]
[ 4, 1, 5, 0, R ]
[ 4, 1, 5, 0, ...[L, 2, R] ]
[ 4, 1, 5, 0, L, 2, R ]
[ 4, 1, 5, 0, ...[], 2, R ]
[ 4, 1, 5, 0, 2, R ]
[ 4, 1, 5, 0, 2, ...[L, 3, R] ]
[ 4, 1, 5, 0, 2, L, 3, R ]
[ 4, 1, 5, 0, 2, ...[], 3, R ]
[ 4, 1, 5, 0, 2, 3, R ]
[ 4, 1, 5, 0, 2, 3, ...[] ]
[ 4, 1, 5, 0, 2, 3 ]

為了保持這種通用性，這需要一個ordering函式與折疊函式分開提供f，現在是一個熟悉的 2-arity 介面 -

const treeFoldl = ordering => f => init => t =>
  // ...

const inorder =
  treeFoldL (l => v => r => [l, v, r])

const concat = a => b =>
  a.concat(b)

const toArray =
  inorder (concat) ([])

toArray (myTree) // => [...]

const toString =
  inorder (concat) ("")

toString (myTree) // => "..."

回到地球

So you could go through the trouble and write treeFoldl in such a way however it overlooks the most obvious implementation, imo. From where I see it, there is no treeFoldl and treeFoldr, instead there is only preorder, inorder, postorder, levelorder, whateverorder. For purposes of associativity, there is foldl and foldr -

Here's a generic foldl that accepts any iterable, it -

const foldl = f => init => it => {
  let acc = init
  for (const v of it)
    acc = f(acc, v)
  return acc
}

And some possible traversals for your binary tree, here written as generators but you can use whatever implementation you like, stack-safe or otherwise -

function *preorder(t) {
  if (t?.[TAG] == "Leaf") return
  yield t.v
  yield *preorder(t.l)
  yield *preorder(t.r)
}

function *inorder(t) {
  if (t?.[TAG] == "Leaf") return
  yield *inorder(t.l)
  yield t.v
  yield *inorder(t.r)
}

function *postorder(t) {
  if (t?.[TAG] == "Leaf") return
  yield *postorder(t.l)
  yield *postorder(t.r)
  yield t.v
}

function *levelorder(t) {
  // pop quiz: 
  // how would you write levelorder using your original interface?
  // ...
}

Instead of tangling left/right associativity in your traversals, these things are kept separate and remain a choice of the caller. Using them is straightforward -

// left
foldl (concat) ([]) (preorder(t)) // => [...]
foldl (concat) ([]) (inorder(t))  // => [...]
foldl (concat) ([]) (postorder(t)) // => [...]

// or right
foldr (concat) ([]) (preorder(t)) // => [...]
foldr (concat) ([]) (inorder(t))  // => [...]
foldr (concat) ([]) (postorder(t)) // => [...]

// left
foldl (concat) ("") (preorder(t)) // => "..."
foldl (concat) ("") (inorder(t))  // => "..."
foldl (concat) ("") (postorder(t)) // => "..."

// or right
foldr (concat) ("") (preorder(t)) // => "..."
foldr (concat) ("") (inorder(t))  // => "..."
foldr (concat) ("") (postorder(t)) // => "..."

關注點分離的優點很多。foldl并且foldr適用于任何可排序的資料型別。它是該資料型別的域來指定它可以被排序的方式。

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/371676.html

標籤：javascript 递归函数式编程二叉树

上一篇：使用其根將樹存盤為字典

下一篇：在R中使用遞回函式[錯誤C堆疊使用太接近限制]