lazy_stream

[] (https://travis-ci.org/melvinxie/lazy_stream)

A Ruby class to represent lazy infinite stream. It is implemented in the same way as the streams in the book [SICP] (http://mitpress.mit.edu/sicp/full-text/sicp/book/node69.html).

Installation

The library is distributed via RubyGems:

$ gem install lazy_stream

Usage

A stream is just a delayed list. We do lazy evaluation in Ruby with code blocks. To create a stream:

require 'lazy_stream'

s = lazy_stream(1) { lazy_stream(2) { lazy_stream(3) } }
s.to_a       #=> [1, 2, 3]
s.first      #=> 1
s.rest       #=> A LazyStream object for the rest of the list [2, 3]
lazy_stream  #=> An empty LazyStream object

lazy_stream is just a shortcut for LazyStream.new. Methods empty?, at, drop, each, map, reduce, select, take are also implemented like Array.

It becomes powerful when we construct infinite streams like these:

def integers_starting_from(n)
  lazy_stream(n) { integers_starting_from(n + 1) }
end

integers_starting_from(1).take(10).reduce(&:+)  #=> 55

def fibgen(a, b)
  lazy_stream(a) { fibgen(b, a + b) }
end

fibgen(0, 1).take(10).to_a  #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

def sieve(stream)
  lazy_stream(stream.first) do
    sieve(stream.rest.select { |x| x % stream.first > 0 })
  end
end

def primes
  sieve(integers_starting_from(2))
end

primes.take(10).to_a  #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Or define streams implicitly:

ones = lazy_stream(1) { ones }
ones.take(10).to_a  #=> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

integers = lazy_stream(1) { LazyStream.add(ones, integers) }
integers.take(10).to_a  #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# fibs is a stream beginning with 0 and 1, such that the rest of the stream can
# be generated by adding fibs to itself shifted by one place:
#     1 1 2 3 5  8 13 21 ... = fibs.rest
#     0 1 1 2 3  5  8 13 ... = fibs
# 0 1 1 2 3 5 8 13 21 34 ... = fibs
fibs = lazy_stream(0) { lazy_stream(1) { LazyStream.add(fibs.rest, fibs) } }
fibs.take(10).to_a  #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

More complicated example, approximating π, with Euler's transform and the tableau sequence accelerator:

def pi_summands(n)
  lazy_stream(1.0 / n) { pi_summands(n + 2).map(&:-@) }
end

def pi_stream
  pi_summands(1).partial_sums.scale(4)
end

def euler_transform(s)
  lazy_stream(s[2] - ((s[2] - s[1])**2 / (s[0] - 2 * s[1] + s[2]))) do
    euler_transform(s.rest)
  end
end

def make_tableau(s, &transform)
  lazy_stream(s) { make_tableau(transform.call(s), &transform) }
end

def accelerated_sequence(s, &transform)
  make_tableau(s, &transform).map(&:first)
end

accelerated_sequence(pi_stream, &method(:euler_transform)).take(8).print
# 4.0
# 3.166666666666667
# 3.142105263157895
# 3.141599357319005
# 3.1415927140337785
# 3.1415926539752927
# 3.1415926535911765
# 3.141592653589778

Since the functions are all recursive here, to make them actually work for large data set, we need to enable the tail call optimization in Ruby, otherwise you will hit the stack level too deep error soon.

For more examples, see my blog post and example spec.