Simple recursive sum function | what's the cause of the weird behaviour?

[Russel Walker]

I know this is simple but I've been starring at it for half an hour and trying all sorts of things in the interpreter but I just can't see where it's wrong.

def supersum(sequence, start=0):
result = start
for item in sequence:
try:
result += supersum(item, start)
except:
result += item
return result

It's supposed to work like the builtin sum, but on multidimensional lists and also with the optional start parameter accepting something like an emptylist and so would also works as a robust list flattener. It's just for kicks, I'm not actually going to use it for anything.


This works:
- - - - - -

x = [[1], [2], [3]]
supersum(x) 6
supersum(x, []) [1, 2, 3]

This does not:
- - - - - - -

x = [[[1], [2]], [3]]
supersum(x, []) [1, 2, 1, 2, 3]

 

[Russel Walker]

Nevermind!

Stupid of me to forget that lists or mutable so result and start both point to the same list.

 

[Russel Walker]

Since I've already wasted a thread I might as well...

Does this serve as an acceptable solution?

def supersum(sequence, start=0):
result = type(start)()
for item in sequence:
try:
result += supersum(item, start)
except:
result += item
return result

 

[Peter Otten]

Since I've already wasted a thread I might as well...

Does this serve as an acceptable solution?

def supersum(sequence, start=0):
result = type(start)()
for item in sequence:
try:
result += supersum(item, start)
except:
result += item
return result

That depends on what is an acceptable result
For instance:

supersum([2, 3], 1) 5
supersum([[1], ["abc"]], [])

[1, 'a', 'b', 'c']

 

[Chris Angelico]

This works:
- - - - - -

x = [[1], [2], [3]]
supersum(x) 6
supersum(x, []) [1, 2, 3]

This does not:
- - - - - - -

x = [[[1], [2]], [3]]
supersum(x, []) [1, 2, 1, 2, 3]

You have a problem of specification here. What should supersum do with
the list [1]? Should it recurse into it, or append it as a list? It
can't do both. For a list flattener, you would need to either use
..append for each element you come across, or .extend with each list,
with some kind of check to find whether you should recurse or not.

Still, it's a fun thing to play with. I like code golfing these sorts
of trinketty functions, just for fun

ChrisA

 

[Terry Reedy]

I know this is simple but I've been starring at it for half an hour and trying all sorts of things in the interpreter but I just can't see where it's wrong.

def supersum(sequence, start=0):
result = start
for item in sequence:
try:
result += supersum(item, start)
except:

Bare except statements cover up too many sins. I and others *strongly*
recommend that you only catch what you *know* you actually want to (see
below).

result += item
return result

I recommend that you start with at least one test case, and with an edge
case at that. If you cannot bring yourself to do it before writing a
draft of the function code, do it immediately after and run. If you do
not want to use a framework, use assert.

assert supersum([]) == 0
assert supersum([], []) == []

Do the asserts match your intention? The tests amount to a specification
by example. Any 'kind' of input that is not tested is not guaranteed to
work.

Back to the except clause: only add try..except xxx when needed to pass
a test.

 

[Rotwang]

It's probably more robust to do:

def supersum(sequence, start=0):
for item in sequence:
try:
result = result + supersum(item, start)
except:
result = result + item
return result

I assume you meant to put "result = start" in there at the beginning.

as that way you aren't assuming the signature of type(start).

It's not quite clear to me what the OP's intentions are in the general
case, but calling supersum(item, start) seems odd - for example, is the
following desirable?

supersum([[1], [2], [3]], 4)

22

I would have thought that the "correct" answer would be 10. How about
the following?

def supersum(sequence, start = 0):
result = start
for item in reversed(sequence):
try:
result = supersum(item, result)
except:
result = item + result
return result

 

[Rotwang]

[...]

It's not quite clear to me what the OP's intentions are in the general
case, but calling supersum(item, start) seems odd - for example, is the
following desirable?

supersum([[1], [2], [3]], 4)

22

I would have thought that the "correct" answer would be 10. How about
the following?

def supersum(sequence, start = 0):
result = start
for item in reversed(sequence):
try:
result = supersum(item, result)
except:
result = item + result
return result

Sorry, I've no idea what I was thinking with that reversed thing. The
following seems better:

def supersum(sequence, start = 0):
result = start
for item in sequence:
try:
result = supersum(item, result)
except:
result = result + item
return result

 

[Russel Walker]

I read through all of the posts and thanks for helping. What was supposed to be simple a (recursively) straightforward, turned out to be quite tricky.

I've set up a small testing bench and tried all of the proposed solutions including my own but none pass. I'll post it below.

I've also discovered something about lists that explains the very first "weird" result I was observing, which I realized was because lists are mutable etc, but more specifically:

This

a = [1, 2]
a += [3]

is equivalent to, AFAIK, this

a = [1, 2]
a.extend([3])

So to overcome that you just have to do

a = [1, 2]
a = a + [3]

Which creates a new list. So any variables which were pointing to the same list as a, are unaffected.

Summary
- - - -

# --- Bad ---
a = [1, 2]
b = a
a += [3]
print a [1, 2, 3]
print b

[1, 2, 3]

# --- Good ---
a = [1, 2]
b = a
a = a + [3]
print a [1, 2, 3]
print b

[1, 2]


And as for the testbench:

def supersum(seq, start=0):
return


# ---------------- Testing -------------------------------- >

testcases = [

# (seq, start, result)

# arithmetic sums
([], 0, 0),
([[], []], 0, 0),
([[], [[],[]]], 0, 0),
([1], 0, 1),
([[], [1]], 0, 1),
([[], [[],[1, 1]]], 0, 2),
([[1], [1]], 0, 2),
([[1], [[1],[1, 1]]], 0, 4),
([[1], [[1],[1, 1]]], 1, 5),

# list flattening
([], [], []),
([[], []], [], []),
([[], [[],[]]], [], []),
([], [1], [1]),
([[], []], [1], [1]),
([[], [[],[]]], [1], [1]),
([1], [1], [1, 1]),
([[1], [1]], [1], [1, 1]),
([[1], [[1],[1]]], [1], [1, 1, 1, 1]),

]


for seq, start, result in testcases:
try:
assert supersum(seq, start) == result
except Exception as er:
print "seq:%s\t start:%s" % (seq, start)
if type(er) is AssertionError:
print "expected:", result
print "got: ", supersum(seq, start)
else:
print repr(er)
print ''

 

[Russel Walker]

I got it! One of the testcases was wrong,

([[1], [1]], [1], [1, 1]),

should be

([[1], [1]], [1], [1, 1, 1]),


And the working solution.

def supersum(sequence, start=0):
result = start
start = type(start)()
for item in sequence:
try:
item = supersum(item, start)
except TypeError:
pass
try:
result = result + item
except TypeError:
return result + sequence
return result


I couldn't yet get around doing type(start)() and it's pretty messy, but anyways...