Как исправить мой поток Фибоначчи в Scala

Question

Я определил функцию для возврата потока Фибоначчи следующим образом:

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 уже было на SO до , поэтому я не буду здесь вдаваться в подробности. Если вы из Java-фона, это должно быть довольно ясно.

Это еще одна приятная вещь в скале; в Java методы могут быть рекурсивными, а типы и значения - нет. В scala значения и типы могут быть рекурсивными.

Answer 2

Вы можете сделать это другим способом:

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