如何在scala中使用滑动Stream获取斐波那契数字？

Question

Stream文档中有一个很好的例子可以获得斐波那契数字.

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

我想通过使用滑动实现它,所以我尝试了以下.

val test = 0 #:: 1 #:: Stream.empty
test.sliding(2).map(_.sum).toStream

最后一行正确获取Stream(1,？)但是当我将其连接到上面时,如下所示,当我尝试获得第3个成员时,我得到一个错误(可能是堆栈溢出,我看不到确切的错误消息,因为它太长了) .

val fibs2:Stream[Int] = 0 #:: 1 #:: fibs2.sliding(2).map(_.sum).toStream

如果我按如下方式给出3个数字,它会计算前两个数字的总和.但那不是斐波纳契数.

val fibs3:Stream[Int] = 0 #:: 0 #:: 1 #:: fibs3.sliding(2).map(_.sum).toStream

任何想法或帮助将不胜感激.

更新

• 我怀疑错误的原因是滑动方法返回Iterator,它需要知道使用hasNext方法是否可以使用下一个值
• 如果给出第一个播种器,则滑动方法应计算前n个数的任意和,称为tribonacci(n = 3),tetranacci(n = 4)等.

Answer 1

问题似乎是GroupedIterator( 返回的sliding) 过于渴望。创建每个滑动窗口时，它会强制当前窗口之后的下一个元素。

这是一个简单的例子：

import scala.util.Try

def bad[T]: Stream[T] = throw new RuntimeException("Don't peek!")

// Should be able to view group of first 2 elements without error,
// but sliding and grouped both read the 3rd element
def testA: Stream[Int] = 1 #:: 2 #:: bad

Try { testA.sliding(2).next }
// res0: scala.util.Try[scala.collection.immutable.Stream[Int]] = Failure(java.lang.RuntimeException: Don't peek!)

Try { testA.grouped(2).next }
// res1: scala.util.Try[scala.collection.immutable.Stream[Int]] = Failure(java.lang.RuntimeException: Don't peek!)

// Adding an extra element before the bad entry gives
// sufficient padding for a sliding window of 2
def testB: Stream[Int] = 1 #:: 2 #:: 3 #:: bad

Try { testB.sliding(2).next }
// res2: scala.util.Try[scala.collection.immutable.Stream[Int]] = Success(Stream(1, ?))

Try { testB.grouped(2).next }
// res3: scala.util.Try[scala.collection.immutable.Stream[Int]] = Success(Stream(1, ?))

sliding您可以使用以下代替scanLeft：

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_+_)

该scan函数有点像fold，但产生所有中间结果。所以你得到的是这样的：

• 0
• 1 = 1
• 0 + 1 = 1
• 1 + 1 = 2
• 1 + 2 = 3
• 2 + 3 = 5
• ...