# Sum a nested list of a nested list of a nested list of integers

Given a Python list whose elements are either integers or lists of integers (only we don't know how deep the nesting goes), how can we find the sum of each individual integer within the list?

It's fairly straightforward to find the sum of a list whose nesting only goes one level deep, e.g.

``````[1, [1, 2, 3]]
# sum is 7
``````

But what if the nesting goes two, three, or more levels deep?

``````[1, [1, [2, 3]]]
# two levels deep

[1, [1, [2, [3]]]]
# three levels deep
``````

The sum in each of the above cases is the same (i.e. 7). I think the best approach is using recursion where the base case is a list with a single integer element, but beyond that I'm stuck.

-

You can use this recursive solution:

``````from collections import Iterable
def flatten(collection):
for element in collection:
if isinstance(element, Iterable):
for x in flatten(element):
yield x
else:
yield element
``````

Demo:

``````>>> lis = [1, [1, [2, [3]]]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, 2, 3]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, [2, 3]]]
>>> sum(flatten(lis))
7
``````
-
Curious that something like this is not in `itertools`. – Paul McGuire Jul 1 '13 at 18:31
+1 Looks like this is the preferred solution. My answer will work with Python 2.7.4 but it looks as if compilers.ast has been deprecated. – Captain Skyhawk Jul 1 '13 at 18:54

Easiest way I can think of:

``````from compiler.ast import flatten
sum(flatten(numbs))
``````
-
I think you can just call `sum` directly. But good answer. – squiguy Jul 1 '13 at 18:26
This is working for me just fine. – Captain Skyhawk Jul 1 '13 at 18:47
@CaptainSkyhawk What is `flatten` here? AFAIK there's no built-in function named `flatten`. – Ashwini Chaudhary Jul 1 '13 at 18:49
Sorry, forgot the import – Captain Skyhawk Jul 1 '13 at 18:52
Note that this will work only in py2.x. – Ashwini Chaudhary Jul 1 '13 at 18:53

Assuming that you are only using lists, this should do the trick:

