javascript - fix 可以是尾递归的，因此可以表示为一个简单的循环？

Question

不知道怎么表达fix作为尾递归算法。或者它已经是尾递归了？大概是我想多了……

const fix = f => x => f(fix(f)) (x); // redundant eta abstraction due to eager eval

const sum = fix(go => acc => ([x, ...xs]) =>
  x === undefined
    ? acc
    : go(acc + x) (xs)) (0);
    
const main = sum([1,2,3,4,5]);

console.log(main); // 15

我尝试了很多，但还没有想出任何远程有用的东西。尾递归算法可以很容易地转换为堆栈安全循环。这才是真正的目标。

Answer 1

I can't figure out how to express fix as a tail recursive algorithm.

一、转换 fix的定义进入 A-normal form .

// fix :: ((a -> b) -> a -> b) -> a -> b
const fix = f => x => {
    const g = fix(f);
    const h = f(g);
    const y = h(x);
    return y;
};

接下来，将生成的程序转换为 continuation-passing style .

// type Cont r a = (a -> r) -> r

// fix :: ((a -> Cont r b) -> Cont r (a -> Cont r b)) -> Cont r (a -> Cont r b)
const fix = f => k => k(x => k =>
    fix(f) (g =>
    f(g)   (h =>
    h(x)   (y =>
    k(y)))));

现在， fix是尾递归的。但是，这可能不是您想要的。

A tail recursive algorithm could be easily transformed to a stack safe loop. That is the actual goal.

如果您想要的只是堆栈安全，那么您可以使用 Trampoline 单子(monad)。

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce(x => f(fix(f))(x));

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

// reachable code
console.log("begin"); // open the console in your browser

// infinite loop
trampoline(fix(id)(0));

// unreachable code
console.log("end");

但是，这需要您更改 sum 的定义。也是。

// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ({ bounce: true, func, args });

// Return :: a -> Trampoline a
const Return = value => ({ bounce: false, value });

// trampoline :: Trampoline a -> a
const trampoline = result => {
    while (result.bounce) result = result.func(...result.args);
    return result.value;
};

// fix :: ((a -> Trampoline b) -> a -> Trampoline b) -> a -> Trampoline b
const fix = f => Bounce((...args) => f(fix(f))(...args));

// _sum :: (Number, [Number]) -> Trampoline Number
const _sum = fix(recur => (acc, xxs) => {
    if (xxs.length === 0) return Return(acc);
    const [x, ...xs] = xxs;
    return recur(acc + x, xs);
});

// sum :: [Number] -> Trampoline Number
const sum = xxs => _sum(0, xxs);

// result :: Number
const result = trampoline(sum([1,2,3,4,5]));

// 15
console.log(result);

希望有帮助。