From: martindemello@... (Martin DeMello)
Date: 2002-11-19T21:49:18+09:00
Subject: Thoughts on generators

I've been looking through the generator threads in the archive, and
they all seem to centre around the problem of converting an internal
iterator to an external iterator. This would be a wonderful thing, I
admit, but so far there's been no time and space efficient way to do
it (as far as I've seen, you either need to dump the enumerable to an
array, or use call/cc).

Leaving aside the general problem for the minute, it might be useful
to see where we *can* efficiently write

  g = SimpleGenerator.new(a) # should be space-efficient
  i = g.next # should be O(1) and cheap
  
and where the generator iterates over the sequence nondestructively,
so that it is threadsafe. One could use g.val rather than g.next,
depending on how you think of it.

SimpleGenerator.new would most likely need to be a factory that
instantiated more specific per-type generators. Some easy examples for
generator-generating objects:
- arrays and other structures that support a[i] where i is an integer
(initialize sets @i = -1, and .next does an @i+=1, @array[@i].dup)
- functions on integers (.next returns f(@i))
- sequences where f[i+1] = g(f[i], f[i-1], ..) and which don't depend
on too large a history (the Fibonacci sequence, e.g., or a random
number generator)
- generator-only structures like unbounded lists and circular arrays

Another nice possibility is built-in support for parallel iteration on
generatable structures:

gen = SimpleGenerator.new (a,b,c,d) {|a,b,c,d| [[a,b],c+d]]}

where gen.next returns [a.next,b.next,c.next,d.next] if no block is
given, and passes it into the block if it is. The arguments could be
automatically converted to generators if they were of some generatable
type, which allows freely mixing generatables and anything else
responding to .next. Of course, this runs into the same problems as
zip does when one of the generators runs out before the others do.

Further ideas:

Composition:
- g1 +  g2 returns a generator that iterates over first g1 and then g2
- g1 || g2 iterates in parallel over g1 and g2 (confusable with or?
better name?
perhaps [g1,g2] would be clearer, but we can overload
SimpleGenerator#|| and not just plain [], so it'd be
  gen = SimpleGenerator.create([g1+g2, g3+g4]) versus 
  gen = (g1+g2)||(g3+g4)

Filtering: have an optional filter function (via .filter), so that
next calls itself repeatedly until the filter succeeds.

#each: converting an external to an internal iterator is fairly
trivial, though there would, of course, be issues with circular and
infinite generators.

Implementation shouldn't be too hard - I'll put something up on the
wiki when I get a free moment. Comments? Has anyone done something
like this already?

martin