Lazy array

Ruby
1

How can I get a lazy array in Ruby? E.g., in Haskell, I can talk about
[1…], which is an infinite list, lazily generated as needed. I can also
do
things like “iterate (+2) 0”, which applies whatever function I give it
to
generate a lazy list. In this case, it would give me all even numbers.
Anyway, I’m sure I can do such things in Ruby, but can’t seem to work
out
how.

2

Ruby Arrays dynamically expand as needed. You can apply blocks to them
to
return things like even numbers.

array = []
array.size # => 0
array[0] # => nil
array[9999] # => nil
array << 1
array.size # => 1
array << 2 << 3 << 4
array.size # => 4

array = (0…9).to_a
array.select do |e|
e % 2 == 0
end

=> [0,2,4,6,8]

Does this help?

3

Ruby 1.9 has the Enumerator class, which can act like a lazy list I
think. A good example is given in the documentation:

fib = Enumerator.new { |y|
a = b = 1
loop {
y << a
a, b = b, a + b
}
}

p fib.take(10) #=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Also, this is a nice trick:

Infinity = 1.0/0

range = 5…Infinity
p range.take(10) #=> [5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

This one only works for consecutive values though.

jeremy

4

Benoit D. wrote:

So, with Enumerator it should be:

even = Enumerator.new { |y|
i = 0
loop {
y << i
i += 2
}
}

p even.take(5) # => [0, 2, 4, 6, 8]

But that is not really common practice in Ruby (Enumerator for so
simple things).

In any case, that Enumerator block form is only syntactic sugar. You can
do the same without using the Enumerator class:

even = Object.new
def even.each(&blk)
(2…1.0/0).step(2,&blk)
end
even.extend Enumerable
p even.take(5)

In both cases, all you’re doing is having ‘each’ generate an infinite
series, and then truncating it with ‘take’.

This is not useful normally, because you can’t chain it - most of the
Enumerable functions like ‘map’, ‘select’ etc collect the full results
into an Array before continuing.

However, it’s quite possible to have these functions process one element
at a time without generating the intermediate arrays, and there is an
implementation of this in the ‘facets’ library:

RUBY_VERSION
=> “1.8.6”

require ‘rubygems’
=> true

require ‘facets/enumerator’
=> true

require ‘facets/enumerable/defer’
=> true

(1…1_000_000_000).defer.select { |i| i % 2 == 0 }.map { |i| i+100 }.take(10).to_a
=> [102, 104, 106, 108, 110, 112, 114, 116, 118, 120]

Infinite lists are no problem here - each element propagates through the
whole chain before the next. You’re processing ‘horizontally’ rather
than ‘vertically’.

Note that this doesn’t use Threads or Fibers, it’s efficient, and it
works in ruby 1.8. For the implementation details, see the Denumerator
class.

5

On 2 August 2010 05:22, jeremy Ruten [email protected] wrote:

array << 1

So, with Enumerator it should be:

even = Enumerator.new { |y|
i = 0
loop {
y << i
i += 2
}
}

p even.take(5) # => [0, 2, 4, 6, 8]

But that is not really common practice in Ruby (Enumerator for so
simple things).

You would probably need something like (0…max).step(2) { |even_n| p
even_n }

B.D.

6

2010/8/2 Brian C. [email protected]:

(2…1.0/0).step(2,&blk)
end
even.extend Enumerable
p even.take(5)

Even simpler:

irb(main):014:0> even = (2…1.0/0).step(2)
=> #Enumerator:0x1027efc4
irb(main):015:0> even.take 5
=> [2.0, 4.0, 6.0, 8.0, 10.0]

irb(main):016:0> even = 2.step(1/0.0, 2)
=> #Enumerator:0x102a070c
irb(main):017:0> even.take 5
=> [2.0, 4.0, 6.0, 8.0, 10.0]

(pun intended)

=> [102, 104, 106, 108, 110, 112, 114, 116, 118, 120]

Infinite lists are no problem here - each element propagates through the
whole chain before the next. You’re processing ‘horizontally’ rather
than ‘vertically’.

Note that this doesn’t use Threads or Fibers, it’s efficient, and it
works in ruby 1.8. For the implementation details, see the Denumerator
class.

Kind regards

robert

7

On Sunday, August 01, 2010 05:45:02 pm Andrew W. wrote:

How can I get a lazy array in Ruby? E.g., in Haskell, I can talk about
[1…], which is an infinite list, lazily generated as needed. I can also do
things like “iterate (+2) 0”, which applies whatever function I give it to
generate a lazy list. In this case, it would give me all even numbers.
Anyway, I’m sure I can do such things in Ruby, but can’t seem to work out
how.

In your specific case, you could do this:

list = (1…(1.0/0))

But you can’t necessarily iterate it like you want, so no, Ruby does not
have
an equivalent feature. You can do things like this:

list.first(10).map{|x| x*2}

That would give you the first ten even numbers, but it wouldn’t work the
way
you expect – first(10) actually dumps those into an array, and map
immediately creates a new array from that one. It’s not at all like the
Haskell/functional concept.

So, you can do similar and interesting things, and you can probably get
close
to the semantics (roughly), but the implementation is going to be very
imperative/eager, and not at all lazy. You can do lazy-ish
transformations by
writing your own Enumerators, but those aren’t as elegant to write.

I think this is a solvable problem, even solvable within Ruby, I just
haven’t
really seen it done, and there doesn’t seem to be anything in the core
language that really does it.

8

On Sun, Aug 1, 2010 at 3:45 PM, Andrew W. [email protected]
wrote:

How can I get a lazy array in Ruby? E.g., in Haskell, I can talk about
[1…], which is an infinite list, lazily generated as needed. I can also do
things like “iterate (+2) 0”, which applies whatever function I give it to
generate a lazy list. In this case, it would give me all even numbers.
Anyway, I’m sure I can do such things in Ruby, but can’t seem to work out
how.

The Ruby equivalent of a lazy array is an enumerator. In Ruby 1.9.2,
you can get an infinite list of positive integers as:

(1…Float::INFINITY).to_enum,

For non-negative even integers, you could do:
(0…Float::INFINITY).step(2)