如何在不可变的树状结构上实现堆栈安全操作？

Question

我有一个不可变的树状结构类型：

type Data<A> = Empty | Node<A> | Both<A>

type Empty = { tag: Tag.Empty };
type Node<A> = { tag: Tag.Node, value: A };
type Both<A> = { tag: Tag.Both, left: Data<A>, right: Data<A> };

什么是实施 堆栈安全 操作（如 fold、map 甚至 flatMap 的良好起点结构？

Answer 1

让我们从数据构造函数开始。

// data Data a = Empty | Node a | Both (Data a) (Data a)
const Empty = { tag: "Empty" };
const Node = value => ({ tag: "Node", value });
const Both = left => right => ({ tag: "Both", left, right });

// data Cont a b = Left (Data a) (Cont a b) | Right b (Cont a b) | Done
const Left = rightQ => next => ({ tag: "Left", rightQ, next });
const Right = leftA => next => ({ tag: "Right", leftA, next });
const Done = { tag: "Done" };

// data Frame a b = Fold (Data a) (Cont a b) | Apply (Cont a b) b
const Fold = data => cont => ({ tag: true, data, cont });
const Apply = cont => result => ({ tag: false, cont, result });

接下来，我们定义一个堆栈安全的fold函数。

// fold :: (b -> b -> b) -> (a -> b) -> b -> Data a -> b
const fold = both => node => empty => data => {
    let frame = Fold(data)(Done);

    while (true) {
        const { data, cont, result } = frame;
        const { value, left, right } = data || {};
        const { leftA, rightQ, next } = cont;

        switch (frame.tag ? data.tag : cont.tag) {
        case "Empty":
            frame = Apply(cont)(empty);
            continue;
        case "Node":
            frame = Apply(cont)(node(value));
            continue;
        case "Both":
            frame = Fold(left)(Left(right)(cont));
            continue;
        case "Left":
            frame = Fold(rightQ)(Right(result)(next));
            continue;
        case "Right":
            frame = Apply(next)(both(leftA)(result));
            continue;
        case "Done":
            return result;
        }
    }
};

注意fold是一个结构折叠，但是我们可以用它来定义foldr这是一个遍历折叠

// id :: a -> a
const id = x => x;

// compose :: (b -> c) -> (a -> b) -> a -> c
const compose = g => f => x => g(f(x));

// flip :: (a -> b -> c) -> b -> a -> c
const flip = f => y => x => f(x)(y);

// foldr :: (a -> b -> b) -> b -> Data a -> b
const foldr = func => flip(fold(compose)(func)(id));

最后，我们可以用fold来定义map和flatMap。

// map :: (a -> b) -> Data a -> Data b
const map = func => fold(Both)(compose(Node)(func))(Empty);

// flatMap :: (Data a) -> (a -> Data b) -> Data b
const flatMap = flip(func => fold(Both)(func)(Empty));

Answer 2

如评论中所述，您显然需要一个 iterative tree-traversal algorithm 来执行一些标准的函数式编程操作，例如 map 和 fold（又名 reduce）。链接文章中提到的迭代算法涉及构建节点父节点的堆栈，或者维护从每个节点到其父节点的映射。

这是 Data<T> 上 fold 的可能（未经过广泛测试，所以要小心）实现，它在构建所需输出结构的同时维护从节点到其父节点的映射。请记住，肯定还有其他算法。我之所以选择这个，是因为它最清楚地表达了我设想如何穿过一棵树：

function fold<T, U>(inData: Data<T>, f: (acc: U, t: T) => U, init: U) {
  const parents: Map<Data<T>, Data<T> | undefined> = new Map();
  let cur: Data<T> | undefined = inData;
  let acc = init;
  while (cur) {
    if ((cur.tag === Tag.Both) && (!parents.has(cur.left))) {
      parents.set(cur.left, cur);
      cur = cur.left;
    } else if ((cur.tag === Tag.Both) && (!parents.has(cur.right))) {
      parents.set(cur.right, cur);
      cur = cur.right;
    } else {
      if (cur.tag === Tag.Node) {
        acc = f(acc, cur.value);
      }
      cur = parents.get(cur);
    }
  }
  return acc;
}

如果您当前的节点是 Both 并且您还没有处理 left 节点，请将当前节点作为 left 添加到他的 parents 映射中节点的父节点，然后沿着树向左走。否则，如果该节点是 Both 并且您尚未处理 right 节点，请执行相同的操作但向右。否则，您正在处理一个 Empty 或 Node 节点，或者一个 Both 节点，其 left 和 right 节点已经被处理......这意味着你然后可以处理当前节点的输出，然后返回到父节点。最终你会尝试走到树根的父节点，你就完成了。

使这个 fold 的部分是我们在处理 Node 节点时运行累加器回调。同样重要的是要注意 fold 通常取决于遍历的顺序（例如，对于列表来说，左折和右折是不同的），所以上面的实现可能不是你想的那个（你想要预购？按顺序？post-order？广度优先？其他？）。

这是一个类似的 map 实现：

function map<T, U>(inData: Data<T>, f: (t: T) => U) {
  const parents: Map<Data<T>, Data<T> | undefined> = new Map();
  const mapped: Map<Data<T>, Data<U>> = new Map();
  let cur: Data<T> | undefined = inData;
  while (cur) {
    if ((cur.tag === Tag.Both) && (!parents.has(cur.left))) {
      parents.set(cur.left, cur);
      cur = cur.left;
    } else if ((cur.tag === Tag.Both) && (!parents.has(cur.right))) {
      parents.set(cur.right, cur);
      cur = cur.right;
    } else {
      mapped.set(cur,
        cur.tag === Tag.Both ? ({
          tag: Tag.Both,
          left: mapped.get(cur.left)!,
          right: mapped.get(cur.right)!
        }) : cur.tag === Tag.Empty ? ({
          tag: Tag.Empty
        }) : ({
          tag: Tag.Node, value: f(cur.value)
        })
      );
      cur = parents.get(cur);
    }
  }
  return mapped.get(inData)!;
}

与fold类似，但输出处理不同。为 Both 构建输出节点涉及使用已经为每个子树构建的输出节点，因此此实现还存储了一个从输入节点到输出节点的 mapped 映射，以便稍后可以检索。

我不会介绍 flatMap()，但它与 map 类似，除了 Node 输入的输出节点是由回调函数直接生成的，而不是需要被建造。您可以验证这些是否为合理的树做了合理的事情（底部的 Playground Link 有一些示例）。

Playground link to code

如何在不可变的树状结构上实现堆栈安全操作？

How to implement stack safe operations on an immutable tree-like structure?

javascript

typescript

functional-programming

tree

immutability