sum for sequences?

[Steve Howell]

On Mar 29, 4:38 pm, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:
> On Mon, 29 Mar 2010 08:12:00 -0700, Steve Howell wrote:
> > On Mar 29, 7:40 am, Patrick Maupin <pmau... at gmail.com> wrote:
> >> On Mar 28, 9:45 pm, Steven D'Aprano
>
> >> <ste... at REMOVE.THIS.cybersource.com.au> wrote:
> >> > And what about tuples? And subclasses of list/tuples? How many
> >> > different types need to be optimized?
>
> >> One of the beautiful things about Python is that, for most things,
> >> there are few surprises for even new users.  "There should be one
> >> obvious way to do it" for the user means that, sometimes, under the
> >> hood, there are a lot of special cases for the implementers.
>
> > If nothing else, I think it's reasonably for users to expect symmetry.
>
> Why? What is symmetry in programming?

"Symmetry" is best shown by example.

 >>> 3 - 2
 1
 >>> set([1,2,3]) - set([2,3])
 set([1])

 >>> 5 * 3
 15
 >>> [1, 2, 3, 4, 5] * 3
 [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

 >>> 1 + 2 + 3 + 4
 10
 >>> sum([1,2,3,4])
 10

 >>> [1,2] + [3,4]
 [1, 2, 3, 4]
 >>> sum([[1,2], [3,4]], [])
 [1, 2, 3, 4]

> Since the + operator takes both numbers and lists, and the - operator
> doesn't, does "symmetry" require that we make up some list operation so
> that integers and lists are symmetrical?
>

No.  Nobody is advocating for list subtraction.

> > If you can use "+" to concatentate lists, then it seems reasonable that
> > something spelled "sum" would concatenate lists as well, and in
> > reasonable time.
>
> Where do you get the "reasonable time" from?
>

>From common sense.  Concatenation of lists should be in O(M*N) time,
not O(M*N*N), because there is no need to build intermediate lists.

>
> With a very few exceptions (e.g. dict lookup being "usually" O(1), list
> append being amortized O(1)), Python makes no promises about performance.
> It's not part of the language. If you, the programmer, are making any
> assumptions about performance that aren't clearly and explicitly
> documented in the official docs, then YOU are at fault, not Python.

I'm not making any assumptions here.  I know that sum() is needlessly
slow for lists, even though it is not explicitly documented.

>
> > It only takes a handful of sublists, about ten on my box, to expose the
> > limitation of the Shlemeil-the-Painter O(M*N*N) algorithm that's under
> > the hood.  It only takes 200 sublists to start getting a 10x degradation
> > in performance.
>
> And how many times have you needed to add 200 sublists?
>
> How many times have you needed to add 10 sublists?
>

Aggregating lists is a very common task in programming.  An example of
a list of lists would be a list of departments, where each department
is a list of employees.  If you want to sort the employees, you will
want to aggregate to a list.

> More special cases for implementers means more bugs in the language,
> which means I end up writing my own code and ignoring the built-in
> version anyway.
>

Special cases do not have to introduce bugs in the language.

> More special cases means I have to pay the cost of high accuracy float
> summation even when I don't need, or want, it.
>

Nothing about making sum() work for the general cases precludes more
specific, optimized functions.

> More special cases means I'm fooled into paying the cost of summing lists
> when I don't need to, because it's easier than importing itertools:

You don't have to be fooled.

> for item in sum(lots_of_lists):
>     pass
>
> needlessly creates a large list out of the smaller ones.

Although this is a mostly harmless example, developers with common
sense would not sum lots of lists unless they expected to keep the
resulting list around for multiple operations, or for one operation,
like sort(), where you need to create a list for the subsequent
operation.

> Even if I don't
> fall for the temptation, and write bad code, I still pay the cost in the
> libraries and applications written by others.

You already pay the small price for polymorphism when you use Python.

> More special cases isn't free.

Nobody said they were.

> It's MORE costly than teaching users to
> use list.extend or itertools.chain.
>

Which the docs for sum() don't do.