Recursive list comprehension

**Adam DePrince** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

On Wed, 2004-12-08 at 15:02, Steven Bethard wrote:[color=blue]
> Adam DePrince wrote:[color=green]
> > def flatten( i ):
> > try:
> > i = i.__iter__()
> > while 1:
> > j = flatten( i.next() )
> > try:
> > while 1:
> > yield j.next()
> > except StopIteration:
> > pass
> > except AttributeError:
> > yield i[/color]
>
>
> Probably you want to catch a TypeError instead of an AttributeError;
> objects may support the iterator protocol without defining an __iter__
> method:
>[color=green][color=darkred]
> >>> class C:[/color][/color]
> ... def __getitem__(sel f, index):
> ... if index > 3:
> ... raise IndexError(inde x)
> ... return index
> ...[color=green][color=darkred]
> >>> list(iter(C()))[/color][/color]
> [0, 1, 2, 3]
>
> I would write your code as something like:
>[color=green][color=darkred]
> >>> def flatten(i):[/color][/color]
> ... try:
> ... if isinstance(i, basestring):
> ... raise TypeError('stri ngs are atomic')
> ... iterable = iter(i)
> ... except TypeError:
> ... yield i
> ... else:
> ... for item in iterable:
> ... for sub_item in flatten(item):
> ... yield sub_item
> ...[color=green][color=darkred]
> >>> list(flatten([['N','F'],['E'],['D']]))[/color][/color]
> ['N', 'F', 'E', 'D'][color=green][color=darkred]
> >>> list(flatten([C(), 'A', 'B', ['C', C()]]))[/color][/color]
> [0, 1, 2, 3, 'A', 'B', 'C', 0, 1, 2, 3]
>
> Note that I special-case strings because, while strings support the
> iterator protocol, in this case we want to consider them 'atomic'. By
> catching the TypeError instead of an AttributeError, I can support
> old-style iterators as well.[/color]

Of course, iter( "a" ).next() is "a" -- if you don't look for the
special case of a string you will spin until you blow your stack. The
problem with a special case is it misses objects that have string like
behavior but are not members of basestring. This change deals with that
case, albeit at the expense of some performance (it adds a small
O(depth) factor)).

def flatten(i, history=[]):
try:
if reduce( lambda x,y:x or y, map( lambda x:i is x, history ),\
False ):
raise TypeError('Dej' )
iterable = iter(i)
except TypeError:
yiel>>> list(flatten([C(), 'A', 'B', ['C', C()]]))[color=blue]
> [0, 1, 2, 3, 'A', 'B', 'C', 0, 1, 2, 3]
>
> Note that I special-case strings because, while strings support the
> iterator protocol, in this case we want to consider them 'atomic'. By
> catching the TypeError instead of an AttributeError, I can support
> old-style iterators as well.[/color]

Of course, iter( "a" ).next() is "a" -- if you don't look for the
special case of a string you will spin until you blow your stack. The
problem with a special case is it misses objects that have string like
behavior but are not members of basestring. This change deals with that
case, albeit at the expense of some performance (it adds a small
O(depth) factor)).

def flatten(i, history=[]):
try:
if isinstance( i,basestring) or reduce( lambda x,y:x or y, map(
lambda x:i is x, history ),\ False ):
raise TypeError('stri ngs are atomic' )
iterable = iter(i)
except TypeError:
yield i
else:
history = history + [i]
for item in iterable:
for sub_item in flatten(item, history ):
yield sub_item

if __name__ == "__main__":
print list( flatten( a ) )
print list( flatten( b ) )
print list( flatten( c ) )

[color=blue]
>
> Steve[/color]
Adam DePrince

**Steven Bethard** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

Adam DePrince wrote:[color=blue]
> On Wed, 2004-12-08 at 15:02, Steven Bethard wrote:[color=green]
>>Note that I special-case strings because, while strings support the
>>iterator protocol, in this case we want to consider them 'atomic'. By
>>catching the TypeError instead of an AttributeError, I can support
>>old-style iterators as well.[/color]
>
> Of course, iter( "a" ).next() is "a" -- if you don't look for the
> special case of a string you will spin until you blow your stack. The
> problem with a special case is it misses objects that have string like
> behavior but are not members of basestring.[/color]

Yup. Unfortunately, there's no "string protocol" like there's an
"iterator protocol" or we could check this kind of thing easier. Seems
like your history check might be the best option if you need to support
this kind of thing.

Steve

**Terry Reedy** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

"Steven Bethard" <steven.bethard @gmail.com> wrote in message
news:o5Jtd.2249 74$R05.24953@at tbi_s53...[color=blue]
> Probably you want to catch a TypeError instead of an AttributeError;
> objects may support the iterator protocol without defining an __iter__
> method:[/color]

