lab42_streams

Bringing Streams to Ruby

An excellent introduction into Streams can be found here

Basic Stream Tutorial

Streams are lazy, immutable lists, or for the purists, lazy cons cells (well the tail/cdr is lazy, the head/car is not).

A first example

Infinite Streams

Given the following definition

```ruby :include def fibs a=0, b=1 cons_stream a do fibs b, a+b end end


The following spec will be satisfied

```ruby :example
    expect(fibs.drop(1000).head).
      to eq(43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875)

There are several things to remember here:

The tail of a stream is always provided as block or lambda, the only way in ruby to implement a normal order parameter.
The result of the tail (that is when the delay or promise the tail defines is forced or realised) must be a Stream. This has to be automated into your reasoning about Streams lest you will have difficulties to come up with stream based solutions.
When the promise of the tail is forced the stack frame of the cons_stream call is not active any more, there will be no stack overflow.

Transformation Chain

One major advantage of streams (and lazy evaluation in general) is that transformations can be composed without any performance penality.

While for example the following code would be terribly inefficent

    elements = { 2 => "two", 4 => "four" }
    list = 1..2 # but imagine a very large value of 2
    list.map{ |x| x * 2 }.map{ |x| elements[x] }.map(&:reverse)

the following stream based code is not.


     translation = { [true,true] => "fizzbuzz", [true, false] => "fizz", [false, true] => "buzz" }
     integers    = Stream.iterate 0, :succ
     fizzbuzz    = integers
        .reject{ |x| (x%100).zero? }
        .map{ |i| [(i%3).zero?,(i%5).zero?,i] }
        .map{ |f,b,i| translation.fetch([f,b],i) }

The reason for this is that, up to now, no single computation has been done, but promises for doing so have been registered. Only when we eventually force values these computations will be executed and then it will make little difference if we execute one complex computation or five simple ones.

And as we operate on infinite streams it becomes obvious that the implementation must delay up to the end.

Memoization

The fourth point to know about Streams is that:

All promises are memoized.

Only for that reason the following naïve, but elegant implementation of the fibonacci sequence has O(N) runtime characteristics, and the result can be computed:

```ruby :include

let(:fibs1) do 
  cons_stream(0){
    cons_stream(1){
      combine_streams fibs1, fibs1.tail, :+
    }
  }
end


```ruby :example
    expect(fibs1.drop(1000).head)
      .to eq(43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875)

Finite Streams

Finite Streams are implemented the same way LISP imlements lists, by providing an End_Marker. What is nil in LISP is empty_stream in Ruby. As a matter of fact the empty_stream method returns a singleton called Lab42::Stream::Empty which is also accessible via EmptyStream if you required the lib with require 'lab42/stream/auto_import' which is true for the demos.

Here is an example of a finite stream

```ruby :include let(:digits){ finite_stream( 0..9 ) }


Now the following all hold

```ruby :example
    expect(digits.drop(9).head).to eq(9)

```ruby :example expect(digits.drop(10)).to be_empty


or alternatively

```ruby :example
    expect(digits.drop(10)).to eq(EmptyStream)