Javascript lazy evaluation fibonacci function

Question

I asked a question before about using lazy evaluation in Scala. I was trying to write the following Haskell function in Scala:

fib a b = c : (fib b c)
   where c = a+b

The answer to that question was that I couldn't use Lists, but should rather use Streams. Now I'm trying to do the same thing in Javascript. I translated the function, and tried it on this site:

function fib(a,b) {
    c = a+b;
    return [c] + fib(b,c);
}

var res = fib(0,1).slice(0,10);

console.log(res);

But I get the following error:

RangeError: Maximum call stack size exceeded

Does Javascript have a way to do this?

Answer 1

You could reify the thunk (read: "not yet evaluated function which continues the computation") that the lazy computation is using.

var fib = function (a, b) {
  var c = a + b
  return { "this": c, "next": function () { return fib(b, c) } }
}

Such that

> var x = fib(1,1)
> x.this
2
> x = x.next()
> x.this
3

In some sense this is an exact translation*, where my return object represents a single Haskell (:) "cons" cell. From here it'd be relatively easy to write a "take" function to convert this javascript "lazy list" into a javascript strict array.

Here's one version.

var take = function(n, cons) {

    var res = []
    var mem = cons

    for (var i = 0; i < n; i++) {
      res.push(mem.this)
      mem = mem.next()
    }

    return res
}

Such that

> take(10, fib(1,1))
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

(*) Technically even the "this" value ought to be wrapped in a thunk, but I took the head-strict notion of lists which is usually pretty close to everyone's intuition.

Answer 2

Not exactly Haskell lazy evaluation, but you can do something similar with currying.

function fib(a,b) {
    var first = true;

    return function(n) {
        if (!isFinite(n) || n < 0)
            throw "Invalid argument";

        var result = first ? [a,b] : [];
        first = false;

        for (var i = result.length; i < n; i++)
            result.push(b = a+(a=b));

        return result;
    };
}

---

The returned function can be invoked multiple times to get a continuation of results:

var f = fib(0,1); // Initialize the sequence with starting values

// Invoke the resulting function with the number of results you want
console.log(f(10)); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

console.log(f(4));  // [55, 89, 144, 233]

console.log(f(4));  // [377, 610, 987, 1597]