O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Streams meet queues

Going back to our functional FIFO queue implementation, do you remember we had to pay the price of occasional reversal? The invariant asserted that the out list would never be empty when the in list is non-empty.

In case the invariant is violated, we can restore it by reversing the in list and turning it into a new out list. We could exploit this laziness to address the once in a while (and possibly costly) reversal. The idea is to make the out list a Stream. The in list remains a strict list, as before. This helps us do the reversal on demand:

 case class LazyQueue(out: Stream[Int], outLen: Int, in: List[Int], inLen: Int) { def push(elem: Int) = { val p = makeLazyQueue(out, outLen, elem :: in, inLen + 1) println(s"pushed: ${elem} ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required