Geniterator? / Re: (infinite) sequences using recurrence relations

From: Eric Ford (eford_at_[hidden])
Date: 2001-08-06 00:54:32

> The examples aren't that clear either.  It looks like an overly-complex
> variant of the "geniterator" idea (which I posted about a few hours
ago).  I
> don't think you gain anything, besides complexity, from splitting
stuff up
> through several classes.

Sorry. I hadn't noticed your geniterator post, since I didn't
recognize the subject as being something I'd be interested in.  Yes,
the idea is similar.  

I'm sure my first implementation isn't the best.  I was hoping people
could make suggestions.  You mention the complexity issue.  That's
definitely a real issue.  If it's too complex to use, people won't use
it.  Personally, I don't mind if a single class someone writes one is
complex, as long as it's easy to use.  That's my goal.  

Based on my initial musing, I thought that there should be four
elements: state, recurrence relation, geniterator (to adopt your
terminology), and sequence.  At least as I'm thinking, a geniterator
needs to know both the current state and how to generate additional
elements (recurrence relation).  I like the idea of separating those
into three separate classes.  Originally, I was hoping that by
separating the state and the recurrence relation into separate
classes, there could be some additional code reuse.  However, if that
doesn't pan out, I might change my mind to prefer combining the state
and recurrence relation classes into one.

Since it would be nice if the geniterator could be used as an iterator
as much as possible, the geniterator class will probably need to be
thought could carefully.   On the plus side, once a generic
geniterator class written once (maybe a few versions), a user would
only need to pass in classes specifying the state and the recurrence
relation.  While I'm certainly not attached to my particular
implementation, I think that it's worth adding some complexity to a
generic geniterator if it can simplify the process of creating
particular geniterators.  

I also think it would be useful to have a few versions.  Like you
mentioned, it would probably be useful to have a few variations of
geniterators:  forward geniterators, bidirectional geniterators, and
random access geniterators.  Also of possible interest would be a
"regular" version (non-cacheing, like we've written) and a caching
version (that would memoize the values of some or all previously
generated elements).

Your fionacci class is nice and considerablely simpler than the
combination of my recurrent_iterator, recurrent_sequence,
fibonacci_state, and fibonacci_recurrence_relation classes.  However,
I'd say that if you just consider my fibonacci_state and
fibonacci_recurrence_relation classes, then that combination is
simpler than your larger single class.  (Of course, I may be biased.
:) )  More importantly, I suspect that a design that separated the
state and recurrence relation from a generic geniterator class would
help keep the complexity down as the state and recurrence relations
became more complicted.  

>The sequences would be like input iterators, except they don't have
an end
>element.  Support for ends could be added if easy to implement, and
we would
>need operators == and != (and maybe <, >, <=, and >=) for comparisons.
You also mentioned the end problem.  (For bidirectional sequences
infinite in each direction, there's also a begin problem.)  I think
the begin and end problems don't really apply to a geniterator itself.
 An stl iterator does not have a begin or end member.  An stl forward
container does have a begin and end.  So I think the begin and end
problem shows up when you want to create a "container using a
geniterator" (the best name I've come up with is recurrent sequence).
        I think it's would probably a good idea to keep the
geniterator concept separate from the recurrent sequence concept.

As for variations on the recurrent sequence idea, I think there would
be value in having a finite recurrent sequence (has both a begin and
an end), (semi) infinite recurrent sequence (has a begin, but no end),
and bi-infinite recurrent sequence (has neither a begin or an end).
Eric