need help on generator...

[Bengt Richter]

Re: Classical FP problem in python : Hamming problem

On 25 Jan 2005 08:30:03 GMT, Nick Craig-Wood <nick@craig-wood.com> wrote:
[color=blue]
>Francis Girard <francis.girard @free.fr> wrote:[color=green]
>> def hamming():
>> def _hamming():
>> yield 1
>> hamming2 = hammingGenerato rs[0]
>> hamming3 = hammingGenerato rs[1]
>> hamming5 = hammingGenerato rs[2]
>> for n in imerge(imap(lam bda h: 2*h, iter(hamming2)) ,
>> imerge(imap(lam bda h: 3*h, iter(hamming3)) ,
>> imap(lambda h: 5*h, iter(hamming5)) )):
>> yield n
>> hammingGenerato rs = tee(_hamming(), 4)
>> return hammingGenerato rs[3][/color]
>
>If you are after readability, you might prefer this...
>
>def hamming():
> def _hamming():
> yield 1
> for n in imerge(imap(lam bda h: 2*h, iter(hamming2)) ,
> imerge(imap(lam bda h: 3*h, iter(hamming3)) ,
> imap(lambda h: 5*h, iter(hamming5)) )):
> yield n
> hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
> return result
>
>PS interesting thread - never heard of Hamming sequences before![/color]

Are the long words really that helpful?

def hamming():
def _hamming():
yield 1
for n in imerge(imap(lam bda h: 2*h, iter(hg2)),
imerge(imap(lam bda h: 3*h, iter(hg3)),
imap(lambda h: 5*h, iter(hg5)))):
yield n
hg2, hg3, hg5, result = tee(_hamming(), 4) # four hamming generators
return result

Regards,
Bengt Richter

[Nick Craig-Wood]

Re: Classical FP problem in python : Hamming problem

Francis Girard <francis.girard @free.fr> wrote:[color=blue]
> The following implementation is even more speaking as it makes self-evident
> and almost mechanical how to translate algorithms that run after their tail
> from recursion to "tee" usage :
>
> *** BEGIN SNAP
> from itertools import tee, imap
> import sys
>
> def imerge(xs, ys):
> x = xs.next()
> y = ys.next()
> while True:
> if x == y:
> yield x
> x = xs.next()
> y = ys.next()
> elif x < y:
> yield x
> x = xs.next()
> else:
> yield y
> y = ys.next()[/color]

Thinking about this some more leads me to believe a general purpose
imerge taking any number of arguments will look neater, eg

def imerge(*generat ors):
values = [ g.next() for g in generators ]
while True:
x = min(values)
yield x
for i in range(len(value s)):
if values[i] == x:
values[i] = generators[i].next()
[color=blue]
> def hamming():
> def _hamming():
> yield 1
> hamming2 = hammingGenerato rs[0]
> hamming3 = hammingGenerato rs[1]
> hamming5 = hammingGenerato rs[2]
> for n in imerge(imap(lam bda h: 2*h, iter(hamming2)) ,
> imerge(imap(lam bda h: 3*h, iter(hamming3)) ,
> imap(lambda h: 5*h, iter(hamming5)) )):
> yield n
> hammingGenerato rs = tee(_hamming(), 4)
> return hammingGenerato rs[3][/color]

This means that this can be further simplified thus,

def hamming():
def _hamming():
yield 1
for n in imerge( imap(lambda h: 2*h, hamming2),
imap(lambda h: 3*h, hamming3),
imap(lambda h: 5*h, hamming5) ):
yield n
hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
return result

(Note the iter(...) seemed not to be doing anything useful so I
removed them)

--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick

[Steven Bethard]

Re: Classical FP problem in python : Hamming problem

Nick Craig-Wood wrote:[color=blue]
> Thinking about this some more leads me to believe a general purpose
> imerge taking any number of arguments will look neater, eg
>
> def imerge(*generat ors):
> values = [ g.next() for g in generators ]
> while True:
> x = min(values)
> yield x
> for i in range(len(value s)):
> if values[i] == x:
> values[i] = generators[i].next()
>[/color]

This kinda looks like it dies after the first generator is exhausted,
but I'm not certain. An alternate version that doesn't search for 'i':

