I came across an answer to another SO question about recursion in Javascript, that gave a very terse form in ES6 using the Y-combinator, using ES6's fat arrow, and thought hey, that'd be neat to use - then 15 minutes or so later had circled back to hm, maybe not.
I've been to a few Haskell/Idris talks and run some code before, and familiar with standard JS, so was hoping I'd be able to figure this out, but can't quite see how a simple "do n
recursions and return" is supposed to go, and where to implement a decrementing counter.
I just wanted to simplify getting the n
th parent node of a DOM element, and there seem to be more dense explain-all guides than examples of simple applications like this.
The example I first saw is:
const Y = a => (a => a(a))(b => a(a => b(b)(a)));
while this more recent answer gives:
const U = f => f (f)
const Y = U (h => f => f (x => h(h)(f)(x)))
...which is given with examples of what the internal functions might be, and some example outputs, but introducing the U-combinator doesn't really help clarify this for me.
In the first example I can't really begin to understand what b
might be in my case - I know I need one function a
to return the parent node:
const par = function(node) {
return node.parentNode;
}
I came up with the below:
function RecParentNode(base_node, n) {
// ES6 Y-combinator, via: https://stackoverflow.com/a/32851197/2668831
// define immutable [const] functions `Y` and `fn` [`fn` uses `Y`]
// the arguments of `Y` are another two functions, `a` and `b`
const Y = par=>(par=>par(par))(b=>par(par=>b(b)(par)));
const fn = Y(fn => n => {
console.log(n);
if (n > 0) {
fn(n - 1);
}
});
}
but then couldn't see what to do with the spare b
lying around, and was about to delete it all and just forget I bothered.
All I'd like is to apply the par
function n
times, since the only alternatives I'm aware of are chaining .parentNode.parentNode.parentNode
... or cheating and turning a string into an eval
call.
Hoping someone familiar with functional JS could help me get the idea here for how to use the Y-combinator to make this helper function RecParentNode
- thanks!
If imperative programming is an option:
Using functional recursion you could do:
Lets build this Y-Combinator from the ground up. As it calls a function by the Y-Combinator of itself, the Y-Combinator needs a reference to itself. For that we need a U-Combinator first:
Now we can call that U combinator with our Y combinator so that it gets a self reference:
However that has a problem: The function gets called with an Y-Combinator reference which gets called with a Y-Combinator reference wich gets called .... weve got Infinite recursion. Naomik outlined that here. The solution for that is to add another curried argument(e.g.
x
) that gets called when the function is used, and then another recursive combinator is created. So we only get the amount of recursion we actually need:We could also restructure it like this:
To get your first snippet, so basically its the same thing just a bit reordered and obfuscated through shadowing.
So now another combinator gets only created when
f(n-1)
gets called, which only happens whenn?
, so weve got an exit condition now. Now we can finally add our node to the whole thing:That would be purely functional, however that is not really useful as it is extremely complicated to use. If we store function references we dont need the U combinator as we can simply take the Y reference. Then we arrive at the snippet above.
due diligence
Hey, that answer you found is mine! But before looking at various definitions of the Y combinator, we first review its purpose: (emphasis mine)
Now, let's review your question
JavaScript supports direct recursion which means functions can call themselves directly by name. No use of U or Y combinators is necessary. Now to design a recursive function, we need to identify our base and inductive case(s)
n
is zero; return thenode
n
is not zero, butnode
is empty; we cannot get the parent of an empty node; returnundefined
(or some error if you wish)n
is not zero andnode
is not empty; recur using the node's parent and decrementn
by 1.Below we write
nthParent
as a pure functional expression. To simplify the discussion to follow, we will define it function in curried form.but what if...
So suppose you were running your program with a JavaScript interpreter that did not support direct recursion... now you have a use case for the combinators
To remove the call-by-name recursion, we wrap our entire function in another lambda whose parameter
f
(or name of your choosing) will be the recursion mechanism itself. It is a drop-in replacement fornthParent
– changes in boldNow we can define Y
And we can remove direct recursion in Y with U using a similar technique as before– changes in bold
But in order for it to work in JavaScript, which uses applicative order evaluation, we must delay evaluation using eta expansion – changes in bold
All together now
Now I hope you see why the Y combinator exists and why you wouldn't use it in JavaScript. In another answer, I attempt to help readers gain a deeper intuition about the Y combinator by use of a mirror analogy. I invite you to read it if the topic interests you.
getting practical
It doesn't make sense to use the Y combinator when JavaScript already supports direct recursion. Below, see a more practical definition of
nthParent
in uncurried formBut what about those maximum recursion depth stack overflow errors? If we had a deep tree with nodes thousands of levels deep, the above function will produce such an error. In this answer I introduce several ways to work around the problem. It is possible to write stack-safe recursive functions in a language that doesn't support direct recursion and/or tail call elimination!