algorithms and ADTs (was Re: efficient idiomatic queue?)

[Alex Martelli]

"David Eppstein" <eppstein at ics.uci.edu> wrote in message
news:eppstein-C4AE42.20190114012002 at news.service.uci.edu...
    ...
> Actually, the merge step in merge sort is a great example for simple
> generators, or would be if not for the difficulty of keeping track of the
> first item of each input iterator:

So, why not encapsulate that "difficulty"?  E.g.:

class Peeker:
    def __init__(self, iterator_or_sequence):
        self.iterator = iter(iterator_or_sequence)
        self.head = None
        self.advance()
    def advance(self):
        head = self.head
        try: self.head = self.iterator.next()
        except StopIteration: self.more = 0
        else: self.more = 1
        return head

With an ADT such as this one, operations such as merging get simpler:

def merge(A, B):
    A=Peeker(A)
    B=Peeker(B)
    while A.more and B.more:
        if A.head < B.head: yield A.advance()
        else: yield B.advance()
    while A.more: yield A.advance()
    while B.more: yield B.advance()

Note that the sum total of wrapper class Peeker and this merge version
is less than or equal to the merge version that tries to do everything,
in terms of both lines of code and "conceptual load".  Basically, this
is because Peeker "captures" the right "primitive concepts" (attributes
more and head, operation advance) for merge's purposes, and therefore
eliminates duplication present in the "stand-alone version of merge".

One might start with the large, code-duplicating version of merge, and
work towards this one, as a way to motivate ADT's, I guess.  But I'm
not sure such a bottom-up-and-refactor approach is didactically more
valid than top-down-and-refine, although it's closer to how one might
work to develop Peeker in real life.


Alex