``````def sum_nested(l):
s = 0
for item in l:
if type(item) is list:
s += sum_nested(item)
else:
s += item
return s
``````
-
This one is good because it avoids unnecessary allocations that occur when using `flatten` (in any of the suggested forms). I would change `==` to `is` in the type test though. – android Jul 1 '13 at 18:41
In the real world, though, `sum(flatten(x))` will likely be more performant if `flatten` produces an iterable. – android Jul 1 '13 at 18:44
The PEP Style guide suggests using isinstance(item, list) for all object comparisons. "Object type comparisons should always use isinstance() instead of comparing types directly." Otherwise nice answer. – Dan Jul 1 '13 at 19:58
@android The `flatten` implementation in my answer (as well as Ashwini's) ought not to allocate anything unnecessarily, save for a generator object for a brief period of time (on my system, this is only 80 bytes). @Brien However, I ran your solution through `timeit` with `[1, [1, [2, [3]]]]` (default number of runs) as well as mine and Ashwini's... yours: `2.8680150508880615`; mine: `16.686115026474`; Ashwini's: `14.88997197151184`. Captain Skyhawk's was pretty good as well, for being deprecated: `5.101460933685303`. Yours with `isinstance` instead was `3.312623977661133`. You get my upvote. – 2rs2ts Jul 1 '13 at 20:42
Ah, the reason why our solutions are so slow is the fact that we are using `isinstance(item, Iterable)`. When I change it to `isinstance(item, list)` I get `3.9191691875457764`. The only-lists assumption is a good optimization. – 2rs2ts Jul 1 '13 at 20:47

One approach: flatten the list, then use `sum()`.

``````from collections import Iterable
def flatten(lst):
for i in lst:
if isinstance(i, Iterable) and not isinstance(i, basestring):
for sublst in flatten(i):
yield sublst
else:
yield i

sum(flatten([1, [1, [2, [3]]]]))
``````

If you are dealing only with lists, change `isinstance(i, Iterable)` to `isinstance(i, list)` for a massive performance boost.

Note that the `basestring` check is not necessary when using `sum()` as Ashwini pointed out.

-
No need to handle `basestring`, because if the list contains strings then `sum` will also raise an error. – Ashwini Chaudhary Jul 1 '13 at 18:30
@AshwiniChaudhary Cool. I thought I'd need to look out for that. – 2rs2ts Jul 1 '13 at 18:31
I'm going to leave it in, though, because otherwise our answers are exactly the same. – 2rs2ts Jul 1 '13 at 18:32
The text passage describes a programming problem related to finding the sum of all integers in a deeply nested list structure in Python. It provides a question about how to solve this problem and multiple solutions, including a recursive function and a method using the `flatten` function.
no_question

however, it's worth noting that while the passage does not contain a direct mathematical question, it does contain a programming problem that involves mathematical operations (summing integers). if we were to consider this as a mathematical question, the type would be single_question_with_answer, as the question is posed and multiple answers are provided. but based on the strict definition of a mathematical question, the type is no_question.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Sum a nested list of a nested list of a nested list of integers

Given a Python list whose elements are either integers or lists of integers (only we don't know how deep the nesting goes), how can we find the sum of each individual integer within the list?

It's fairly straightforward to find the sum of a list whose nesting only goes one level deep, e.g.

``````[1, [1, 2, 3]]
# sum is 7
``````

But what if the nesting goes two, three, or more levels deep?

``````[1, [1, [2, 3]]]
# two levels deep

[1, [1, [2, [3]]]]
# three levels deep
``````

The sum in each of the above cases is the same (i.e. 7). I think the best approach is using recursion where the base case is a list with a single integer element, but beyond that I'm stuck.

-

You can use this recursive solution:

``````from collections import Iterable
def flatten(collection):
for element in collection:
if isinstance(element, Iterable):
for x in flatten(element):
yield x
else:
yield element
``````

Demo:

``````>>> lis = [1, [1, [2, [3]]]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, 2, 3]]
>>> sum(flatten(lis))
7
>>> lis = [1, [1, [2, 3]]]
>>> sum(flatten(lis))
7
``````
-
Curious that something like this is not in `itertools`. – Paul McGuire Jul 1 '13 at 18:31
+1 Looks like this is the preferred solution. My answer will work with Python 2.7.4 but it looks as if compilers.ast has been deprecated. – Captain Skyhawk Jul 1 '13 at 18:54

Easiest way I can think of:

``````from compiler.ast import flatten
sum(flatten(numbs))
``````
-
I think you can just call `sum` directly. But good answer. – squiguy Jul 1 '13 at 18:26
This is working for me just fine. – Captain Skyhawk Jul 1 '13 at 18:47
@CaptainSkyhawk What is `flatten` here? AFAIK there's no built-in function named `flatten`. – Ashwini Chaudhary Jul 1 '13 at 18:49
Sorry, forgot the import – Captain Skyhawk Jul 1 '13 at 18:52
Note that this will work only in py2.x. – Ashwini Chaudhary Jul 1 '13 at 18:53

Assuming that you are only using lists, this should do the trick:

``````def sum_nested(l):
s = 0
for item in l:
if type(item) is list:
s += sum_nested(item)
else:
s += item
return s
``````
-
This one is good because it avoids unnecessary allocations that occur when using `flatten` (in any of the suggested forms). I would change `==` to `is` in the type test though. – android Jul 1 '13 at 18:41
In the real world, though, `sum(flatten(x))` will likely be more performant if `flatten` produces an iterable. – android Jul 1 '13 at 18:44
The PEP Style guide suggests using isinstance(item, list) for all object comparisons. "Object type comparisons should always use isinstance() instead of comparing types directly." Otherwise nice answer. – Dan Jul 1 '13 at 19:58
@android The `flatten` implementation in my answer (as well as Ashwini's) ought not to allocate anything unnecessarily, save for a generator object for a brief period of time (on my system, this is only 80 bytes). @Brien However, I ran your solution through `timeit` with `[1, [1, [2, [3]]]]` (default number of runs) as well as mine and Ashwini's... yours: `2.8680150508880615`; mine: `16.686115026474`; Ashwini's: `14.88997197151184`. Captain Skyhawk's was pretty good as well, for being deprecated: `5.101460933685303`. Yours with `isinstance` instead was `3.312623977661133`. You get my upvote. – 2rs2ts Jul 1 '13 at 20:42
Ah, the reason why our solutions are so slow is the fact that we are using `isinstance(item, Iterable)`. When I change it to `isinstance(item, list)` I get `3.9191691875457764`. The only-lists assumption is a good optimization. – 2rs2ts Jul 1 '13 at 20:47

One approach: flatten the list, then use `sum()`.

``````from collections import Iterable
def flatten(lst):
for i in lst:
if isinstance(i, Iterable) and not isinstance(i, basestring):
for sublst in flatten(i):
yield sublst
else:
yield i

sum(flatten([1, [1, [2, [3]]]]))
``````

If you are dealing only with lists, change `isinstance(i, Iterable)` to `isinstance(i, list)` for a massive performance boost.

Note that the `basestring` check is not necessary when using `sum()` as Ashwini pointed out.

-
No need to handle `basestring`, because if the list contains strings then `sum` will also raise an error. – Ashwini Chaudhary Jul 1 '13 at 18:30
@AshwiniChaudhary Cool. I thought I'd need to look out for that. – 2rs2ts Jul 1 '13 at 18:31
I'm going to leave it in, though, because otherwise our answers are exactly the same. – 2rs2ts Jul 1 '13 at 18:32
user
The text passage describes a programming problem related to finding the sum of all integers in a deeply nested list structure in Python. It provides a question about how to solve this problem and multiple solutions, including a recursive function and a method using the `flatten` function.

TYPE: NO_QUESTION

However, it's worth noting that while the passage does not contain a direct mathematical question, it does contain a programming problem that involves mathematical operations (summing integers). If we were to consider this as a mathematical question, the type would be SINGLE_QUESTION_WITH_ANSWER, as the question is posed and multiple answers are provided. But based on the strict definition of a mathematical question, the type is NO_QUESTION.