py> def imerge(*iterabl es):
.... iters = [iter(i) for i in iterables]
.... values = [i.next() for i in iters]
.... while iters:
.... x, i = min((val, i) for i, val in enumerate(value s))
.... yield x
.... try:
.... values[i] = iters[i].next()
.... except StopIteration:
.... del iters[i]
.... del values[i]
....
py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
py> list(imerge([3, 6, 9], [1, 4, 7], [2, 5, 8]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
py> list(imerge([1, 4, 7], [3, 6, 9], [2, 5, 8]))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[color=blue]
> This means that this can be further simplified thus,
>
> def hamming():
> def _hamming():
> yield 1
> for n in imerge( imap(lambda h: 2*h, hamming2),
> imap(lambda h: 3*h, hamming3),
> imap(lambda h: 5*h, hamming5) ):
> yield n
> hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
> return result[/color]

Nice.

Steve

[Nick Craig-Wood]

Re: Classical FP problem in python : Hamming problem

Steven Bethard <steven.bethard @gmail.com> wrote:[color=blue]
> Nick Craig-Wood wrote:[color=green]
> > Thinking about this some more leads me to believe a general purpose
> > imerge taking any number of arguments will look neater, eg
> >
> > def imerge(*generat ors):
> > values = [ g.next() for g in generators ]
> > while True:
> > x = min(values)
> > yield x
> > for i in range(len(value s)):
> > if values[i] == x:
> > values[i] = generators[i].next()
> >[/color]
>
> This kinda looks like it dies after the first generator is exhausted,
> but I'm not certain.[/color]

Yes it will stop iterating then (rather like zip() on lists of unequal
size). Not sure what the specification should be! It works for the
hamming problem though.
[color=blue][color=green][color=darkred]
>>> list(imerge(ite r([1, 2]), iter([1, 2, 3]), iter([1, 2, 3, 4])))[/color][/color][/color]
[1, 2]
[color=blue]
> An alternate version that doesn't search for 'i':
>
> py> def imerge(*iterabl es):
> ... iters = [iter(i) for i in iterables]
> ... values = [i.next() for i in iters]
> ... while iters:
> ... x, i = min((val, i) for i, val in enumerate(value s))
> ... yield x
> ... try:
> ... values[i] = iters[i].next()
> ... except StopIteration:
> ... del iters[i]
> ... del values[i]
> ...
> py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
> [1, 2, 3, 4, 5, 6, 7, 8, 9]
> py> list(imerge([3, 6, 9], [1, 4, 7], [2, 5, 8]))
> [1, 2, 3, 4, 5, 6, 7, 8, 9]
> py> list(imerge([1, 4, 7], [3, 6, 9], [2, 5, 8]))
> [1, 2, 3, 4, 5, 6, 7, 8, 9][/color]

This isn't quite right...
[color=blue][color=green][color=darkred]
>>> list(imerge([1, 2, 3], [1, 2, 3], [1, 2, 3]))[/color][/color][/color]
[1, 1, 1, 2, 2, 2, 3, 3, 3]

This should produce
[1, 2, 3]

So I'm afraid the searching *is* necessary - you've got to find all
the generators with the min value and move them on.

--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick

[Steven Bethard]

Re: Classical FP problem in python : Hamming problem

Nick Craig-Wood wrote:[color=blue]
> Steven Bethard <steven.bethard @gmail.com> wrote:
>[color=green]
>> Nick Craig-Wood wrote:
>>[color=darkred]
>>>Thinking about this some more leads me to believe a general purpose
>>>imerge taking any number of arguments will look neater, eg
>>>
>>>def imerge(*generat ors):
>>> values = [ g.next() for g in generators ]
>>> while True:
>>> x = min(values)
>>> yield x
>>> for i in range(len(value s)):
>>> if values[i] == x:
>>> values[i] = generators[i].next()
>>>[/color]
>>
>> This kinda looks like it dies after the first generator is exhausted,
>> but I'm not certain.[/color]
>
>
> Yes it will stop iterating then (rather like zip() on lists of unequal
> size). Not sure what the specification should be! It works for the
> hamming problem though.[/color]

Actually, it stops iterating on lists of equal size too:

py> def imerge(*iterato rs):
.... iterators = [iter(i) for i in iterators]
.... values = [i.next() for i in iterators]
.... while True:
.... x = min(values)
.... yield x
.... for i, val in enumerate(value s):
.... if val == x:
.... values[i] = iterators[i].next()
....
py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
[1, 2, 3, 4, 5, 6, 7]

Note that 8 and 9 are not in the list.

Steve

[Michael Spencer]

Re: Classical FP problem in python : Hamming problem

Nick Craig-Wood wrote:[color=blue]
> Steven Bethard <steven.bethard @gmail.com> wrote:
>[color=green]
>> Nick Craig-Wood wrote:
>>[color=darkred]
>>>Thinking about this some more leads me to believe a general purpose
>>>imerge taking any number of arguments will look neater, eg
>>>
>>>def imerge(*generat ors):
>>> values = [ g.next() for g in generators ]
>>> while True:
>>> x = min(values)
>>> yield x
>>> for i in range(len(value s)):
>>> if values[i] == x:
>>> values[i] = generators[i].next()
>>>[/color]
>>
>> This kinda looks like it dies after the first generator is exhausted,
>> but I'm not certain.[/color]
>
>
> Yes it will stop iterating then (rather like zip() on lists of unequal
> size). Not sure what the specification should be! It works for the
> hamming problem though.
>
>[color=green][color=darkred]
>>>>list(imerge (iter([1, 2]), iter([1, 2, 3]), iter([1, 2, 3, 4])))[/color][/color]
>
> [1, 2]
>
>[color=green]
>>An alternate version that doesn't search for 'i':
>>
>> py> def imerge(*iterabl es):
>> ... iters = [iter(i) for i in iterables]
>> ... values = [i.next() for i in iters]
>> ... while iters:
>> ... x, i = min((val, i) for i, val in enumerate(value s))
>> ... yield x
>> ... try:
>> ... values[i] = iters[i].next()
>> ... except StopIteration:
>> ... del iters[i]
>> ... del values[i]
>> ...
>> py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
>> [1, 2, 3, 4, 5, 6, 7, 8, 9]
>> py> list(imerge([3, 6, 9], [1, 4, 7], [2, 5, 8]))
>> [1, 2, 3, 4, 5, 6, 7, 8, 9]
>> py> list(imerge([1, 4, 7], [3, 6, 9], [2, 5, 8]))
>> [1, 2, 3, 4, 5, 6, 7, 8, 9][/color]
>
>
> This isn't quite right...
>
>[color=green][color=darkred]
>>>>list(imerge ([1, 2, 3], [1, 2, 3], [1, 2, 3]))[/color][/color]
>
> [1, 1, 1, 2, 2, 2, 3, 3, 3]
>
> This should produce
> [1, 2, 3]
>
> So I'm afraid the searching *is* necessary - you've got to find all
> the generators with the min value and move them on.
>[/color]
Here's a dict-based implementation: cute, but slow, at least for a small number
of iterators
[color=blue][color=green][color=darkred]
>>> def imerge(*iterabl es):[/color][/color][/color]
... cache = {}
... iterators = map(iter,iterab les)
... number = len(iterables)
... exhausted = 0
... while 1:
... for it in iterators:
... try:
... cache.setdefaul t(it.next(),[]).append(it)
... except StopIteration:
... exhausted += 1
... if exhausted == number:
... raise StopIteration
... val = min(cache)
... iterators = cache.pop(val)
... yield val
[color=blue][color=green][color=darkred]
>>> list(imerge([1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 4, 5]))[/color][/color][/color]
[1, 2, 3, 4, 5, 6, 7][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Michael

[Jeff Shannon]

Re: Classical FP problem in python : Hamming problem

Bengt Richter wrote:
[color=blue]
> On 25 Jan 2005 08:30:03 GMT, Nick Craig-Wood <nick@craig-wood.com> wrote:
>[color=green]
>>If you are after readability, you might prefer this...
>>
>>def hamming():
>> def _hamming():
>> yield 1
>> for n in imerge(imap(lam bda h: 2*h, iter(hamming2)) ,
>> imerge(imap(lam bda h: 3*h, iter(hamming3)) ,
>> imap(lambda h: 5*h, iter(hamming5)) )):
>> yield n
>> hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
>> return result[/color]
>
> Are the long words really that helpful?
>
> def hamming():
> def _hamming():
> yield 1
> for n in imerge(imap(lam bda h: 2*h, iter(hg2)),
> imerge(imap(lam bda h: 3*h, iter(hg3)),
> imap(lambda h: 5*h, iter(hg5)))):
> yield n
> hg2, hg3, hg5, result = tee(_hamming(), 4) # four hamming generators
> return result[/color]

Well, judging by the fact that shortening the identifiers made it so
that you felt the need to add a comment indicating what they were
identifying, I'd say that yes, the long words *are* helpful. ;)
Comments are good, but self-documenting code is even better.

Jeff Shannon
Technician/Programmer
Credit International

[Bengt Richter]

Re: Classical FP problem in python : Hamming problem

On Tue, 25 Jan 2005 11:46:04 -0800, Jeff Shannon <jeff@ccvcorp.c om> wrote:
[color=blue]
>Bengt Richter wrote:
>[color=green]
>> On 25 Jan 2005 08:30:03 GMT, Nick Craig-Wood <nick@craig-wood.com> wrote:
>>[color=darkred]
>>>If you are after readability, you might prefer this...
>>>
>>>def hamming():
>>> def _hamming():
>>> yield 1
>>> for n in imerge(imap(lam bda h: 2*h, iter(hamming2)) ,
>>> imerge(imap(lam bda h: 3*h, iter(hamming3)) ,
>>> imap(lambda h: 5*h, iter(hamming5)) )):
>>> yield n
>>> hamming2, hamming3, hamming5, result = tee(_hamming(), 4)
>>> return result[/color]
>>
>> Are the long words really that helpful?
>>
>> def hamming():
>> def _hamming():
>> yield 1
>> for n in imerge(imap(lam bda h: 2*h, iter(hg2)),
>> imerge(imap(lam bda h: 3*h, iter(hg3)),
>> imap(lambda h: 5*h, iter(hg5)))):
>> yield n
>> hg2, hg3, hg5, result = tee(_hamming(), 4) # four hamming generators
>> return result[/color]
>
>Well, judging by the fact that shortening the identifiers made it so
>that you felt the need to add a comment indicating what they were
>identifying, I'd say that yes, the long words *are* helpful. ;)
>Comments are good, but self-documenting code is even better.[/color]

The comment was a conscious factoring decision, in terms of documentation ;-)

Regards,
Bengt Richter

[Francis Girard]

Re: Classical FP problem in python : Hamming problem

Le mardi 25 Janvier 2005 09:01, Michael Spencer a écrit :[color=blue]
> Francis Girard wrote:[color=green]
> > The following implementation is even more speaking as it makes
> > self-evident and almost mechanical how to translate algorithms that run
> > after their tail from recursion to "tee" usage :[/color]
>
> Thanks, Francis and Jeff for raising a fascinating topic. I've enjoyed
> trying to get my head around both the algorithm and your non-recursive
> implementation.
>[/color]

Yes, it's been fun.
[color=blue]
> Here's a version of your implementation that uses a helper class to make
> the algorithm itself prettier.
>
> from itertools import tee, imap
>
> def hamming():
> def _hamming():
> yield 1
> for n in imerge(2 * hamming, imerge(3 * hamming, 5 * hamming)):
> yield n
>
> hamming = Tee(_hamming())
> return iter(hamming)
>
>
> class Tee(object):
> """Provides an indepent iterator (using tee) on every iteration
> request Also implements lazy iterator arithmetic"""
> def __init__(self, iterator):
> self.iter = tee(iterator,1)[0]
> def __iter__(self):
> return self.iter.__cop y__()
> def __mul__(self, number):
> return imap(lambda x: x * number,self.__i ter__())
>
> def imerge(xs, ys):
> x = xs.next()
> y = ys.next()
> while True:
> if x == y:
> yield x
> x = xs.next()
> y = ys.next()
> elif x < y:
> yield x
> x = xs.next()
> else: # if y < x:
> yield y
> y = ys.next()
>[color=green][color=darkred]
> >>> hg = hamming()
> >>> for i in range(10000):[/color][/color]
>
> ... n = hg.next()
> ... if i % 1000 == 0: print i, n
> ...
> 0 1
> 1000 51840000
> 2000 8100000000
> 3000 279936000000
> 4000 4707158941350
> 5000 50960793600000
> 6000 409600000000000
> 7000 263882790666240 0
> 8000 143327232000000 00
> 9000 680244480000000 00
>
>[/color]

Interesting idea.
[color=blue]
> Regards
>
> Michael[/color]

[Francis Girard]

Re: Classical FP problem in python : Hamming problem

Le mardi 25 Janvier 2005 19:52, Steven Bethard a écrit :

Thank you Nick and Steven for the idea of a more generic imerge.

To work with the Hamming problem, the imerge function _must_not_ allow
duplicates and we can assume all of the specified iteratables are of the same
size, i.e. infinite !

Therefore, Nick's solution fulfills the need. But it is admittedly confusing
to call the function "imerge" when it doesn't merge everything (including
duplicates). Anyway both solution sheds new light and brings us a bit
farther.

That's the beauty of many brains from all over the world collabarating.
Really, it makes me emotive thinking about it.

For the imerge function, what we really need to make the formulation clear is
a way to look at the next element of an iteratable without consuming it. Or
else, a way to put back "consumed" elements in the front an iteration flow,
much like the list constructors in FP languages like Haskell.

It is simple to encapsulate an iterator inside another iterator class that
would do just that. Here's one. The additional "fst" method returns the next
element to consume without consuming it and the "isBottom" checks if there is
something left to consume from the iteration flow, without actually consuming
anything. I named the class "IteratorDeiter ator" for lack of imagination :

-- BEGIN SNAP
class IteratorDeitera tor:
def __init__(self, iterator):
self._iterator = iterator.__iter __()
self._firstVal = None ## Avoid consuming if not requested from outside
## Works only if iterator itself can't return None

def __iter__(self): return self

def next(self):
valReturn = self._firstVal
if valReturn is None:
valReturn = self._iterator. next()
self._firstVal = None
return valReturn

def fst(self):
if self._firstVal is None:
self._firstVal = self._iterator. next()
return self._firstVal

def isBottom(self):
if self._firstVal is None:
try: self._firstVal = self._iterator. next()
except StopIteration:
return True
return False
-- END SNAP

Now the imerge_infinite which merges infinite lists, while allowing
duplicates, is quite straightforward :

-- BEGIN SNAP
def imerge_infinite (*iterators):
vItTopable = [IteratorDeitera tor(it) for it in iterators]
while vItTopable:
yield reduce(lambda itSmallest, it:
itSmallest.fst( ) > it.fst() and it or itSmallest,
vItTopable).nex t()
-- END SNAP

To merge finite lists of possibly different lengths is a bit more work as you
have to eliminate iterators that reached the bottom before the others. This
is quite easily done by simply filtering them out.
The imerge_finite function below merges "lists" of possibly different sizes.

-- BEGIN SNAP
def imerge_finite(* iterators):
vItDeit = [IteratorDeitera tor(it) for it in iterators]
vItDeit = filter(lambda it: not it.isBottom(), vItDeit)
while vItDeit:
yield reduce(lambda itSmallest, it:
itSmallest.fst( ) > it.fst() and it or itSmallest,
vItDeit).next()
vItDeit = filter(lambda it: not it.isBottom(), vItDeit)
-- END SNAP


Now, we want versions of these two merge functions that do not allow
duplicates. Building upon what we've already done in a semi FP way, we just
filter out the duplicates from the iteration streams returned by the above
functions. The job is the same for the infinite and finite versions, hence
the imerge_nodup generic function.

-- BEGIN SNAP
def imerge_nodup(fI merge, *iterators):
it = fImerge(*iterat ors)
el = it.next()
yield el
while True:
el = dropwhile(lambd a _next: _next == el, it).next()
yield el

imerge_inf_nodu p = \
lambda *iterators: imerge_nodup(im erge_infinite, *iterators)
imerge_finite_n odup = \
lambda *iterators: imerge_nodup(im erge_finite, *iterators)
-- END SNAP

I used the lambda notation for imerge_inf_nodu p and imerge_finite_n odup to
avoid another useless for-yield loop. Here the notation really just express
function equivalence with a bounded argument (it would be great to have a
notation for this in Python, i.e. binding a function argument to yield a new
function).

The merge function to use with hamming() is imerge_inf_nodu p.

Regards,

Francis Girard
FRANCE
[color=blue]
> Nick Craig-Wood wrote:[color=green]
> > Steven Bethard <steven.bethard @gmail.com> wrote:[color=darkred]
> >> Nick Craig-Wood wrote:
> >>>Thinking about this some more leads me to believe a general purpose
> >>>imerge taking any number of arguments will look neater, eg
> >>>
> >>>def imerge(*generat ors):
> >>> values = [ g.next() for g in generators ]
> >>> while True:
> >>> x = min(values)
> >>> yield x
> >>> for i in range(len(value s)):
> >>> if values[i] == x:
> >>> values[i] = generators[i].next()
> >>
> >> This kinda looks like it dies after the first generator is exhausted,
> >> but I'm not certain.[/color]
> >
> > Yes it will stop iterating then (rather like zip() on lists of unequal
> > size). Not sure what the specification should be! It works for the
> > hamming problem though.[/color]
>
> Actually, it stops iterating on lists of equal size too:
>
> py> def imerge(*iterato rs):
> ... iterators = [iter(i) for i in iterators]
> ... values = [i.next() for i in iterators]
> ... while True:
> ... x = min(values)
> ... yield x
> ... for i, val in enumerate(value s):
> ... if val == x:
> ... values[i] = iterators[i].next()
> ...
> py> list(imerge([1, 4, 7], [2, 5, 8], [3, 6, 9]))
> [1, 2, 3, 4, 5, 6, 7]
>
> Note that 8 and 9 are not in the list.
>
> Steve[/color]

[Steven Bethard]

Re: Classical FP problem in python : Hamming problem

Francis Girard wrote:[color=blue]
> For the imerge function, what we really need to make the formulation clear is
> a way to look at the next element of an iteratable without consuming it. Or
> else, a way to put back "consumed" elements in the front an iteration flow,
> much like the list constructors in FP languages like Haskell.
>
> It is simple to encapsulate an iterator inside another iterator class that
> would do just that. Here's one. The additional "fst" method returns the next
> element to consume without consuming it and the "isBottom" checks if there is
> something left to consume from the iteration flow, without actually consuming
> anything. I named the class "IteratorDeiter ator" for lack of imagination :
>[/color]
[snip]

Another implementation is my peekable class:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/304373

It allows you to peek several elements ahead if that's necessary.

Steve

[Nick Craig-Wood]

Re: Classical FP problem in python : Hamming problem

Francis Girard <francis.girard @free.fr> wrote:[color=blue]
> Thank you Nick and Steven for the idea of a more generic imerge.[/color]

You are welcome :-) [It came to me while walking the children to school!]

