javascriptrecursionfunctional-programmingfixpoint-combinators

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

I can't figure out how to express fix as a tail recursive algorithm. Or is it already tail recursive? I am probably overthinking it...

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

I tried a lot but haven't come up with anything remotely useful yet. A tail recursive algorithm could be easily transformed to a stack safe loop. That is the actual goal.

Solution

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

    First, convert the definition of fix into 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;
};

    Next, convert the resulting program into 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)))));

    Now, fix is tail recursive. However, this is probably not what you want.

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

    If all you want is stack safety, then you could use the 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");

    However, this would require that you change the definition of sum as well.

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

    Hope that helps.