CODEWITHSUNDEEP
pythontypes
Bryan Head
Bryan Head

Reputation: 12580

Avoiding the use of type() comparisons where polymorphism won't work

I came across the following in How to Think Like a Computer Scientist (here):

def recursive_sum(nested_num_list):
    sum = 0
    for element in nested_num_list:
        if type(element) == type([]):
            sum = sum + recursive_sum(element)
        else:
            sum = sum + element
    return sum

I was shocked by the use of type(element) == type([]). Not only is it bad practice, but this function won't work for any other sequence types. Polymorphism is the typical way of avoiding type comparisons, but can't be used here. How could one avoid the type comparison in such a case? I considered:

def recursive_sum(nested_sum_list):
    sum = 0
    for element in nested_num_list:
        try:
            sum += element
        except TypeError:
            sum += recursive_sum(element)
    return sum

which makes the function applicable to other sequences, but is still kinda gross. Thanks!

Upvotes: 3

Views: 160

Answers (7)

Tom
Tom

Reputation: 2016

Things that are true of a list:

>>> import collections
>>> hasattr(element, '__getitem__')
True
>>> not hasattr(element, 'keys')
True
>>> isinstance(element, collections.Sequence)
True
>>> hasattr(element, '__iter__')
True

Things that are true of a string:

>>> string = '1234'
>>> hasattr(string, '__getitem__')
True
>>> not hasattr(string, 'keys')
True
>>> isinstance(string, collections.Sequence)
True
>>> hasattr(string, '__iter__')
False

Upvotes: 1

Jochen Ritzel
Jochen Ritzel

Reputation: 107676

You were checking if the element can be added to a int, which is not what you wanted.

The try is not bad though: Try to use it as a iterable - if it works then it is a iterable:

def recursive_sum(nested_sum_list):
    sum = 0
    # this raises TypeError if element is not a sequence
    for element in nested_num_list: 
        try:
            sum += recursive_sum(element)
        except TypeError:
            sum += element
    return sum

There is also a typeclass for iterables:

import collections
print isinstance(element, collections.Iterable)

which basically just searches for a __iter__ method.

Upvotes: 0

Andrew Clark
Andrew Clark

Reputation: 208585

The purpose of this function is not to be universally applicable for adding nested structures, it was simply created to illustrate recursion.

Adding more complex sequence type checking, try and except, or the ability to add something other than numbers would make the function less useful as a learning tool for recursion.

That being said, isinstance(element, (list, tuple)) would probably be more appropriate here, and it wouldn't add any complexity.

Upvotes: 0

Boaz Yaniv
Boaz Yaniv

Reputation: 6424

You can check if an element is a sequence by using isinstance(element, collections.Sequence).

Upvotes: 3

utdemir
utdemir

Reputation: 27236

"sum" functions takes an iterable, so I would check the element implements the __iter__ method or not,using "hasattr" builtin function.

Like this:

def recursive_sum(nested_num_list):
    sum = 0
    for element in nested_num_list:
        if hasattr(element, '__iter__'):
            sum = sum + recursive_sum(element)
        else:
            sum = sum + element
    return sum

Upvotes: 2

Eli Bendersky
Eli Bendersky

Reputation: 273676

What you see here isn't polymorphism in any language I know. += for lists means one thing, for numbers another thing. You'd like += for lists to mean something unusual (sum up all elements and return the sum) - but this is only meaningful for your specific example. For other (most, I'd say) uses of lists, the original meaning of += is much more convenient.

To make this behave truly polymorphically, you can derive from list and make += mean what you want - then you won't need these hacks.

BTW:

if type(element) == type([]):

Should be rewritten to:

if isinstance(element, list):

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 602315

For the flattening of an aribtrarily nested list, you will always need some kind of check to test if an element is itself an iterable or a leaf node. I wouldn't combine the flattening with computing the sum in one function, but rather define a generator function that only does the flattening:

def flatten(x):
    try:
        it = iter(x)
    except TypeError:
        yield x
    else:
        for i in it:
            for j in flatten(i):
                yield j

This way, you will have all the ugly bits contained in a single function. For a nested sequence x, you can now do

sum(flatten(x))

to get the recursive sum.

Upvotes: 1

Related Questions