Search code examples
javascriptrecursiony-combinator

Finite number of recursions in Javascript with ES6 Y-combinator

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 nth 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!

Solution

  • If imperative programming is an option:

     function getParent(el, n){
   while(n--) el = el.parentNode;
   return el;
}

    Using functional recursion you could do:

     const Y = f => x => f (Y (f)) (x); // thanks to @Naomik
 const getParent = Y(f => el => n => n ? f(el.parentNode)(n - 1) : el);

 console.log(getParent(document.getElementById("test"))(5));

    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:

     (U => U(U))

    Now we can call that U combinator with our Y combinator so that it gets a self reference:

     (U => U(U))
 (Y => f => f( Y(Y)(f) ))

    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:

     (U => U(U))
 (Y => f => x => f( Y(Y)(f) )(x) )
 (f => n => n ? f(n - 1): n)(10) // a small example

    We could also restructure it like this:

     (f => (U => U(U))(Y => f(x => Y(Y)(x))))
 (f => n => n ? f(n - 1): n)(10) // a small example

    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 when n?, so weve got an exit condition now. Now we can finally add our node to the whole thing:

     (U => U(U))
 (Y => f => x => f( Y(Y)(f) )(x) )
 (f => el => n => n ? f(el.parentNode)(n - 1): el)
 (document.getElementById("test"))(10)

    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.