java - 懒惰斐波那契数列

Question

我刚刚开始学习 haskell，想知道是否有任何方法可以用 C# 或 java 或其他非惰性命令式语言实现以下斐波那契数列。

在 Haskell 中，我们可以使用以下行简洁地生成斐波那契数列

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

问题 - 我知道随着 C#/Java 等的急切评估，上面的内容可能会进入无限循环。但我不明白的是，即使我们使用 thunk，我们如何才能创建一个自引用数据结构，当我们迭代它时它会发生变化(使用递归)。

如果您能分享一些片段，我们将不胜感激

Answer 1

Scala API docs for Stream包含有关如何在 Scala 中执行此操作的示例:

val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }

编辑:要使用像 Haskell 这样没有内置内存功能的语言来实现记忆化，您显然需要使用变异(数组或映射)。例如:

  val fib: Int => Int = {
    val m = ArrayBuffer(0, 1)

    x => if (x < m.size) m(x) else {
      println("Calculating " + x + "...")
      val r = fib(x - 2) + fib(x - 1)
      m += r
      r
    }
  }

这仍然可以被认为是一个纯函数，因为在单线程环境中没有可观察到的副作用(除了运行时性能)。