Javascript 惰性求值斐波那契函数

Question

我问了a question在 Scala 中使用惰性求值之前。我试图在 Scala 中编写以下 Haskell 函数:

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

这个问题的答案是我不能使用列表，而应该使用流。现在我正在尝试用 Javascript 做同样的事情。我翻译了函数，并在 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);

但是我得到以下错误:

RangeError: Maximum call stack size exceeded

Javascript 有办法做到这一点吗？

Answer 1

您可以具体化惰性计算正在使用的 thunk(阅读:“尚未评估的函数继续计算”)。

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

这样

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

从某种意义上说，这是一个精确的翻译*，其中我的返回对象表示单个 Haskell (:)“cons”单元格。从这里开始，编写一个“take”函数以将此 javascript“惰性列表”转换为 javascript 严格数组会相对容易。

这是一个版本。

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
}

这样

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

(*) 从技术上讲，即使是 "this" 值也应该包含在一个 thunk 中，但我采用了列表的严格概念，这通常非常接近每个人的直觉。