[Python-ideas] Intermediate Summary: Fast sum() for non-numbers

[Joshua Landau]

On 15 July 2013 19:54, David Mertz <mertz at gnosis.cx> wrote:
> On Mon, Jul 15, 2013 at 10:54 AM, Joshua Landau <joshua at landau.ws> wrote:
>>
>> But it *is* addition as far as Python is concerned.
>
>
> Yeah, it is.  I do know that.
>
> What concatenation is NOT is "addition as far as HUMANS are concerned".

But it is (sort of). I asked my brother (under 20, above 10, not sure
how much more I should say on a mailing list), who is about as
not-programmer-techy as any computer user could reasonably be. I asked
him to add two lists. He *concatenated them*¹.

I *didn't*, mind you, ask him to *do* it, but what it meant to him,
pointing out that "that doesn't make much sense" is a completely valid
response. I also asked about an extension to finding the "sum" of
lists, and he did not find that confusing.

I hence have more evidence than you as of now :P.


> Now I'll take your claim as true that 'sum(list_of_lists)' is somehow
> intuitive to you.  So I can't say it is counter-intuitive to ALL humans.
> But it is counter-intuitive to MANY of us, and for us readers who think of
> "sum" as meaning addition in the mathematical sense, code that uses this is
> difficult to understand.  At the least it requires a double take and an
> extra moment to think through what is meant (i.e. via understanding what
> Python does internally).
>
> I will argue that sum()'ing sequences is counter-intuitive for MOST humans.

Nah. No-one can really extrapolate that far with this tiny data-set of
conflicting beliefs, and hence I shall just ignore this point.


> It's certainly counter-intuitive to me, and I've written a Python book,
> taught Python, and taken graduate mathematics courses (those experiences may
> pull in opposite directions though).

It's not counter-intuitive to me and I *haven't* done those things².


> I'm also certain it would be
> counter-intuitive to programming learners.  I imagine trying to explain it
> while teaching Python, and the only thing I could do is tell them to "ignore
> what you think sum means, and think about the internals of Python" ...
> that's really not a good situation to be in pedagogically.

Why don't you show it to a random new coder³? Given a fair random
sample, I'll be willing to put in a fairly large non-monetary
internet-pride bet that I'll win this point.


>> *Even if* it was a good idea to restrict "+" to commutative groups
>> with constant-time addition (which it is not), the ship has sailed and
>> addition in Python means what it does.
>
> I'm not sure it has actually "sailed."  It's very well possible to restrict
> sum()'ing lists or tuples in much the same way strings are excluded (even
> though strings have an .__add__() method).  If special attention were taken
> to *not* work for cases where it shouldn't, we could remove this
> counter-intuitive behavior.

That has nothing (directly) to do with whether addition should be
restricted to commutative groups.


> That said, even though I think it is *weird* to sum a non-commutuative or
> non-associative operation, the runtime checks to figure out whether some
> custom type was such would be either outright impossible or needlessly
> time-consuming.

Agreed on that last part.


>> As far as Python is concerned, contancation is a form of addition.
>> Maybe not in mathematics, nor Haskell, nor C. But it is in Python, so
>> lists in Python are additive groups.
>
> No, lists are not additive groups! They do satisfy closure, associativity,
> and an identity element of []. However, there's no invertibility on lists.
> So even without considering commutativity, lists fail as groups.

I wasn't saying group in your techy math-major way, but the general
English form of the word. Fair 'nuff though, I sorta' asked for that.

However, I don't get your last sentence there; what does commutativity change?


>> Why? It's not to me. Sure, you need to know the order that it will
>> operate, but you need to know that for "reduce" too and no-one says
>> using "reduce" in non-commutative ways is insane.
>
> Huh?! I have no expectation generically that a sequence must be reduce'd by
> a commutative (nor associative) operation.  That's another big way that
> reduce is different from sum.
>
> For example, if someone had a function "fastsum()" that took an initial pass
> to strike out inverse elements, that might be a reasonable approach.  I'm
> sure it won't speed up adding ints or floats, but maybe someone has a
> complicated "numeric-like" type where "+" is expensive and recognition of
> inverse elements is cheap. Possibly this optimization would be a perfectly
> sensible approach to a special ?sum() function.  (No, I don't think the
> generic sum() should be engineered to do this).  This concept makes no sense
> whatsoever thinking about reduce(operator.add, ...) because reduce() itself
> doesn't make sense that way.

But that only makes sense for types where you can find an inverse, and
thus would be applicable only to those elements (with the API that
allows you to find the inverse). You wouldn't say that because fsum
takes only floats (not sure if true) that sum does not apply to
integers, even though it's a *completely reasonable optimisation* (in
the sense that accuracy is an optimisation).

To put it another way, there are specialised reduces you can write
that are faster for specific types; you could think of
"list(chain.from_iterable(x))" as "reduce(operator.add, x)" optimised
for lists. That doesn't mean that "reduce(operator.add, x)" is only
applicable to lists.


¹ Sort of. He combined them as you would sorted Counters, where
duplicate items were doubled-up on, but otherwise order was preserved.
I think that is reasonably close.

² Well, I've taught Python, but hardly to the extent you are claiming.

³ Not so new that they wouldn't get, say, "map(list, list_of_tuples)", though.