need help on generator...

[Joh]

hello,

i'm trying to understand how i could build following consecutive sets
from a root one using generator :

l = [1,2,3,4]

would like to produce :

[1,2], [2,3], [3,4], [1,2,3], [2,3,4]

but unfortunately can not, i guess i can do it by using sub generator
and maybe enumerate, please if you help could you explain a bit the
trick ? looks like this sub generator thing mess me up.

(i think it should may be also have [1,], [2,], [3,], [1,2,3,4] , and
then be filtered)

bests

[Denis S. Otkidach]

Re: need help on generator...

On 21 Jan 2005 05:58:03 -0800
joh12005@yahoo. fr (Joh) wrote:
[color=blue]
> i'm trying to understand how i could build following consecutive sets
> from a root one using generator :
>
> l = [1,2,3,4]
>
> would like to produce :
>
> [1,2], [2,3], [3,4], [1,2,3], [2,3,4][/color]
[color=blue][color=green][color=darkred]
>>> def consecutive_set s(l):[/color][/color][/color]
.... for i in xrange(2, len(l)):
.... for j in xrange(0, len(l)-i+1):
.... yield l[j:j+i]
....[color=blue][color=green][color=darkred]
>>> list(consecutiv e_sets([1,2,3,4]))[/color][/color][/color]
[[1, 2], [2, 3], [3, 4], [1, 2, 3], [2, 3, 4]]

--
Denis S. Otkidach
http://www.python.ru/ [ru]

[Laszlo Zsolt Nagy]

Re: need help on generator...

Joh wrote:
[color=blue]
>hello,
>
>i'm trying to understand how i could build following consecutive sets
>from a root one using generator :
>
>l = [1,2,3,4]
>
>would like to produce :
>
>[1,2], [2,3], [3,4], [1,2,3], [2,3,4]
>
>[/color]
Do you mean:

[1,2], [2,3], [3,4], [1,2,3], [2,3,4], [1,3,4]


(E.g. all elements in the power set except the empty set, the sets with
one element and the sets with all elements.)
Otherwise, please describe your desired sets in verbal - I cannot see
the point.

[Craig Ringer]

Re: need help on generator...

On Fri, 2005-01-21 at 17:14 +0300, Denis S. Otkidach wrote:[color=blue]
> On 21 Jan 2005 05:58:03 -0800
> joh12005@yahoo. fr (Joh) wrote:
>[color=green]
> > i'm trying to understand how i could build following consecutive sets
> > from a root one using generator :
> >
> > l = [1,2,3,4]
> >
> > would like to produce :
> >
> > [1,2], [2,3], [3,4], [1,2,3], [2,3,4][/color]
>[color=green][color=darkred]
> >>> def consecutive_set s(l):[/color][/color]
> ... for i in xrange(2, len(l)):
> ... for j in xrange(0, len(l)-i+1):
> ... yield l[j:j+i][/color]

Since you have a much faster brain than I (though I ended up with
exactly the same thing barring variable names) and beat me to posting
the answer, I'll post the inevitable awful generator expression version
instead:

consecutive_set s = ( x[offset:offset+s ubset_size]
for subset_size in xrange(2, len(x))
for offset in xrange(0, len(x) + 1 - subset_size) )

--
Craig Ringer

[Francis Girard]

Re: need help on need help on generator...

Hi,

I recently read David Mertz (IBM DeveloperWorks) about generators and got
excited about using lazy constructs in my Python programming.

But besides the fact that generators are either produced with the new "yield"
reserved word or by defining the __new__ method in a class definition, I
don't know much about them.

In particular, I don't know what Python constructs does generate a generator.
I know this is now the case for reading lines in a file or with the new
"iterator" package. But what else ? Does Craig Ringer answer mean that list
comprehensions are lazy ? Where can I find a comprehensive list of all the
lazy constructions built in Python ? (I think that to easily distinguish lazy
from strict constructs is an absolute programmer need -- otherwise you always
end up wondering when is it that code is actually executed like in Haskell).

Thank you

Francis Girard
FRANCE

