Skip to content

Instantly share code, notes, and snippets.

@neizod
Forked from 140bytes/LICENSE.txt
Last active Apr 27, 2019
Embed
What would you like to do?
Fibonacci (Recursive Lambda)

Fibonacci (Recursive Lambda)

98b. Yet another Fibonacci function.

Lambda?

In brief: Just another way of calling anonymous function (function that had no name).

This way, even you do a recursive function. The name of function doesn't even leak to global scope!

Then Why?

1st this is (at some point) a fundamental of functional programming, a very interesting programming paradigm. 2nd isn't it fun?

How Can It Work?

You got confused how the hell on earth an unnamed-function can do recursion, right? Well then if we give it a name (for learning propose, of course).

    f = function(arg){return arg+1;}

And we define some function

    h = function(func){return func(1) * func(4);}

Then you'll see that

    h(f) /* can pass function f (which is unnamed) into 2 place. you can reuse it! */

Now, we need to modify our h function to be a combinator, which is something that had behavior like

    h(f); /* will yield */ f(h, f);

I'll leave the rest for your own fun. Hope you like it!

function(v) { // main function wrapper
return(
function(f, a){return f(f, a)}( // lambda combinator
function(r, n){ // fibonacci recursive function
return n>1? // check
r(r, n-1) + r(r, n-2): // recursive
n // terminate
},
v // feed arg to make it start
)
)
}
function(v){return(function(f,a){return f(f,a)}(function(r,n){return n>1?r(r,n-1)+r(r,n-2):n},v))}
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2012 Nattawut Phetmak <http://about.me/neizod>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
{
"name": "fibonacciRecursiveLambda",
"description": "learn recursive the hard way.",
"keywords": [
"fibonacci",
"recursive",
"lambda",
"combinator",
"functional"
]
}
<!DOCTYPE html>
<title>Fibonacci (Recursive Lambda)</title>
<div>Expected value: <b>1,1,2,3,5,8,13,21,34,55</b></div>
<div>Actual value: <b id="ret"></b></div>
<script>
// write a small example that shows off the API for your example
// and tests it in one fell swoop.
var fib = function(v){return(function(f,a){return f(f,a)}(function(r,n){return n>1?r(r,n-1)+r(r,n-2):n},v))}
document.getElementById( "ret" ).innerHTML = function(t,i){for(i=0;i<10;t[i++]=fib(i));return t}([])
</script>
@maettig

This comment has been minimized.

Copy link

@maettig maettig commented Mar 20, 2012

This is clever. You made JavaScript look like Scheme (or Lisp, if you are more familiar with this). I like that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment