haskell - Javascript lazy evaluation fibonacci function - Stack Overflow

admin管理员组

文章数量:1332383

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?

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?

• javascript
• haskell
• lazy-evaluation

Share Improve this question Follow edited May 23, 2017 at 11:53 CommunityBot 111 silver badge asked Jun 26, 2013 at 19:44 user377628user377628 12

• 1 where is the end condition? – Elazar Commented Jun 26, 2013 at 19:46
• 1 You don't have an exit condition for your recursion. – Robert Harvey 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. – user377628 Commented Jun 26, 2013 at 19:47
• I'm starting to understand now that slice() isn't going to do that. – user377628 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 ment. Perhaps an explicit "javascript doesn't have lazy evaluation" before stating the need for an exit condition would have been clearer. – AndrewC Commented Jun 26, 2013 at 20:14

 |  Show 7 more ments

3 Answers 3

Sorted by: Reset to default 9

You could reify the thunk (read: "not yet evaluated function which continues the putation") that the lazy putation 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.

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]

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

本文标签： haskellJavascript lazy evaluation fibonacci functionStack Overflow