Le vendredi 21 Janvier 2005 15:38, Craig Ringer a écrit :[color=blue]
> On Fri, 2005-01-21 at 17:14 +0300, Denis S. Otkidach wrote:[color=green]
> > On 21 Jan 2005 05:58:03 -0800
> >
> > joh12005@yahoo. fr (Joh) wrote:[color=darkred]
> > > i'm trying to understand how i could build following consecutive sets
> > > from a root one using generator :
> > >
> > > l = [1,2,3,4]
> > >
> > > would like to produce :
> > >
> > > [1,2], [2,3], [3,4], [1,2,3], [2,3,4]
> > >
> > >>> def consecutive_set s(l):[/color]
> >
> > ... for i in xrange(2, len(l)):
> > ... for j in xrange(0, len(l)-i+1):
> > ... yield l[j:j+i][/color]
>
> Since you have a much faster brain than I (though I ended up with
> exactly the same thing barring variable names) and beat me to posting
> the answer, I'll post the inevitable awful generator expression version
> instead:
>
> consecutive_set s = ( x[offset:offset+s ubset_size]
> for subset_size in xrange(2, len(x))
> for offset in xrange(0, len(x) + 1 - subset_size) )
>
> --
> Craig Ringer[/color]

[Craig Ringer]

Re: need help on generator...

On Fri, 2005-01-21 at 22:38 +0800, Craig Ringer wrote:
[color=blue]
> consecutive_set s = ( x[offset:offset+s ubset_size]
> for subset_size in xrange(2, len(x))
> for offset in xrange(0, len(x) + 1 - subset_size) )[/color]

Where 'x' is list to operate on, as I should've initially noted. Sorry
for the reply-to-self.

I did say "awful" for a reason ;-)

--
Craig Ringer

[Peter Otten]

Re: need help on generator...

Joh wrote:
[color=blue]
> i'm trying to understand how i could build following consecutive sets
> from a root one using generator :
>
> l = [1,2,3,4]
>
> would like to produce :
>
> [1,2], [2,3], [3,4], [1,2,3], [2,3,4]
>
> but unfortunately can not, i guess i can do it by using sub generator
> and maybe enumerate, please if you help could you explain a bit the
> trick ? looks like this sub generator thing mess me up.[/color]

Here is an (untested) variant that accepts any iterable while trying to
remain memory-efficient. This makes it necessary to shuffle the order of
the output a bit.

from itertools import tee, islice

def gen(iterable, start, end):
it = iter(iterable)
while True:
it, a = tee(it)
a = tuple(islice(a, end-1))
for sz in xrange(start, len(a)+1):
yield a[:sz]
it.next()


if __name__ == "__main__":
print list(gen(range( 1, 5), 2, 4))

# prints:
# [(1, 2), (1, 2, 3), (2, 3), (2, 3, 4), (3, 4)]

Peter

[Craig Ringer]

Re: need help on need help on generator...

On Fri, 2005-01-21 at 16:05 +0100, Francis Girard wrote:[color=blue]
> I recently read David Mertz (IBM DeveloperWorks) about generators and
> got excited about using lazy constructs in my Python programming.[/color]

Speaking of totally great articles, and indirectly to lazyness (though
not lazyily evaluated constructs), I was really impressed by this
fantastic article on metaclasses:

http://gnosis.cx/publish/programming/metaclass_1.html

http://gnosis.cx/publish/programming/metaclass_2.html

which shows that they're really just not that hard. That saved me an
IMMENSE amount of utterly tedious coding just recently.
[color=blue]
> But besides the fact that generators are either produced with the new
> "yield" reserved word or by defining the __new__ method in a class
> definition, I don't know much about them.[/color]

They can also be created with a generator expression under Python 2.4. A
generator expression works much like a list comprehension, but returns a
generator instead of a list, and is evaluated lazily. (It also doesn't
pollute the outside namespace with its working variables).
[color=blue][color=green][color=darkred]
>>> print [ x for x in range(1,10)][/color][/color][/color]
[1, 2, 3, 4, 5, 6, 7, 8, 9][color=blue][color=green][color=darkred]
>>> print ( x for x in xrange(1,10) )[/color][/color][/color]
<generator object at 0x401e40ac>[color=blue][color=green][color=darkred]
>>> print list(( x for x in xrange(1,10) ))[/color][/color][/color]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Not the use of xrange above for efficiency in the generator expressions.
These examples are trivial and pointless, but hopefully get the point
across.
[color=blue]
> In particular, I don't know what Python constructs does generate a
> generator.[/color]

As far as I know, functions that use yield, and generator expressions. I
was unaware of the ability to create them using a class with a __new__
method, and need to check that out - I can imagine situations in which
it might be rather handy.

I'm not sure how many Python built-in functions and library modules
return generators for things.
[color=blue]
> I know this is now the case for reading lines in a file or with the
> new "iterator" package. But what else ? Does Craig Ringer answer mean
> that list comprehensions are lazy ?[/color]

