# Optimizing a recursion code over lists

I'm writing three functions which iterate over lists, I want do this recursively, but I think this code is not as efficient as it could be.

def flatten(lst):

if type(lst)==int:
return [lst]
elif lst==[]:
return lst
else:
return sum([flatten(sub) for sub in lst], [])

def size(lst): #counts how many numbers and pairs of parentheses in the list
global cnt
cnt=0
if type(lst)==int:
cnt+=1
return 1

if lst==[]:
cnt+=1
return 1
else:
return (sum([size(sub) for sub in lst])+cnt)

def transform(f, lst):
if lst==[]:
return []
if isinstance(lst,(int,float)):
return f(lst)
else:
return [transform(f,sub) for sub in lst]


The flatten function will not handle any element other than integer or list. A better and simpler way of handling it is using a predefined function flatten.

import compiler.ast as cmp
flatten = cmp.flatten

>>> flatten([1,2,[3,]])
>>> [1,2,3,4]


Now the size function can be rewritten as :

def size(lst):
return len(lst) + sum(
nested_count(l) for l in lst if isinstance(l,list))


I also noticed that you take care of float in transform function and not in (your) flatten function. Please ensure all cases or add catch Exceptions where you expect it.

## flatten

You could try @PranavRaj's suggestion, but that won't work in Python 3, as compiler is deprecated.

This would work in Python 3 too (from this other answer):

def flatten(lst):
for el in lst:
if isinstance(el, collections.Iterable) and not isinstance(el, basestring):
for sub in flatten(el):
yield sub
else:
yield el


## size

I don't really understand what you're doing with the global cnt variable there. Using global variables is usually a sign of bad design, and in your case you're not actually using it for anything, so you can just drop it.

Here's a simpler and more general implementation:

def size(lst):
if isinstance(lst, collections.Iterable) and not isinstance(lst, basestring):
return 1 + sum([size(sub) for sub in lst])
return 1


## transform

Here's a simpler and more general implementation:

def transform(f, lst):
if isinstance(lst, collections.Iterable) and not isinstance(lst, basestring):
return [transform(f, el) for el in lst]
return f(lst)

• When I run the function size you wrote I get this error: NameError: global name 'collections' is not defined – user3369309 May 13 '14 at 7:55