Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #50059 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  Simple recursive sum function | what's the cause of the weird behaviour? Russel Walker <russ.pobox@gmail.com> - 2013-07-06 05:37 -0700
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Russel Walker <russ.pobox@gmail.com> - 2013-07-06 05:54 -0700
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Russel Walker <russ.pobox@gmail.com> - 2013-07-06 05:59 -0700
      Re: Simple recursive sum function | what's the cause of the weird behaviour? Peter Otten <__peter__@web.de> - 2013-07-06 15:19 +0200
      Re: Simple recursive sum function | what's the cause of the weird behaviour? Joshua Landau <joshua.landau.ws@gmail.com> - 2013-07-06 19:43 +0100
        Re: Simple recursive sum function | what's the cause of the weird behaviour? Rotwang <sg552@hotmail.co.uk> - 2013-07-06 21:10 +0100
          Re: Simple recursive sum function | what's the cause of the weird behaviour? Rotwang <sg552@hotmail.co.uk> - 2013-07-06 21:25 +0100
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Chris Angelico <rosuav@gmail.com> - 2013-07-07 03:22 +1000
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Terry Reedy <tjreedy@udel.edu> - 2013-07-06 14:47 -0400
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Russel Walker <russ.pobox@gmail.com> - 2013-07-07 09:13 -0700
    Re: Simple recursive sum function | what's the cause of the weird behaviour? Russel Walker <russ.pobox@gmail.com> - 2013-07-07 09:44 -0700

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

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 empty list 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]
>>> 

[toc] | [next] | [standalone]

#50060

Nevermind!

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

[toc] | [prev] | [next] | [standalone]

#50061

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

[toc] | [prev] | [next] | [standalone]

#50062

Russel Walker wrote:

> 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']

[toc] | [prev] | [next] | [standalone]

#50073

On 6 July 2013 13:59, Russel Walker <russ.pobox@gmail.com> wrote:
> 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

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

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

[toc] | [prev] | [next] | [standalone]

#50080

On 06/07/2013 19:43, Joshua Landau wrote:
> On 6 July 2013 13:59, Russel Walker <russ.pobox@gmail.com> wrote:
>> 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
>
> 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

[toc] | [prev] | [next] | [standalone]

#50084

On 06/07/2013 21:10, Rotwang wrote:
> [...]
>
> 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

[toc] | [prev] | [next] | [standalone]

#50071

On Sat, Jul 6, 2013 at 10:37 PM, Russel Walker <russ.pobox@gmail.com> wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#50074

On 7/6/2013 8:37 AM, Russel Walker wrote:
> 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.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#50105

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 ''

[toc] | [prev] | [next] | [standalone]

#50106

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...

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web