Maybe you are misremembering the story? += deferred concatenation requires lazy strings and that didn't come until 10-15 years later. However, concatenating string lists with sum() was a common Python idiom at the time and it indeed incurred O(n^2) complexity. Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax.
> += deferred concatenation requires lazy strings and that didn't come until 10-15 years later.
CPython's += does not perform deferred concatenation and CPython does not use lazy strings. The optimization uses an eager in-place realloc if the string's ref-count is 1. This remains the optimization used even to this day and was introduced in 2005:
https://docs.python.org/3/whatsnew/2.4.html#optimizations
>However, concatenating string lists with sum() was a common Python idiom at the time
It could not possibly have been a common Python idiom since sum() explicitly rejected strings by throwing a TypeError. This was explicitly special cased to avoid the degenerate performance and the TypeError even has an error message saying "TypeError: sum() can't sum strings [use ''.join(seq) instead]".
>Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax.
No it had nothing to do with mixing with lambda syntax, on the contrary GvR actually wanted to remove reduce and lambda (and map and filter as well). Here is the actual article by GvR regarding removing reduce, absolutely nothing in it involves how it mixes with lambda expressions.
https://www.artima.com/weblogs/viewpost.jsp?thread=98196
>So now reduce(). This is actually the one I've always hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
Yes thanks for finding the Python 2.4 release page which shows the optimization! So I remembered correctly -- Python already had that optimization back then. (There seems to be a large amount of confusion on that in this subthread)
And the March 2005 Artima post is also a very good reference! That actually predates my story, since Guido hadn't joined Google by then. I recall that he joined in December 2005.
So maybe the bug I remember was more of a "push" in the direction he had already thought of, not the direct inspiration.
It's clear from the blog post that he disliked all of map / filter / reduce, and then I'm sure that users or python-dev pushed back on removing them, so he settled for banishing reduce() to the stdlib.
It was never possible to sum() strings.
https://github.com/python/cpython/commit/a70b19147fd163744be...