Optimizing a recursion code over lists

Question

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]

Answer 1

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,[4]]])
>>> [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.

Answer 2

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)