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?

The idea is that after 10 numbers in this example, the list will no longer be evaluated. — , Jun 26 '13 at 19:47
I'm starting to understand now that `slice()` isn't going to do that. — , Jun 26 '13 at 19:48
https://developer.mozilla.org/en-US/docs/Web/JavaScript/New_in_JavaScript/1.7?redirectlocale=en-US&redirectslug=JavaScript%2FNew_in_JavaScript%2F1.7#Generators — Robert Harvey, Jun 26 '13 at 19:50
Like Scala, you might try using streams here instead of lists. Maybe look at [stream.js](http://streamjs.org/)? I've never used it so I don't know how well it would work here. — Jeff Burka, Jun 26 '13 at 19:51
Thanks guys for the links. That's a good bit of reading I have to do before letting you know whether it worked or not. I'll let you know. — , Jun 26 '13 at 19:52
(@RobertHarvey in Haskell he wouldn't need an exit condition: since only a finite part of the list is required, only that finite part will be calculated, due to lazy evaluation. This convenient treatment of infinite lists is a hallmark of lazy evaluation.) — AndrewC, Jun 26 '13 at 19:59
@AndrewC: So? The OP is asking for a solution in Javascript. See the Mozilla post I linked. — Robert Harvey, Jun 26 '13 at 20:02
Related maybe: http://stackoverflow.com/questions/7944239/generating-fibonacci-sequence — Sergio, Jun 26 '13 at 20:13
@RobertHarvey Indeed. Your link is very helpful to the OP. I was just explaining why in a question entitled "lazy evaluation" the OP deliberately didn't include an exit condition for the recursion. You had seemed to overlook the lazy evaluation aspect when making your comment. Perhaps an explicit "javascript doesn't have lazy evaluation" before stating the need for an exit condition would have been clearer. — AndrewC, Jun 26 '13 at 20:14

J. Abrahamson · Accepted Answer · 2013-06-26T21:59:46.840

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.

+1, thunks are the correct way of doing this. Too bad JS doesn't have macros or you could write stream-cons and stream-cdr — Wes, Jun 26 '13 at 21:36
I say likewise that it's too bad that javascript doesn't have types, else we could define `LazyList a = {"this": a, "next": function () (returns: LazyList a)}` :) — J. Abrahamson, Jun 26 '13 at 21:41

score 2 · Answer 2 · answered Jun 26 '13 at 20:24

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]

score 0 · Answer 3 · edited Nov 26 '16 at 13:31

0

ES6 has generator functions you can use it for lazy evaluation (in conjunction with destructuring assignment operator) Using this technique we can write the fibonacci function like below (just one more way of doing it).

var fib_generator = function *(){
  var current = 0, next = 1;
  while(true)
  {
     [next, current] = [next+current, next];
     yield current;
  }
}

var fib = fib_generator();


// below is the sample code prints values uptill 55
for(var i=0; i<10; i++)
{
   console.log(fib.next().value);
}

edited Nov 26 '16 at 13:31

melpomene

84,125
8
85
148

answered Nov 26 '16 at 12:55

Muqsith

163
1
8

@melpomene thanks. Sorry i assumed lazy evaluation of variables but not of function itself, did not read the question properly. – Muqsith Nov 26 '16 at 13:20

Javascript lazy evaluation fibonacci function

3 Answers3