Reduce requires knowing that the sum of zero entities is zero but the multiply of zero entities is one. They forget to throw the correct number and think that reduce() just do not work for them.
For numerical code I like einops.reduce more than numpy/pytorch sum reductions because you can reduce over named dimensions. It’s much more readable than having to reason through axis indexing again every time you come back to the code
Has the performance of sum on lists of lists in Python been fixed? It used to be pretty abysmal. But I suppose some would say that if you need to consider performance at all, you’re in the wrong language… :)
It always messes with me: reducing across a specific axis always takes O(whole tensor) time, because there's no difference between "iterate over all dims, then collapse the final one" versus "iterate versus the first dim and do some cursed tensor accum" (and likewise for between)
Maybe there's just a better way to think about it and I'm still thinking about it way too much like a programmer
You "accumulate" an answer one item at a time, but there's no guarantee any dimensions are getting reduced.
You can easily duplicate the effects of map with reduce, for example, so the dims would stay the same. You could even expand dimensions, if you like, turning a 1-d array with n elements into an s X t 2-d array. If the reducing function tracks the total number of elements seen, it can easily know when to start a new row.
This is part of why people keep pointing out the name, "reduce", is a bit misleading.
Well yeah, it's the lowest-level array function. All of the others can be written with reduce, but not vice-versa. Of course it's going to be less friendly.
I like reduce in principle since it generalizes a simple concept pretty nicely. I don't use it that much in practice since its alternatives just require less brainpower. It competes against using local mutable state with a loop or iterator combinator which I would argue are easier to wrap your head around (i.e. loop with variable/map with closure). I would argue its one of those cases where something is just harder to do/understand in functional vs imperative programming.
I assume the author is talking about `fold`, as in `[A] -> B -> ((B,A) -> B) -> B`, and not what I often think of as reduce as `[A] -> ((A,A) -> A) -> A`.
`fold` is awesome and super useful. It's the easiest and most convenient way to turn a collection into a single value. Put me anecdotally in the opposite bucket.
For loops are not easier or more convenient than fold.
fold sum 0 collection
versus
acc = 0
for x in collection:
acc = acc + x
or the even worse
int acc = 0;
for(int x = 0; x < collection.length; ++x) {
acc += collection[x];
}
You can read one line and know exactly what's happening in the fold example. In the Python and C++ examples, you have to scan more lines and there's way more opportunity for typos.
A for loop gives you better memory management and speed, but the tradeoff only makes sense to me if you're doing embedded work or something. Otherwise, eat the .000000000001% speed loss to reduce the risk of logic errors, typos, etc. and to improve developer ergonomics.
Only real difference is that `fold` is denser. Both require prior knowledge to understand in their respective paradigms.
Adding numbers like this is not common in real world code. Now let's say instead of adding x, you have too look up X in a cache with an additional "type" param and update a metric of cache hits (or misses). You have to define a free function to keep your fold readable and understandable. In for loop it's much easier to understand.
>You have to define a free function to keep your fold readable and understandable.
I agree. But you'd do that for a for-loop, too, unless you want a bloated for-loop.
> In for-loop it's much easier to understand.
I have to disagree there. You'd still be working with a free function, or you'd be working with a bloated for-loop body.
Combining cache loopkups, metric tracking, etc. runs into SOC issues that IME for-loops just let imperative developers get away with until it comes time to test their code.
Furthermore, free functions aren't bad. They're good. They're a self-documenting abstraction. Unless you name it `function_one` or something.
Having my fold lambda do its primary business role but call `update_cache_and_metrics` makes it unnecessary for someone reading the flow of logic from even needing to go read the body of that free function.
I think part of the issue is that a lot of programming languages don't make a strong distinction between the two, and only provide the (more powerful) fold, but in a way that makes reduce operations harder to reason about (like OP said, with 0 types).
Associativity also makes fold hard. It's not super trivial to know when you might need e.g. left fold vs right fold
These are pretty close to each other, to the point where I wouldn't bother strongly distinguishing them.
Suppose we have foldr as in [A] -> B -> ((A, B) -> B) -> B, foldl as in [A] -> B -> ((B, A) -> B) -> B, and reduce as in [A] -> ((A, A) -> A) -> A.
Then we have foldr list value operator = reduce [\b -> operator a b | a <- list] (.), foldl list value operator = foldr (reverse list) value (flip operator), and in the case of a finite non-empty list and associative operator, we have reduce list operator = foldr (tail list) (head list) operator = foldl (init list) (last list) operator.
So these are all basically slight re-parametrizations of each other.
Even in the world of functional programming, there's an argument to be made that `fold` is a bit of a code smell, in a similar vein as `while` being slightly smelly in an imperative code base. There's good reasons for each to be used, but they are such low level iteration primitives that you might be better off with a higher one (e.g. for loops or iterators in imperative programs; in FP you might reach for monoidic reduces (as opposed to folds where the accumulator is a different type from the list element), monadic traverses, or recursion schemes). Even though you can implement iterators or for loops in terms of while loops, you probably shouldn't, and similar for functional traversals.
In languages like python or Java though, you don't really have access to many of the higher power functional traversals however. So that puts you into a similar kind of bind as working in a language with only while loops
todo_iter = iter(todo)
while True:
try:
value = next(todo_iter)
except StopIteration:
break
process(value)
or like that?
todo_iter = iter(todo) # Note: assume "todo" does not contain None
while value := next(todo_iter, None):
process(value)
I'd say neither of those are as clean as a simple for loop:
for value in todo:
process(value)
and yes, that's the case of a personal preference, although I'd bet a lot of Python programmers will share that preference with me. That's what "code smell" means, after all - it's not a bug which is clearly incorrect, it's a code which is best avoided based on reviewer's personal experience.
Your for loop is using an iterator of some kind. Just because it’s hidden in your language of choice doesn’t mean it’s not there.
While/for can achieve the same thing, sometimes while is more practical as the steps to complete are unknown. But sure, stick your simple iterating a fixed collection as why it demonstrates while is a lesser language feature.
Probably because while is the source of many infinite loops, and because it’s sometimes faster and more rigorous to compute the length ahead of going into the loop.
That said, I personally don’t think it’s smelly at all.
Map and Filter are nice because they let you reason locally about a single element in isolation. Reduce(Fold) forces you to reason globally about intermediate results. Reduce also forces you to conjure up a "zero" value of the relevant type, which isn't usually difficult but it does constitute some extra mental overhead.
The accumulator is global state. If you're folding from list<int> to int you're right that it's (usually) effectively a pairwise operation on ints. If the fold is something like list<foo> -> tree<bar> then you have to reason about each intermediate (tree<bar>, foo) -> tree<bar>, i.e. how global state should evolve over time with each update.
What a load of nonsense. The only thing you have to do is think about your initial state, which is usually trivial and some sort of empty state (0, empty list) and how to combine two elements.
That's what I'm used to as well, but in my experience a lot of programmers take fold and reduce to be synonyms. A monoidal reduce is much less "scary" than a general fold. I suspect most programmers have never heard the word monoid, let alone know what it means, and having to remember the meaning of a weird new word is enough to make most people dislike something compared to the simpler more familiar operations.
It just means if you have some functor F (generic type with a `map` function, like List), then you have a `flatten` operation F[F[_]] - > F[_], and like a monoidal product, it's associative. So if you have a triply nested List, you can flatten inside first or outside first. Also, like a monoid, it has a neutral function wrap: A->List[A] (e.g. x -> [x]), and that function is an identity for flatten.
So basically wrapping and flattening behave in a sane way. Wrap is your one, flatten is your multiply, and it's like a monoid if you squint.
"The meme" literally comes from a book immediately after a long definition that was offering it as an intuitive explanation, assuming you know what a monoid is. All the laws and stuff boil down to "if you generalize the idea of a monoid a little bit, and if you have some functor+flatten+map forming a monoid, we call that a monad." If you don't know what that stuff means then obviously it's not for you, but if you do, then it's actually a concise way to say "what it is," which is basically just that flatten is associative and wrap is trivial.
The point is that the terminology surrounding this is impenetrable and non intuitive. Rather than acknowledge that, we get a lesson on category theory, which is missing the point.
The person I replied to said they know what monoid means, so they're familiar with algebra. The explanation is intuitive for someone familiar with undergraduate algebra. That's literally where the meme comes from, an intuitive remark from an introductory text on category theory. If you think it's impenetrable, it's not for you. You don't have the correct background, so ignore it.
It may have come from an old textbook, but its origin as a meme is a 2009 joke blog post that gets its humor from making fun of how obtuse and pedagogically inept that explanation is. When people reference it today, this is what they are referencing: https://james-iry.blogspot.com/2009/05/brief-incomplete-and-...
I'm aware of the meme, but it's not obtuse or pedagogically inept.
Like if someone says they're familiar with groups and Fourier transforms, but not what it means to say wavelets are the Fourier basis for the affine group, and I break that down, and you don't know what any of those words mean, that's not me giving an obtuse explanation of wavelets; that's you wandering into the wrong conversation.
Do you want to understand monads, or do you want to understand the original quote that the joke you referenced was based on?
For the record, the original quote by Saunders Mac Lane is "a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor."
That quote is a statement in category theory. The author probably never heard of, say, Haskell - he was a pure mathematician. You can't usefully express that quote in Haskell code. You can treat it as a kind of formal description of what monads are, and Haskell generally conforms to that. But in that context, the quote itself is essentially using category theory as a metalanguage, in the same sort of way as one might write a mathematical statement that captures the semantics of some programming language expression.
That said, the quote can be handwavingly understood if you know what a monoid is, and that for monads, the identity object is the identity functor, its product is `join`[1] and its unit and multiplication satisfy the usual monoid laws.
For a concrete example, consider this Haskell expression using the `Maybe` monad:
do
x <- Just 3
return (x + 1)
That desugars to:
Just 3 >>= \x -> Just (x + 1)
Which we can desugar to an expression in terms of the monad's monoidal product, `join`, by substituting the definition of `>>=` in terms of `join`[1] to get:
join (fmap (\x -> Just (x + 1)) (Just 3))
You can evaluate that in Haskell and you'll get `Just 4`, just like the original expression.
So what happened there? The inner expression `fmap (\x -> Just (x + 1)) (Just 3)` applies the anonymous function to `Just 3` to get the double-wrapped `Just (Just 4)`. One of the `Just` wrappers is then eliminated with `join`.
(Btw, the fact that we have a Maybe within a Maybe here is related to the fact "monads are monoids in the category of endofunctors" - a category that maps to itself. That's where that part of the quote comes from.)
In this simple example, there's some unnecessary machinery - you can get the same result with `fmap (\x -> x + 1) (Just 3)`, without the extra `Just` wrapper or the `join` to eliminate it. But then you lose the ability to do things "in the monad": the anonymous function becomes just an ordinary function, it doesn't have access to the monadic wrapper. Many of the useful things that monads can do are because the wrapper is available in every function, so you can store state in it (Reader monad), create new wrapper instances with different state and pass those on (Writer and State monad), etc.
> Reduce also forces you to conjure up a "zero" value of the relevant type, which isn't usually difficult but it does constitute some extra mental overhead.
It's always worthwhile to consider what the result will be when you pass in an empty list.
If you have need of a reducing operation though, you will still need to think about that value. If you are summing up a list of numbers, it doesn't matter whether you use reduce or a loop, you need to set some initial value.
I agree, although most of the time you do end up needing to consider it with Map/Filter. It's just, it doesn't force you to. Which means either you think about it later, or it bites you in the ass because you didn't consider the empty case. Not always—and for those cases where you don't end up needing the empty case, Reduce is probably not necessary, and Map/Filter is sufficient.
> Reduce also forces you to conjure up a "zero" value of the relevant type
It's more accurately an identity. If you are multiplying the identity is 1. While I think most people are comfortable saying the sum of no elements is 0 it's perhaps less intuitive that the product of no elements is 1. This makes me think reduce might be preferred by those with a mathematical background.
Related to the point about worse performance, I'm pretty sure I was there when reduce was "banished" from Python 3 -- demoted to functools.reduce(), instead of the builtin reduce() in Python 2
The story is that sometime in 2006 or 2007, Guido van Rossum was debugging why a web page in Google's internal code review tool (which he wrote) was taking 30+ seconds to render.
This is basically a "production" incident, since thousands of Google engineers relied on the tool. Requests like this were probably tying up threads and exhausting thread pools, perhaps
Eventually it was tracked down to a line wrapping algorithm written with reduce(). I don't think he wrote it -- it may have come in through a dependency. As many know, reduce() is basically:
s1 + s2
s1 + s2 + s3
s1 + s2 + s3 + s4
...
And that's O(n^2) when s_i are strings. And I think it showed up if you viewed a 5000+ line diff, or a 5000+ line file. (Newer programs like Github also suffer here)
I believe in Python at that time, += was already optimized to avoid this (just like essentially all JS VMs are). Or you can use the idiom of append() to list and join() after.
But reduce() basically forces the inefficient implementation, and I'm sure this is still true in Python 3.
---
So basically Guido spent a long time debugging a performance problem related to reduce(), and made the decision to eject it. I was his officemate at the time, so I recall this, but I wasn't involved directly
Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style.
He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later.
This always feels odd to me. It would seem a fairly straight forward optimization of the interpreter to special case the different types that it can reduce.
That is, why couldn't they have done the essentially same trick that you reference for += with reduce?
That sounds nice but in practice it’s probably not super helpful. Yes you could make a special case for reducing “+” over integers. But in python you can generally not promise that all the inputs are strictly integers, and you can’t even promise that your “+” function has no side effects.
There is no such trick. Python is only now getting those sort of JIT style optimizations, and that one in particular still hasn't hit. Do not use += on strings in a loop unless you are certain the iteration count will be small.
There is an optimization for lists, and maybe that's what GP is remembering. l += is functionally different from l = l +. The former mutates l, whereas the latter creates a new l. The difference matters when the line above is m = l. The mutation version will mutate m as well (they're the same reference), the creates new version will not. This optimization can just as easily turn into a footgun if the programmer is unaware of it, and in that sense is unpythonic.
I’m not a fan of this kind of “fancy” optimization anyway.
It’s too fragile. I may make some innocuous change, now the compiler cannot recognize the pattern and performance falls off the cliff.
I’d rather have the reliabile performance than the absolute fastest possible result. Then if there’s an issue I can catch and fix it reliably with profiling, not deal with a heisenbug based on whether the compiler can match the pattern.
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, 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.
>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:
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.
Python has always had a bytecode compiler that did some minor optimizations, since its inception in the 90's. The issue is that optimizations are very hard to do correctly in the compiler because Python is so dynamic. Any piece of code could suddenly redefine mytype.__add__() and so forth.
I find that decision a bit odd given that accumulating a string with a loop is also quadratic in Python if you use = instead of +=, or even if you use += when the left operand isn't provably unshared. I don't believe removing loops was seriously considered.
The footgun isn't `reduce` in particular, but failing to use `join`.
Doesn't reduce force the accumulator to be shared though? Both the reduce and the lambda are holding onto references to acc, which defeats any "single reference" optimizations.
Why is it still active? Even an interpreter with no lookahead could see that it goes out of scope immediately when f returns (it gets shadowed on that line), so as long as there's no guarantee about when finalizers get called, it should be able to mark it dead inside of reduce as soon as it's passed to f. Like move semantics here should be a general pattern for optimization, no?
Yes. My point is that it's better to use the explicit optimized method for joining strings in a performance-sensitive context than to try to meet the conditions for an implicit optimization.
If the s are small the usual geometric buffer growth mitigates that. Of course you can compute the final buffer size in this case, but often you have a bunch of dynamically-generated strings of different sizes.
I suppose `reduce` as built-in is the footgun because it's too easy to reach for. Now if someone doesn't know about `join` perhaps they look up how to do it because they think 'surely there's a better way than a loop without an import'.
> Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style.
> He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later.
That would explain why they're so inconvenient to chain.
I wanted to add that from personal experience tastes can change! I didn't like reduce when I was first exposed to functional programming, but have come to prefer it.
Might be nonsensical, but one thing I sometimes wonder is why I reach for reducing a list to a value more often than I need to generate a list from a starting value. I guess the asymmetry has something to do with the kinds of applications I work on.
Anywhere that I could use reduce, I instead write a tail recursive function. This is also why I do not and will not ever choose python or javascript voluntarily.
It's on my list of things that are awkwardly named because there's not a great name to choose, particularly given how wide the different use cases are.
At least in TypeScript, it's a bit clunky to type, and I usually forget the order of the reduce function's arguments (accumulator, current item). Maybe it's just me, but it's especially easy to forget the order when the position of the accumulator is the 1st argument to the callback but the 2nd argument of the reduce function:
In .filter(), The current item is the 1st argument and the intermediate/accumulated value comes later: filter((currentItem, index, intermediateArray)) => ...)
I use .filter() more often, so that argument ordering where currentItem is right next to the array is more intuitive for me
That's an interesting idea. I might get hung up for cases where "previous" is a different type from "current", like if you're reducing a list of objects into a single object. You've got the current item of the array and the current state of the accumulator, so they're kind of both current. Or you've got the last state and current item, but "last" is ambiguous.
In general, I find that if something is hard to describe in plain language, it's hard to code. Reducers are a bit clunky to talk about, which could make them harder to reason about, too.
In TS/JS you’re usually inlining the reducer fn, and there’s something hard to read/especially ugly about the comma after the bracket or arrow fn into the initalValue.
That said, when I’m reducing a list, I still use reduce.
I think I've written this before and generally people are horrified, but a neat trick I like to do for a little bit of concurrency is making the first argument an async function.
That means you have to await the accumulator at some point before you return it, but anything you do before that call all gets fired off immediately. Then each invidivual iteration waits for the one before it to finish before finishing itself.
It's a pretty niche pattern, but it's a good way to make your coworkers do a double take while giving you quite a bit of control over exactly how it behaves. Similar to Promise.all, but more expressive I feel.
I've worked with developers that were reduce maximalist. During PR reviews, anything that could be rewritten with reduce was flagged. One of the benefits of AI is not having to care as much about things like that.
109 comments
[ 2.8 ms ] story [ 121 ms ] threadI come across reduce once in a few months, then I think it's a neat trick and a nice to have function.
then I forget it's even available and don't ever use unless these days LLM brings it up again.
Maybe there's just a better way to think about it and I'm still thinking about it way too much like a programmer
You "accumulate" an answer one item at a time, but there's no guarantee any dimensions are getting reduced.
You can easily duplicate the effects of map with reduce, for example, so the dims would stay the same. You could even expand dimensions, if you like, turning a 1-d array with n elements into an s X t 2-d array. If the reducing function tracks the total number of elements seen, it can easily know when to start a new row.
This is part of why people keep pointing out the name, "reduce", is a bit misleading.
`fold` is awesome and super useful. It's the easiest and most convenient way to turn a collection into a single value. Put me anecdotally in the opposite bucket.
You will eventually learn about something called "for loop", and it will be nice.
A for loop gives you better memory management and speed, but the tradeoff only makes sense to me if you're doing embedded work or something. Otherwise, eat the .000000000001% speed loss to reduce the risk of logic errors, typos, etc. and to improve developer ergonomics.
Adding numbers like this is not common in real world code. Now let's say instead of adding x, you have too look up X in a cache with an additional "type" param and update a metric of cache hits (or misses). You have to define a free function to keep your fold readable and understandable. In for loop it's much easier to understand.
I agree. But you'd do that for a for-loop, too, unless you want a bloated for-loop.
> In for-loop it's much easier to understand.
I have to disagree there. You'd still be working with a free function, or you'd be working with a bloated for-loop body.
Combining cache loopkups, metric tracking, etc. runs into SOC issues that IME for-loops just let imperative developers get away with until it comes time to test their code.
Furthermore, free functions aren't bad. They're good. They're a self-documenting abstraction. Unless you name it `function_one` or something.
Having my fold lambda do its primary business role but call `update_cache_and_metrics` makes it unnecessary for someone reading the flow of logic from even needing to go read the body of that free function.
Associativity also makes fold hard. It's not super trivial to know when you might need e.g. left fold vs right fold
Suppose we have foldr as in [A] -> B -> ((A, B) -> B) -> B, foldl as in [A] -> B -> ((B, A) -> B) -> B, and reduce as in [A] -> ((A, A) -> A) -> A.
Then we have foldr list value operator = reduce [\b -> operator a b | a <- list] (.), foldl list value operator = foldr (reverse list) value (flip operator), and in the case of a finite non-empty list and associative operator, we have reduce list operator = foldr (tail list) (head list) operator = foldl (init list) (last list) operator.
So these are all basically slight re-parametrizations of each other.
The fact that you wrote this comment with Hindley-Milner-ish notation already makes your an outlier.
In languages like python or Java though, you don't really have access to many of the higher power functional traversals however. So that puts you into a similar kind of bind as working in a language with only while loops
Care to explain?
I feel like this is a case of personal preference over actual issue.
While/for can achieve the same thing, sometimes while is more practical as the steps to complete are unknown. But sure, stick your simple iterating a fixed collection as why it demonstrates while is a lesser language feature.
You're not the OP, you/me we're only guessing what he/she might've meant.
That said, I personally don’t think it’s smelly at all.
Fold is a recursion scheme
More complicated recursion schemes are progressively harder to read. Probably not great if you are not doing code golf
If the algortihm doesn't work the same forward, backwards, and with a tree scan, it ain't reduce (as a first approximation not IFF)
So basically wrapping and flattening behave in a sane way. Wrap is your one, flatten is your multiply, and it's like a monoid if you squint.
Like if someone says they're familiar with groups and Fourier transforms, but not what it means to say wavelets are the Fourier basis for the affine group, and I break that down, and you don't know what any of those words mean, that's not me giving an obtuse explanation of wavelets; that's you wandering into the wrong conversation.
For the record, the original quote by Saunders Mac Lane is "a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor."
That quote is a statement in category theory. The author probably never heard of, say, Haskell - he was a pure mathematician. You can't usefully express that quote in Haskell code. You can treat it as a kind of formal description of what monads are, and Haskell generally conforms to that. But in that context, the quote itself is essentially using category theory as a metalanguage, in the same sort of way as one might write a mathematical statement that captures the semantics of some programming language expression.
That said, the quote can be handwavingly understood if you know what a monoid is, and that for monads, the identity object is the identity functor, its product is `join`[1] and its unit and multiplication satisfy the usual monoid laws.
For a concrete example, consider this Haskell expression using the `Maybe` monad:
That desugars to: Which we can desugar to an expression in terms of the monad's monoidal product, `join`, by substituting the definition of `>>=` in terms of `join`[1] to get: You can evaluate that in Haskell and you'll get `Just 4`, just like the original expression.So what happened there? The inner expression `fmap (\x -> Just (x + 1)) (Just 3)` applies the anonymous function to `Just 3` to get the double-wrapped `Just (Just 4)`. One of the `Just` wrappers is then eliminated with `join`.
(Btw, the fact that we have a Maybe within a Maybe here is related to the fact "monads are monoids in the category of endofunctors" - a category that maps to itself. That's where that part of the quote comes from.)
In this simple example, there's some unnecessary machinery - you can get the same result with `fmap (\x -> x + 1) (Just 3)`, without the extra `Just` wrapper or the `join` to eliminate it. But then you lose the ability to do things "in the monad": the anonymous function becomes just an ordinary function, it doesn't have access to the monadic wrapper. Many of the useful things that monads can do are because the wrapper is available in every function, so you can store state in it (Reader monad), create new wrapper instances with different state and pass those on (Writer and State monad), etc.
---
[1] x >>= f = join (fmap f x)
It's always worthwhile to consider what the result will be when you pass in an empty list.
It's more accurately an identity. If you are multiplying the identity is 1. While I think most people are comfortable saying the sum of no elements is 0 it's perhaps less intuitive that the product of no elements is 1. This makes me think reduce might be preferred by those with a mathematical background.
The story is that sometime in 2006 or 2007, Guido van Rossum was debugging why a web page in Google's internal code review tool (which he wrote) was taking 30+ seconds to render.
This is basically a "production" incident, since thousands of Google engineers relied on the tool. Requests like this were probably tying up threads and exhausting thread pools, perhaps
Eventually it was tracked down to a line wrapping algorithm written with reduce(). I don't think he wrote it -- it may have come in through a dependency. As many know, reduce() is basically:
And that's O(n^2) when s_i are strings. And I think it showed up if you viewed a 5000+ line diff, or a 5000+ line file. (Newer programs like Github also suffer here)I believe in Python at that time, += was already optimized to avoid this (just like essentially all JS VMs are). Or you can use the idiom of append() to list and join() after.
But reduce() basically forces the inefficient implementation, and I'm sure this is still true in Python 3.
---
So basically Guido spent a long time debugging a performance problem related to reduce(), and made the decision to eject it. I was his officemate at the time, so I recall this, but I wasn't involved directly
Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style.
He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later.
https://docs.python.org/3/library/functools.html#functools.r...
That is, why couldn't they have done the essentially same trick that you reference for += with reduce?
There is an optimization for lists, and maybe that's what GP is remembering. l += is functionally different from l = l +. The former mutates l, whereas the latter creates a new l. The difference matters when the line above is m = l. The mutation version will mutate m as well (they're the same reference), the creates new version will not. This optimization can just as easily turn into a footgun if the programmer is unaware of it, and in that sense is unpythonic.
s = s + "foo"
and
s += "foo"
Since 2005 with the release of Python 2.4:
https://docs.python.org/3/whatsnew/2.4.html#optimizations
It’s too fragile. I may make some innocuous change, now the compiler cannot recognize the pattern and performance falls off the cliff.
I’d rather have the reliabile performance than the absolute fastest possible result. Then if there’s an issue I can catch and fix it reliably with profiling, not deal with a heisenbug based on whether the compiler can match the pattern.
> += deferred concatenation requires lazy strings and that didn't come until 10-15 years later.
CPython's += does not perform deferred concatenation, 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.
>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:
https://www.artima.com/weblogs/viewpost.jsp?thread=98196
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.
https://github.com/python/cpython/commit/a70b19147fd163744be...
The footgun isn't `reduce` in particular, but failing to use `join`.
-map: [x*2 for x in xs]
-filter: [x for x in xs if x%0==2]
-reduce: ummm..
Maybe something like:
sum = x+ret for x in xs from ret=0
> He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later.
That would explain why they're so inconvenient to chain.
I find the two ways that you call it to be a bit annoying (not a showstopper). It just seems a bit "kludgy" to me.
Might be nonsensical, but one thing I sometimes wonder is why I reach for reducing a list to a value more often than I need to generate a list from a starting value. I guess the asymmetry has something to do with the kinds of applications I work on.
The FUBAR potential with map and filter is much smaller, with reduce it depends on deep knowledge of the internals of the reduction itself.
I use .filter() more often, so that argument ordering where currentItem is right next to the array is more intuitive for me
I had similar trouble, but I know call the "accumulator" just "previous" which makes it more logical in my head:
.reduce( (previous, current) => previous+current, 0 );
In general, I find that if something is hard to describe in plain language, it's hard to code. Reducers are a bit clunky to talk about, which could make them harder to reason about, too.
I think if `reduce` looked more functional or more like Erlang code, it'd be easier to read and digest.
That said, when I’m reducing a list, I still use reduce.
allTasks.reduce((acc, item) => { acc[item.label] = t => t.item.label === item.label; return acc; }, {} as Record<string, (t: typeof tasks[number]) => boolean>)
tasks.reduce<Record<string, (t: typeof tasks[number]) => boolean>>((acc, item) => ..., {})
Also imo it's cleaner to reduce to an object with something like this as the callback:
(acc, item) => ({ ...acc, [item.label]: t => t.label === item.label })
That means you have to await the accumulator at some point before you return it, but anything you do before that call all gets fired off immediately. Then each invidivual iteration waits for the one before it to finish before finishing itself.
It's a pretty niche pattern, but it's a good way to make your coworkers do a double take while giving you quite a bit of control over exactly how it behaves. Similar to Promise.all, but more expressive I feel.