[snip][color=blue]
> class IteratorDeitera tor:
> def __init__(self, iterator):
> self._iterator = iterator.__iter __()
> self._firstVal = None ## Avoid consuming if not requested from outside
> ## Works only if iterator itself can't return None[/color]

You can use a sentinel here if you want to avoid the "can't return
None" limitation. For a sentinel you need an object your iterator
couldn't possibly return. You can make one up, eg

self._sentinel = object()
self._firstVal = self._sentinel

Or you could use self (but I'm not 100% sure that your recursive
functions wouldn't return it!)
[color=blue]
> def __iter__(self): return self
>
> def next(self):
> valReturn = self._firstVal
> if valReturn is None:[/color]

and
if valReturn is self._sentinel:
[color=blue]
> valReturn = self._iterator. next()
> self._firstVal = None[/color]

self._firstVal = self._sentinel

etc..

[snip more code]

Thanks for some more examples of fp-style code. I find it hard to get
my head round so its been good exercise!
--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick

[Francis Girard]

Re: Classical FP problem in python : Hamming problem

Le jeudi 27 Janvier 2005 10:30, Nick Craig-Wood a écrit :[color=blue]
> Francis Girard <francis.girard @free.fr> wrote:[color=green]
> > Thank you Nick and Steven for the idea of a more generic imerge.[/color]
>
> You are welcome :-) [It came to me while walking the children to school!]
>[/color]

