Lazy array

ruby-talk
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?

···

On Sun, Aug 1, 2010 at 17:45, Andrew Wagner <wagner.andrew@gmail.com> 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.

3

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.

···

On Sunday, August 01, 2010 05:45:02 pm Andrew Wagner 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.

4

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)

···

On Sun, Aug 1, 2010 at 3:45 PM, Andrew Wagner <wagner.andrew@gmail.com> 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.

5

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

···

On Sun, Aug 1, 2010 at 8:56 PM, skim <skim.la@gmail.com> wrote:

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?

On Sun, Aug 1, 2010 at 17:45, Andrew Wagner <wagner.andrew@gmail.com> 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.

6

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.

···

On 2 August 2010 05:22, jeremy Ruten <jeremy.ruten@gmail.com> wrote:

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

On Sun, Aug 1, 2010 at 8:56 PM, skim <skim.la@gmail.com> wrote:

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?

On Sun, Aug 1, 2010 at 17:45, Andrew Wagner <wagner.andrew@gmail.com> 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.

7

Benoit Daloze 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.

···

--
Posted via http://www.ruby-forum.com/\.

8

Benoit Daloze 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)

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)

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.

Kind regards

robert

···

2010/8/2 Brian Candler <b.candler@pobox.com>:

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/