5

There is a good example in Stream document that gets fibonacci numbers.

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

I would like to implement that by using sliding, so I tried followings.

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

Last line correctly gets Stream(1, ?) but when I concatenate that to above as follows, I get a error (possibly stack overflow, I could not see the exact error message because it was too long) when I try to get 3rd member.

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

If I give 3 numbers as follows, it calculates sums of preceding two numbers. But that's not fibonacci number.

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

Any ideas or help would be appreciated.

Updates

  • I doubt the cause of the error is that sliding method returns Iterator, which needs to know if next value is available using hasNext method
  • sliding method should calculate any sum of previous n numbers if first seeders are given, which are called tribonacci (n=3), tetranacci (n=4), etc.
nineclue
  • 51
  • 4

2 Answers2

2

The problem seems to be that the GroupedIterator (returned by sliding) is over-eager. It forces the next element after your current window when creating each sliding window.

Here's a simple example:

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, ?))

Instead of sliding, you can use scanLeft:

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

The scan function is kind of like fold, but produces all the intermediate results. So what you get is this:

  • 0
  • 1 = 1
  • 0 + 1 = 1
  • 1 + 1 = 2
  • 1 + 2 = 3
  • 2 + 3 = 5
  • ...
DaoWen
  • 32,589
  • 6
  • 74
  • 101
0

DaoWen's clear explanation showed sliding method cannot solve the problem. I found out another way of calculating Fibonacci numbers of higher order.

/* make a Stream of Stream of integer 
input - Stream(0, 1)
output - Stream(0, 1), Stream(1, 1), Stream(1, 2), Stream(2, 3), ... 
*/
def appendSum(initial:Stream[Int]):Stream[Stream[Int]] = 
  Stream.iterate(initial)(s => s.tail :+ s.sum)

/* fibonacci number of higher order is original Stream + new Stream's last member */
def nbonacci(n:Int) = { 
    val inits = Stream.continually(0).take(n-1) :+ 1
    inits.append(appendSum(inits).tail.map(_.last)) 
}

/* print out first 20 members of fibonacci, tribonacci, tetrabonacci numbers */
(2 to 4).foreach(n => {println(s"$n -----"); nbonacci(n).take(20).foreach(println(_))})

It's much cleaner and maybe much faster if sliding returned Stream.

nineclue
  • 51
  • 4