Nope, but generator expressions are, and they're pretty similar.
[color=blue]
> Where can I find a comprehensive list of all the lazy constructions
> built in Python ? (I think that to easily distinguish lazy from strict
> constructs is an absolute programmer need -- otherwise you always end
> up wondering when is it that code is actually executed like in
> Haskell).[/color]

I'm afraid I can't help you with that. I tend to take the view that side
effects in lazily executed code are a bad plan, and use lazy execution
for things where there is no reason to care when the code is executed.

--
Craig Ringer

[Francis Girard]

Re: need help on generator...

Le vendredi 21 Janvier 2005 16:06, Craig Ringer a écrit :[color=blue]
> On Fri, 2005-01-21 at 22:38 +0800, Craig Ringer wrote:[color=green]
> > consecutive_set s = ( x[offset:offset+s ubset_size]
> > for subset_size in xrange(2, len(x))
> > for offset in xrange(0, len(x) + 1 - subset_size) )[/color]
>
> Where 'x' is list to operate on, as I should've initially noted. Sorry
> for the reply-to-self.
>
> I did say "awful" for a reason ;-)
>
> --
> Craig Ringer[/color]

First, I think that you mean :

consecutive_set s = [ x[offset:offset+s ubset_size]
for subset_size in xrange(2, len(x))
for offset in xrange(0, len(x) + 1 - subset_size)]

(with square brackets).

Second,

this is not lazy anymore (like Denis S. Otkidach previous answer was) because
the __whole__ list get constructed __before__ any other piece of code have a
chance to execute. The type of consecutive_set s is simply a list, not a
generator.

I'm just trying to understand and obviously I'm missing the point.

Thank you

Francis Girard
FRANCE

[Francis Girard]

Re: need help on need help on generator...

Really, thank you Craig Ringer for your great answer.

[color=blue]
> I'm afraid I can't help you with that. I tend to take the view that side
> effects in lazily executed code are a bad plan, and use lazy execution
> for things where there is no reason to care when the code is executed.[/color]


I completly agree with this. But this is much more true in theory than in
practice. In practice you might end up with big big memory usage with lazy
constructs as the "system" has to store intermediate results (the execution
context in the case of Python). These kinds of phenomena happen all the time
in a language like Haskell -- at least for a beginner like me -- if you don't
pay attention to it ; and this makes the language a lot more difficult to
master. Thus you have to keep an eye on performance even though, in FP, you
shoould just have to "declare" your intentions and let the system manage the
execution path.

[color=blue]
> http://gnosis.cx/publish/programming/metaclass_1.html
> http://gnosis.cx/publish/programming/metaclass_2.html[/color]

Thank you, I'll read that.

Francis Girard
FRANCE

Le vendredi 21 Janvier 2005 16:42, Craig Ringer a écrit :[color=blue]
> On Fri, 2005-01-21 at 16:05 +0100, Francis Girard wrote:[color=green]
> > I recently read David Mertz (IBM DeveloperWorks) about generators and
> > got excited about using lazy constructs in my Python programming.[/color]
>
> Speaking of totally great articles, and indirectly to lazyness (though
> not lazyily evaluated constructs), I was really impressed by this
> fantastic article on metaclasses:
>
> http://gnosis.cx/publish/programming/metaclass_1.html
> http://gnosis.cx/publish/programming/metaclass_2.html
>
> which shows that they're really just not that hard. That saved me an
> IMMENSE amount of utterly tedious coding just recently.
>[color=green]
> > But besides the fact that generators are either produced with the new
> > "yield" reserved word or by defining the __new__ method in a class
> > definition, I don't know much about them.[/color]
>
> They can also be created with a generator expression under Python 2.4. A
> generator expression works much like a list comprehension, but returns a
> generator instead of a list, and is evaluated lazily. (It also doesn't
> pollute the outside namespace with its working variables).
>[color=green][color=darkred]
> >>> print [ x for x in range(1,10)][/color][/color]
>
> [1, 2, 3, 4, 5, 6, 7, 8, 9]
>[color=green][color=darkred]
> >>> print ( x for x in xrange(1,10) )[/color][/color]
>
> <generator object at 0x401e40ac>
>[color=green][color=darkred]
> >>> print list(( x for x in xrange(1,10) ))[/color][/color]
>
> [1, 2, 3, 4, 5, 6, 7, 8, 9]
>
> Not the use of xrange above for efficiency in the generator expressions.
> These examples are trivial and pointless, but hopefully get the point
> across.
>[color=green]
> > In particular, I don't know what Python constructs does generate a
> > generator.[/color]
>
> As far as I know, functions that use yield, and generator expressions. I
> was unaware of the ability to create them using a class with a __new__
> method, and need to check that out - I can imagine situations in which
> it might be rather handy.
>
> I'm not sure how many Python built-in functions and library modules
> return generators for things.
>[color=green]
> > I know this is now the case for reading lines in a file or with the
> > new "iterator" package. But what else ? Does Craig Ringer answer mean
> > that list comprehensions are lazy ?[/color]
>
> Nope, but generator expressions are, and they're pretty similar.
>[color=green]
> > Where can I find a comprehensive list of all the lazy constructions
> > built in Python ? (I think that to easily distinguish lazy from strict
> > constructs is an absolute programmer need -- otherwise you always end
> > up wondering when is it that code is actually executed like in
> > Haskell).[/color]
>
> I'm afraid I can't help you with that. I tend to take the view that side
> effects in lazily executed code are a bad plan, and use lazy execution
> for things where there is no reason to care when the code is executed.
>
> --
> Craig Ringer[/color]

