sum and strings: Summary

[Paddy]

Paul Rubin wrote:
> "Paddy" <paddy3118 at netscape.net> writes:
> > Pythons designers seem to know and apply the advantages of having fewer
> > 'themes' that can be applied with less constraints I am curious about
> > such a constraint on sum.
>
> The opposing argument is that sum is sort of like reduce, i.e.
> sum((a,b,c,d)) could conceivably implemented as
>
>    temp = a
>    temp += b
>    temp += c
>    temp += d
>    return temp
>
> If the args are strings, the above is a quadratic time algorithm and
> it's better to throw an error than create such a trap for an unwary user.
> The obvious fix is for the manual to specify that the sum function should
> do the right thing and use a sensible algorithm.
>
> Semi-relevant quotation:
>
>     "Let's take an example. Consider an abstract data type stack. It's not
>     enough to have Push and Pop connected with the axiom wherein you push
>     something onto the stack and after you pop the stack you get the same
>     thing back. It is of paramount importance that pushing the stack is a
>     constant time operation regardless of the size of the stack. If I
>     implement the stack so that every time I push it becomes slower and
>     slower, no one will want to use this stack.
>
>     We need to separate the implementation from the interface but not at
>     the cost of totally ignoring complexity. Complexity has to be and is a
>     part of the unwritten contract between the module and its user. The
>     reason for introducing the notion of abstract data types was to allow
>     interchangeable software modules. You cannot have interchangeable
>     modules unless these modules share similar complexity behavior. If I
>     replace one module with another module with the same functional
>     behavior but with different complexity tradeoffs, the user of this
>     code will be unpleasantly surprised. I could tell him anything I like
>     about data abstraction, and he still would not want to use the
>     code. Complexity assertions have to be part of the interface."
>
>               --Alex Stepanov (designer of C++ standard template library)
>                 http://www.sgi.com/tech/stl/drdobbs-interview.html


Thanks Paul.
I also found this from Guido:
  http://mail.python.org/pipermail/python-dev/2003-April/034853.html
And this, in the same thread:
  http://mail.python.org/pipermail/python-dev/2003-April/034854.html

So,
The upshot is that complexity matters. The algorithm used in sum is
'very wrong' for use with strings, and their is no clean way to switch
to the preferred method for strings.( ''.join() ).


Thanks group,
- Paddy.