2

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?

Improve this question
12
  • 1
    where is the end condition? Commented Jun 26, 2013 at 19:46
  • 1
    You don't have an exit condition for your recursion. Commented Jun 26, 2013 at 19:47
  • 3
    The idea is that after 10 numbers in this example, the list will no longer be evaluated. Commented Jun 26, 2013 at 19:47
  • I'm starting to understand now that slice() isn't going to do that. Commented Jun 26, 2013 at 19:48
  • 1
    @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. Commented Jun 26, 2013 at 20:14

3 Answers 3

Reset to default
9

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

+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
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)} :)
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]
Improve this answer

Comments

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);
}

Improve this answer

1 Comment

@melpomene thanks. Sorry i assumed lazy evaluation of variables but not of function itself, did not read the question properly.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.