如何在Scala中修复我的Fibonacci流

Question

我定义了一个返回Fibonacci流的函数,如下所示:

def fib:Stream[Int] = {
  Stream.cons(1,
    Stream.cons(2,
      (fib zip fib.tail) map {case (x, y) => println("%s + %s".format(x, y)); x + y}))
}

功能正常但看起来效率低(参见下面的输出)

scala> fib take 5 foreach println
1
2
1 + 2
3
1 + 2
2 + 3
5
1 + 2
1 + 2
2 + 3
3 + 5
8

所以,看起来该函数从一开始就计算出第n个斐波纳契数.这是对的吗？你会怎么解决它？

Answer 1

那是因为你用了一个def.尝试使用val:

lazy val fib: Stream[Int] 
  = 1 #:: 2 #:: (fib zip fib.tail map { case (x, y) => x + y })

基本上def是一种方法; 在您的示例中,每次调用方法调用构造新流时都会调用该方法.之间的区别def,并val已被覆盖在此之前,所以我不会细讲这里.如果你来自Java背景,那应该很清楚.

这是关于scala的另一个好处; 在Java中,方法可能是递归的,但类型和值可能不是.在scala中,值和类型都可以是递归的.

Answer 2

你可以用另一种方式做到这一点:

lazy val fibs = {
  def f(a: Int, b: Int): Stream[Int] = a #:: f(b, a + b)
  f(0, 1)
}