Recursion is a functional primitive and thus we try to avoid it, because ultimately it is only a nasty imperative loop in disguise. In FP we usually use folds and only resort to recursion if folding is not expressive enough.
In Javascript we additionally need to take care of stack-safety. It is therefore a smart strategy to implement folds with specific trampolines suitable for each type:
// Foldable
const arrFold = f => init => xs => {
let acc = init;
for (let i = 0; i < xs.length; i++) // trampoline
acc = f(acc) (xs[i], i);
return acc;
};
// identity
const id = x => x;
// function composition
const comp = f => g => x => f(g(x));
const compn = arrFold(comp) (id); // variadic
// MAIN
const inc = x => x + 1;
compn([inc, inc, inc, inc, inc]) (0); // 5
You may think yourself safe with arrFold being implemented as a stack-safe trampoline. However, you are not:
// MAIN
const inc = x => x + 1;
const xs = Array(1e5).fill(inc);
const foo = compn(xs); // still okay
foo(0); // stack overflow
Composing means to combine two functions to a description of a new function, which is only evaluated if the required argument is provided. So iteratively composing builds up a huge description of descriptions waiting to be run.
What can we do about it? We need a way to break the composition apart. We've already used trampolines. It seems to be the proper tool:
// trampoline for deferred function call trees
const postRec = f => (...args) => {
let step = f(...args);
while (step.tag !== "Base")
step = f(...step.args);
return init => {
let {f, x} = step.x(init);
while (step = f(x)) {
if (step && step.tag === "Call") {
step = step.f(step.x);
if (step && step.tag === "Call") {
({f, x} = step);
continue;
}
else break;
}
else break;
}
return step;
}
};
const Base = x =>
({tag: "Base", x});
const Call = f => x =>
({tag: "Call", f, x});
const Step = (...args) =>
({tag: "Step", args});
// function composition
const comp = f => g => x => f(g(x));
const compn = xs => // variadic
postRec((i, acc) =>
i === xs.length
? Base(acc)
: Step(i + 1, Call(comp(acc) (xs[i]))))
(0, Call(id));
// MAIN
const inc = x => x + 1;
const xs = Array(1e5).fill(inc);
compn(xs) (0); // 100000
postRec isn't a beauty. It reveals all its ugly operational semantics. Javascript was never about beauty but to get things done, I guess.
Anayway, in FP we often have to deal with descriptions of computations that create huge deferred function call trees. Having a specialized trampoline at our disposal allows us to get serious about FP in JS.
If you want to learn more about FP in JS take a look at my course on Github.
Top comments (5)
Interesting analysis Iven.
Is there any reason you wouldn't just do this?...
No, you missed the whole point of the post! In order to keep your code pure while working with data bases, local storage, file systems, random numbers, dates etc. you need to defer the impure computations. You do that by merely describing them. This may lead to stack overflows as I demonstrated with the contrived example above.
You've lost me there.
Could you give me an example of where my code above would throw a RangeError (stack overflow)?
No offence, but I can't help ya. I wasn't talkin about your exmaple, because it doesn't make any sense in the context of my post. You built a variadic applicator, which is dual to function composition. You cannot compare function application
f => x => f(x)with compositionf => g => x => f(g(x)). Both have completely different operational semantics.Sounds pretty deep in the academics. ;)
When building applications I test if the behavior is robust and if it's performant and achieves the desired result.
Good luck.