Sometimes fresh air and children purity is all what it takes. Much better than
coffee, cigarrette and flat screen.
[color=blue]
> [snip]
>[color=green]
> > class IteratorDeitera tor:
> > def __init__(self, iterator):
> > self._iterator = iterator.__iter __()
> > self._firstVal = None ## Avoid consuming if not requested from
> > outside ## Works only if iterator itself can't return None[/color]
>
> You can use a sentinel here if you want to avoid the "can't return
> None" limitation. For a sentinel you need an object your iterator
> couldn't possibly return. You can make one up, eg
>[/color]

Great idea. I'll use it.
[color=blue]
> self._sentinel = object()
> self._firstVal = self._sentinel
>
> Or you could use self (but I'm not 100% sure that your recursive
> functions wouldn't return it!)
>[color=green]
> > def __iter__(self): return self
> >
> > def next(self):
> > valReturn = self._firstVal
> > if valReturn is None:[/color]
>
> and
>
> if valReturn is self._sentinel:[color=green]
> > valReturn = self._iterator. next()
> > self._firstVal = None[/color]
>
> self._firstVal = self._sentinel
>
> etc..
>
> [snip more code]
>
> Thanks for some more examples of fp-style code. I find it hard to get
> my head round so its been good exercise![/color]

Introduction to functional programming
Richard Bird and Philip Wadler
Prentice Hall
1988

This is the very best intro I ever read. The book is without hype, doesn't
show its age and is language neutral.
Authors are world leaders in the field today. Only really strong guys have the
kindness to do understandable introductions without trying to hide the
difficulties (because they are strong enough to face them with simplicity).

It's been a real pleasure.

Regards,

Francis Girard
FRANCE

[color=blue]
> --
> Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick[/color]

[Paul Rubin]

Re: Classical FP problem in python : Hamming problem

Francis Girard <francis.girard @free.fr> writes:[color=blue]
> Thank you Nick and Steven for the idea of a more generic imerge.[/color]

If you want to get fancy, the merge should use a priority queue (like
in the heapsort algorithm) instead of a linear scan through the
incoming iters, to find the next item to output. That lowers the
running time to O(n log k) instead of O(n*k), where k is the number of
iterators and n is the length.

[Michael Spencer]

Re: Classical FP problem in python : Hamming problem

Paul Rubin wrote:[color=blue]
> Francis Girard <francis.girard @free.fr> writes:
>[color=green]
>>Thank you Nick and Steven for the idea of a more generic imerge.[/color]
>
>
> If you want to get fancy, the merge should use a priority queue (like
> in the heapsort algorithm) instead of a linear scan through the
> incoming iters, to find the next item to output. That lowers the
> running time to O(n log k) instead of O(n*k), where k is the number of
> iterators and n is the length.[/color]

I looked at a heapq solution but didn't see any clean way of dealing with
multiple iterators having equal values. The dict solution below deals cleanly
with that, since one key can be shared by any number of iterators. Extracting
the minimum, and the associated iterables is fast, but the overall solution is
still slower than the brute force approach for the 3 hamming iterators.
[color=blue][color=green][color=darkred]
>>> def imerge(*iterabl es):[/color][/color][/color]
... cache = {}
... iterators = map(iter,iterab les)
... number = len(iterables)
... exhausted = 0
... while 1:
# First time through, looked at all of them
# Subsequently, update only the minimum iterators
... for it in iterators:
... try:
# Key each iterator by its next() value
# Multiple iterators may share the same key
... cache.setdefaul t(it.next(),[]).append(it)
... except StopIteration:
... exhausted += 1
... if exhausted == number:
... raise StopIteration
# Get the lowest value
... val = min(cache)
# and all the iterators that have that value
... iterators = cache.pop(val)
... yield val
[color=blue][color=green][color=darkred]
>>> list(imerge([1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 4, 5]))[/color][/color][/color]
[1, 2, 3, 4, 5, 6, 7][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Michael