On Mon, 4 Jul 2005, Ron Adam wrote:
> George Sakkis wrote:
>
>> And finally for recursive flattening:
>>
>> def flatten(seq):
>> return reduce(_accum, seq, [])
>>
>> def _accum(seq, x):
>> if isinstance(x,list):
>> seq.extend(flatten(x))
>> else:
>> seq.append(x)
>> return seq
>>
>>
>>>>> flatten(seq)
>>
>> [1, 2, 3, 4, 5, 6]
>
> How about this for a non recursive flatten.
>
> def flatten(seq):
> s = []
> while seq:
> while isinstance(seq[0],list):
> seq = seq[0]+seq[1:]
> s.append(seq.pop(0))
> return s
>
> seq = [[1,2],[3],[],[4,[5,6]]]
> flatten(seq)
The trouble with these is that they make a lot of temporary lists -
George's version does it with the recursive calls to flatten, and Ron's
with the slicing and concatenating. How about a version which never makes
new lists, only appends the base list? We can use recursion to root
through the lists ...
def isiterable(x):
return hasattr(x, "__iter__") # close enough for government work
def visit(fn, x): # perhaps better called applytoall
if (isiterable(x)):
for y in x: visit(fn, y)
else:
fn(x)
def flatten(seq):
a = []
def appendtoa(x):
a.append(x)
visit(appendtoa, seq)
return a
If you hate recursion, you can write a non-recursive version of visit;
you'll have to manage a stack of lists yourself, though. Something like:
def visit(fn, x):
if (not isiterable(x)): x = (x,)
stack = [None] # stack of iterators
cur = iter(x) # current iterator
while (cur != None):
try:
thing = cur.next()
if (isiterable(thing)):
stack.append(cur)
cur = iter(thing)
else:
fn(thing)
except StopIteration:
cur = stack.pop()
There might be a cleverer way to do this.
tom
--
The revolution will not be televised. The revolution will be live.
--
http://mail.python.org/mailman/listinfo/python-list
