Streams chapter in Okasaki's Purely Functional Data Structure

Question

In his introductory chapter on streams, Okasaki provides 2 implementations for drop on streams.

He explicitly mentions that the second is more efficient (and both have the same semantics), but I cannot seem to figure out why one is more efficient than the other. Any insight would be greatly appreciated.

Answer 1

If I had to guess, I would say that this has to be due to the fact that the second version is not making use of as much laziness as the first, yet it seems that regardless of the context, if you force any bit of the result, then you force the entire computation. For example, let's say I wanted to do:

val x = hd ($drop(10, l))

For the first version, we need to go through all 10 iterations, before we end up with a cons cell (assuming the stream has more than 10 elements). This is the same amount of computation that would be performed in the second version as well, however, we don't have to deal with the overhead of creating a thunk in each iteration and forcing it.

Certain compilers, like GHC, will actually perform something called strictness analysis, where you try and determine if a particular term is going to be forced, and if so, there is no need to create a thunk and then force it, more details about that can be found here

For take on the other hand,

val x = hd ($take(10, l))

Under the fully lazy version, we only need to evaluate the first iteration of take, until we can stop, whereas an analog of the second version would evaluate all 10 iterations. In this example, laziness gives you some savings.