No, having an __iter__ method that returns an iterator is an essential half
of the current iterator protocol just so that iter(iterator) (==
iterator.__iter __()) always works. This requirement conveniently makes
'iterator' a subcategory of 'iterable'. (I am ignoing the old and obsolete
getnext protocol, as does the itertools library module.)

Terry J. Reedy

**Steven Bethard** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

Terry Reedy wrote:[color=blue]
> "Steven Bethard" <steven.bethard @gmail.com> wrote in message
> news:o5Jtd.2249 74$R05.24953@at tbi_s53...
>[color=green]
>>Probably you want to catch a TypeError instead of an AttributeError;
>>objects may support the iterator protocol without defining an __iter__
>>method:[/color]
>
>
> No, having an __iter__ method that returns an iterator is an essential half
> of the current iterator protocol just so that iter(iterator) (==
> iterator.__iter __()) always works. This requirement conveniently makes
> 'iterator' a subcategory of 'iterable'.[/color]

Yeah, you're right, I probably should have referred to it as the
'iterable protocol' instead of the 'iterator protocol'.
[color=blue]
> (I am ignoing the old and obsolete
> getnext protocol, as does the itertools library module.)[/color]

What is the getnext protocol? Is that the same thing that the iter()
docs call the sequence protocol? Because this definitely still works
with itertools:
[color=blue][color=green][color=darkred]
>>> class C:[/color][/color][/color]
.... def __getitem__(sel f, index):
.... if index > 3:
.... raise IndexError(inde x)
.... return index
....[color=blue][color=green][color=darkred]
>>> import itertools
>>> list(itertools. imap(str, C()))[/color][/color][/color]
['0', '1', '2', '3']

Steve

**Terry Reedy** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

"Steven Bethard" <steven.bethard @gmail.com> wrote in message
news:LoNtd.4653 10$wV.295778@at tbi_s54...[color=blue]
> What is the getnext protocol? Is that the same thing that the iter()
> docs call the sequence protocol?[/color]

Yes. (I meant to write getitem rather than getnext.)
[color=blue]
> Because this definitely still works with itertools:[/color]

Yes, not because itertools are cognizant of sequence objects but because
itertools apply iter() to inputs and because iter() currently accomodates
sequence-protocol objects as well as iterable-protocol objects by wrapping
the former with builtin <iterator> objects. I expect that may change if
and when the builtin C-coded types are updated to have __init__ methods.
This is a ways off, if ever, but I think the general advice for user code
is to use the newer protocol. So, for the purpose of writing new code, I
think it justified to forget about or at least ignore the older iteration
protocol.

Terry J. Reedy

**Steven Bethard** · Jul 18 '05, 06:29 PM

Re: Recursive list comprehension

Terry Reedy wrote:[color=blue]
> This is a ways off, if ever, but I think the general advice for user code
> is to use the newer protocol.[/color]

Yes, definitely. I hope no one misconstrued me to be suggesting that
you should use the 'sequence protocol' for iterators (e.g. using
__getitem__ and raising an IndexError). This is deprecated and is only
supported for backwards compatiblity. All new code should define
__iter__ instead.
[color=blue]
> So, for the purpose of writing new code, I
> think it justified to forget about or at least ignore the older iteration
> protocol.[/color]

This is probably valid as long as you don't need your code to work with
any objects defined before the __iter__ protocol.

Steve

**Nick Craig-Wood** · Jul 18 '05, 06:30 PM

Re: Recursive list comprehension

Peter Otten <__peter__@web. de> wrote:[color=blue]
> Adam DePrince wrote:
>[color=green]
> > def flatten( i ):
> > try:
> > i = i.__iter__()
> > while 1:
> > j = flatten( i.next() )
> > try:
> > while 1:
> > yield j.next()
> > except StopIteration:
> > pass
> > except AttributeError:
> > yield i[/color]
>
> While trying to break your code with a len() > 1 string I noted that strings
> don't feature an __iter__ attribute. Therefore obj.__iter__() is not
> equivalent to iter(obj) for strings. Do you (plural) know whether this is a
> CPython implementation accident or can be relied upon?[/color]

I'd like to know this too!

You can write the above as the shorter (and safer IMHO - it doesn't
catch any exceptions it shouldn't)

def flatten( i ):
if hasattr(i, "__iter__") :
for j in i:
for k in flatten(j):
yield k
else:
yield i

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

Recursive list comprehension

Comment

Comment

Comment

Comment

Comment

Comment

Comment