[Craig Ringer]

Re: need help on generator...

On Fri, 2005-01-21 at 16:54 +0100, Francis Girard wrote:
[color=blue]
> First, I think that you mean :
>
> consecutive_set s = [ x[offset:offset+s ubset_size]
> for subset_size in xrange(2, len(x))
> for offset in xrange(0, len(x) + 1 - subset_size)]
>
> (with square brackets).[/color]
[color=blue]
> I'm just trying to understand and obviously I'm missing the point.[/color]

Yep. This:

( x for x in xrange(10) )

will return a generator that calculates things as it goes, while this:

[ x for x in xrange(10) ]

will return a list.

Check out:

http://www.python.org/peps/pep-0289.html

http://docs.python.org/whatsnew/node4.html

http://www.python.org/dev/doc/newstyle/ref/genexpr.html

for details.

--
Craig Ringer

[Francis Girard]

Re: need help on generator...

Thank you,

I immediately download version 2.4, switching from version 2.3.

Francis Girard
FRANCE

Le vendredi 21 Janvier 2005 17:34, Craig Ringer a écrit :[color=blue]
> On Fri, 2005-01-21 at 16:54 +0100, Francis Girard wrote:[color=green]
> > First, I think that you mean :
> >
> > consecutive_set s = [ x[offset:offset+s ubset_size]
> > for subset_size in xrange(2, len(x))
> > for offset in xrange(0, len(x) + 1 - subset_size)]
> >
> > (with square brackets).
> >
> > I'm just trying to understand and obviously I'm missing the point.[/color]
>
> Yep. This:
>
> ( x for x in xrange(10) )
>
> will return a generator that calculates things as it goes, while this:
>
> [ x for x in xrange(10) ]
>
> will return a list.
>
> Check out:
> http://www.python.org/peps/pep-0289.html
> http://docs.python.org/whatsnew/node4.html
> http://www.python.org/dev/doc/newstyle/ref/genexpr.html
> for details.
>
> --
> Craig Ringer[/color]

[Nick Coghlan]

Re: need help on need help on generator...

Francis Girard wrote:[color=blue]
> In particular, I don't know what Python constructs does generate a generator.
> I know this is now the case for reading lines in a file or with the new
> "iterator" package. But what else ? Does Craig Ringer answer mean that list
> comprehensions are lazy ? Where can I find a comprehensive list of all the
> lazy constructions built in Python ? (I think that to easily distinguish lazy
> from strict constructs is an absolute programmer need -- otherwise you always
> end up wondering when is it that code is actually executed like in Haskell).[/color]

I don't think there is a *list* as such, but there are some rules of thumb for
when lazy evaluation will take place (hopefully others will note any cases that
I missed):

1. Iterators (classes with a next() method, and an __iter__ method that returns
'self') are lazily evaluated, as itr.next() is called to retrieve each value. I
think you will find it is this method, rather than __new__ which is relevant to
creating class-based generators. Note that "for x in itr" automatically calls
itr.next() in order to obtain each new value of the loop variable.
This iterator protocol is the basis of lazy evaluation in Python, and is
described here:

http://www.python.org/dev/doc/devel/lib/typeiter.html

2. Iterables (classes with an __iter__ method) will return a lazy iterator via
iter(obj). Actual iterators return themselves from __iter__, so iter(obj) is a
good way to make sure you have an iterator.

3. Generators (functions that use 'yield' instead of 'return') and generator
expressions (like list comprehensions, but without the square brackets) are
simply concise ways of creating iterators.

