map/filter/reduce/lambda opinions and background unscientific mini-survey

[Tom Anderson]

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.