Recursion in livescript

I have been looking at JavaScript, and languages that compile to JS. Coffeescript was my first love in this domain, and I have very recently transitioned to LiveScript, just a few months ago.

Until now, I was not faced with a problem for which recursion is the most natural solution. A couple of days go, when I was writing this program to test for a palindromic number, a recursive implementation seemed the most sensible approach. LiveScript being my new found love, I fired up vim, and… blank.

I tried searching on google, but it turned up nothing useful. I spent almost half an hour reading livescript and prelude, to find these two solutions. Turns out that you can use the keyword function to create named functions, which get hoisted as usual with javascript.

function fib x
   if x<0 then throw new Error
   if x<3 then x
   else fib(x-1)+fib(x-2)

Or, you can use the fix function from prelude to do anonymous recursion. This is the first time I saw the beautiful Y combinator being used this way. And I had to read my old notes on Y combinators and Javascript call and apply to understand the magic of what is happening.

require! 'prelude-ls'.fix

fib = fix (fib) ->
   (x) ->
       if x < 0 throw new Error
       if x < 3 then x
       else fib(x-1) + fib(x-2)

Looks similar? Nope. Here, fix takes a function that returns a function as an argument, and returns a function that is the inner function, with the outer argument referring to the inner function itself. Did that make any sense? 😀

The beauty of this approach is that the function fib doesn’t get hoisted, it is just an ordinary variable assignment, not a named function, and we just did anonymous recursion!

Don’t know if the sound of it excites you, but I sure am excited. Recursion in an anonymous function? Isn’t that cool?

Actually, looks like one of the common applications of Y combinator is to do anonymous recursion, but I didn’t think of it earlier.

Advertisements