如何在严格评估的语言中实现保护递归？

Question

我List在Javascript中实现了一个Scott编码类型以及一个append模仿Semigroup类型类的重载函数.

append工作得很好,但对于大型列表,它会炸掉堆栈.这是我实施的决定性部分:

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));

通常我使用蹦床来避免不断增长的堆栈,但这预示着尾递归,因此在这种情况下不起作用.

由于这个实现是基于Haskell的,我想懒惰的评估和保护的递归/尾递归模数缺点有所不同:

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

如果我理解正确的话,由于懒惰的评估(差不多),当我向另一个人添加一个列表时,Haskell中没有任何事情发生,直到我真正对这个新列表做了一些事情.在下面的例子中,我折叠它.

我不明白的是,保护递归如何保持递归不会增加调用堆栈以及是否可以在严格评估的语言(如Javascript)中显式实现此行为.

希望这个问题不是太宽泛.

为了更好地理解,这里是完整的实现/示例:

// type constructor

const Type = name => {
  const Type = tag => Dcons => {
    const t = new Tcons();

    Object.defineProperty(
      t,
      `run${name}`,
      {value: Dcons});

    t[TAG] = tag;
    return t;
  };

  const Tcons =
    Function(`return function ${name}() {}`) ();

  Tcons.prototype[Symbol.toStringTag] = name;
  return Type;
};


const TAG = Symbol("TAG");
const List = Type("List");


// data constructors

const Cons = x => tx => List("Cons") (cases => cases.Cons(x) (tx));
const Nil = List("Nil") (cases => cases.Nil);


// overload binary functions

const overload2 = (name, dispatch) => {
  const pairs = new Map();

  return {
    [`${name}Add`]: (k, v) => pairs.set(k, v),

    [`${name}Lookup`]: k => pairs.get(k),

    [name]: x => y => {
      if (typeof x === "function" && (VALUE in x))
        x = x(y);

      else if (typeof y === "function" && (VALUE in y))
        y = y(x);

      const r = pairs.get(dispatch(x, y));

      if (r === undefined)
        throw new TypeError("...");

      else if (typeof r === "function")
        return r(x) (y);

      else return r;
    }
  }
};


const dispatcher = (...args) => args.map(arg => {
  const tag = Object.prototype.toString.call(arg);
  return tag.slice(tag.lastIndexOf(" ") + 1, -1);
}).join("/");


// Semigroup "typeclass"

const {appendAdd, appendLookup, append} =
  overload2("append", dispatcher);


// List instance for Semigroup

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));


// fold

const foldr = f => acc => {
  const aux = tx =>
    tx.runList({
      Nil: acc,
      Cons: x => tx_ => f(x) (aux(tx_))})

  return aux;
};


// data

const tx = Cons(1) (Cons(2) (Nil));
const ty = Cons(3) (Cons(4) (Nil));
const tz = append(tx) (ty);


// run

console.log(
  foldr(x => acc => `${x}${acc}`) (0) (tz) // "12340"
);

Answer 1

这不是真正的答案，而是我进一步研究后得出的结论：

1. 尾部递归取模缺点 - TRMC（以及其他操作的“取模”）仅指严格评估的上下文，而受保护的递归指的是惰性评估的上下文
2. TRMC 是一种昂贵的编译器技术，在用户空间中实现它（可能）没有意义
3. TRMC要求运算是结合的（至少形成一个Semigroup），这样括号就可以重新排列

这个问答也很有帮助：尾递归版本列表附加函数 。