4. The utility functions in the itertools module generally return iterators
rather than lists (this shouldn't suprise anyone!)

5. Several builtin functions return iterators rather than lists, specifically
xrange(), enumerate() and reversed(). Other builtins that yield sequences
(range(), sorted(), zip()) return lists.

However, be aware that some things which accept any iterable don't take
advantage of the lazy evaluation, and still cause the whole thing to be created
in memory at once - "".join(itr ) is currently one such operation.

The sequence vs iterator distinction is somewhat unfortunate (since it breaks
with TOOWTDI), but completing the transition to an iterator based approach isn't
going to be possible until Python 3.0, when things that currently return lists
can be converted to return iterators (i.e. it has been suggested that the
fundamental construct in Python 3.x should be an iterator just as a list is the
fundamental construct in Python 2.x)

Regards,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Alex Martelli]

Re: need help on need help on generator...

Francis Girard <francis.girard @free.fr> wrote:
...[color=blue]
> But besides the fact that generators are either produced with the new "yield"
> reserved word or by defining the __new__ method in a class definition, I
> don't know much about them.[/color]

Having __new__ in a class definition has nothing much to do with
generators; it has to do with how the class is instantiated when you
call it. Perhaps you mean 'next' (and __iter__)? That makes instances
of the class iterators, just like iterators are what you get when you
call a generator.
[color=blue]
> In particular, I don't know what Python constructs does generate a generator.[/color]

A 'def' of a function whose body uses 'yield', and in 2.4 the new genexp
construct.
[color=blue]
> I know this is now the case for reading lines in a file or with the new
> "iterator" package.[/color]

Nope, besides the fact that the module you're thinking of is named
'itertools': itertools uses a lot of C-coded special types, which are
iterators but not generators. Similarly, a file object is an iterator
but not a generator.
[color=blue]
> But what else ?[/color]

Since you appear to conflate generators and iterators, I guess the iter
built-in function is the main one you missed. iter(x), for any x,
either raises an exception (if x's type is not iterable) or else returns
an iterator.
[color=blue]
> Does Craig Ringer answer mean that list
> comprehensions are lazy ?[/color]

Nope, those were generator expressions.
[color=blue]
> Where can I find a comprehensive list of all the
> lazy constructions built in Python ?[/color]

That's yet a different question -- at least one needs to add the
built-in xrange, which is neither an iterator nor a generator but IS
lazy (a historical artefact, admittedly).

But fortunately Python's built-ins are not all THAT many, so that's
about it.
[color=blue]
> (I think that to easily distinguish lazy
> from strict constructs is an absolute programmer need -- otherwise you always
> end up wondering when is it that code is actually executed like in Haskell).[/color]

Encapsulation doesn't let you "easily distinguish" issues of
implementation. For example, the fact that a file is an iterator (its
items being its lines) doesn't tell you if that's internally implemented
in a lazy or eager way -- it tells you that you can code afile.next() to
get the next line, or "for line in afile:" to loop over them, but does
not tell you whether the code for the file object is reading each line
just when you ask for it, or whether it reads all lines before and just
keeps some state about the next one, or somewhere in between.

The answer for the current implementation, BTW, is "in between" -- some
buffering, but bounded consumption of memory -- but whether that tidbit
of pragmatics is part of the file specs, heh, that's anything but clear
(just as for other important tidbits of Python pragmatics, such as the
facts that list.sort is wickedly fast, 'x in alist' isn't, 'x in adict'
IS...).


Alex

[Alex Martelli]

Re: need help on need help on generator...

Nick Coghlan <ncoghlan@iinet .net.au> wrote:
[color=blue]
> 5. Several builtin functions return iterators rather than lists, specifically
> xrange(), enumerate() and reversed(). Other builtins that yield sequences
> (range(), sorted(), zip()) return lists.[/color]

Yes for enumerate and reversed, no for xrange:
[color=blue][color=green][color=darkred]
>>> xx=xrange(7)
>>> xx.next()[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
AttributeError: 'xrange' object has no attribute 'next'[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

it SHOULD return an iterator, no doubt, but it doesn't (can't, for
backwards compatibility reasons). Neither does it return a list: it
returns "an `xrange' object", a specialized type that's not an iterator,
though it's iterable. It's a type, btw:
[color=blue][color=green][color=darkred]
>>> xrange[/color][/color][/color]
<type 'xrange'>[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

so it's not surprising that calling it returns instances of it
(enumerate and reversed are also types, but *WITH* 'next'...).


Alex