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.

如果你想要的只是堆栈安全，那么你可以使用 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);

希望对您有所帮助。

fix 可以尾递归并因此表示为一个简单的循环吗？

Can fix be tail recursive and thus expressed as a simple loop?

javascript

recursion

functional-programming

fixpoint-combinators