javascript - Is tail recursion merely a special case of CPS? -
i've implemented map
in tail recursive , continuation passing style. both versions quite similar:
var inc = x => ++x; var xs = [1,2,3,4,5]; var mapr = f => xs => { var rec = acc => { acc[acc.length] = f(xs[acc.length]); return acc.length < xs.length ? rec(acc) : acc; } return rec([]); } mapr(inc)(xs); // [2,3,4,5,6] var mapc = f => xs => cc => { var rec = acc => cc => { acc[acc.length] = f(xs[acc.length]); return acc.length < xs.length ? cc(acc)(rec) : acc; } return cc(rec([])(rec)); } mapc(inc)(xs)(console.log.bind(console)); // [2,3,4,5,6]
instead of cc(acc)(rec)
have wrote rec(acc)
. conclusion correct, tail recursion merely special case of cps , mapc
written var rec = acc => {...}
proper cps function?
i'd write thing in pure cps following:
const inc = x => cont => cont(x+1); const map = f => xss => cont => { if (!xss.length) cont([]); else f(xss[0])(x => map(f)(xss.slice(1))(xs => cont([x].concat(xs)))); }; // or accumulator: const mapa = f => xs => cont => { const rec = acc => { if (acc.length >= xs.length) cont(acc); else f(xs[acc.length])(x => { acc.push(x); rec(acc); }); } rec([]); };
is tail recursion merely special case of cps?
i wouldn't so. cps isn't related recursion @ all.
however, cps consists of tail calls, makes stack superfluous - , functions powerful.
Comments
Post a Comment