Python 2.2 alpha - generators test

[Tim Peters]

[Steve Horne]
> I've been playing with the Python 2.2 alpha, found it to be pretty
> reliable so far, and I've fallen in love with the iterators and
> generators. However, I did find what I think is a problem in the
> test_generators.py (sorry if the filenames slightly wrong) file.

By definition, if test_generators.py passes, there are no problems <wink>.

> I was looking at the 2**i * 3**j * 5**k problem, and decided to try my
> own approach. I reached a point where I needed essentially a
> duplicate-removing priority queue (if such a thing exists) but I
> couldn't be bothered revising my heap theory so temporarily I decided
> to just merge the new items into a simple ordered list.
>
> I remembered a generator called merge or xmerge or something, and
> decided to borrow that to get the initial version running quickly.
>
> Trouble is, it didn't work at all.
>
> Looking back at the merge function, I realised that when either one of
> the input generators is exhausted the generator terminates immediately
> - it does not pass on the remaining items from the other generator. In
> fact, if one of the input generators ends immediately (empty list), no
> items will be output at all irrespective of the number of items the
> other generator could generate.
>
> I'm not sure of the implications in the algorithm it was used in
> (which I didn't fully understand), but it is certainly incorrect for
> merging two ordered sequences - which is what it appeared to be - and
> is certainly what caused my problems.
>
> Is this a real bug, or just a case of me jumping to daft conclusions
> about what the generator was meant to do?

The merge in test_generators was specifically written for the test case at
hand.  It assumes both input streams are:  (a) unbounded; and, (b)
non-decreasing.  When programming with infinite streams (the appropriate way
to view this part of the test), #a is an utterly conventional assumption.
Indeed, one of the joys of working with unbounded streams is that you don't
have to clutter up your logic with termination tests.  You *do* have to
worry about whether stream algorithms can always make progress, and #b isn't
actually strong enough on its own to guarantee that.  But it's a test case,
not a stream tutorial <wink>.