CODEWITHSUNDEEP
scalastreamlazy-evaluationfibonacci
KodeWarrior
KodeWarrior

Reputation: 3598

Tracing execution of calculation of Fibonacci using Scala Streams

I'm a functional programming/scala newbie. I have been trying to get my head wrapped around the following code snippet and output produced.

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}))
}

Output Trace:

scala> fib take 4 foreach println

1
2
1 + 2
3
1 + 2  <-- Why this ?????
2 + 3
5

I do not understand how 1 + 2 is evaluated for the calculation of result 5. In theory, I do understand that def should force re calculation of fib but I'm not able to locate where in the execution trace this could happen.

I would like to step u guys through my understanding 

Output( My understanding):

1  
This is the head, trivial

2  
This is the tail of the first Cons in Cons( 1, Cons( 2, fn ) ). Trivial.

1 + 2
(fib zip fib.tail) map {case (x, y) => println("%s + %s".format(x, y)); x + y}))
first element of fib is 1
first element of fib.tail is 2
Hence 1 + 2 is printed.

The zip operation on the Stream does the following
 Cons( ( this.head, that.head), this.tail zip that.tail ) # this is fib and that is fib.tail. Also remember that this.tail starts from 2 and that.tail would start from 3. This new Stream forms an input to the map operation.

The map operation does the following 
cons(f(head), tail map f ) # In this case tail is a stream defined in the previous step and it's not evaluated.

So, in the next iteration when tail map f is evaluated shouldn't just 2 + 3 be printed ? I don't understand why 1 + 2 is first printed

:( :( :(

Is there something obvious I'm missing ?

Upvotes: 1

Views: 326

Answers (1)

elm
elm

Reputation: 20415

A coding for Fibonacci proposed in https://stackoverflow.com/a/20737241/3189923 with verbosity added here for tracing execution,

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)((a,b) => {
  println(s"$a + $b = ${a+b}")
  a+b
})

Then, for instance,

scala> fibs(7)
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
res38: Int = 13

Upvotes: 1

Related Questions