Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.
Reduce has an accumulator and a 2-arg function and languages are not very consistent amongst each other as to whether it's reduce(initial_acc, callback(acc, elem)) or reduce(callback(acc, elem), initial_acc) or reduce(callback(elem, acc), initial_acc) or what.
Hard to remember. Also some languages have a version of reduce that doesn't take an initial accumulator at all, which is just a footgun waiting for you to hit an empty collection. Also ALSO, the accumulator can easily become awkward in languages that don't support anonymous types or don't support easy mutation of an anonymous type record. Which is most of them!
Haskell got this right. You have foldr (right fold) and foldl' (left fold), and the order of the callback is opposite. If you do a left fold, then the initial accumulator is applied on the left; if you do a right fold, then the initial accumulator is applied on the right.
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
foldl' f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
The mnemonic here is that the folding function (aka the callback) replaces the comma.
I find this slightly easier to remember than other languages. In contrast most other languages do not simultaneously provide a left fold and a right fold, so they do not consider this aspect, making things more difficult to remember.
That said I totally agree this requires more brainpower to read and write than map or filter. For this reason I have sometimes refactored code to use foldMap instead of foldr or foldl', so one no longer needs to think of the direction of the fold or the order of arguments.
It's still a complex and more abstract function than map or filter. Those do a single thing that's easy to grasp. reduce/fold can be easily abused to duplicate the effect of most other collection functions, at the cost of making the code less readable. Although for slightly-too-clever people, that could mean you only need to know one function instead of all of them.
But it hurts readability. If you're going to do it, at least don't use it anonymously, but give it a name that clearly describes what's going on.
But even then, there can be hidden performance traps. I've often seen javascript that used reduce and created the new accumulator by using a spread on the old accumulator and adding the new one: `[...acc, newValue]`. But that spread is another iteration inside a loop, turning it from O(n) to O(n^2). A for loop where you append it is much faster.
That's what I tend to do, but since foldr/foldl' is so ubiquitous in Haskell it would be nice if I could just remember the argument order of the callback. kccqzy's explanation (in particular "it replaces the comma") might just help me do that :)
In some programming languages with RPN you can avoid this problem, because it makes sense to put it in the stack as the initial value, and then you can as easily have multiple initial values; and then the callback function can read that from the stack that you had put there, like anything else you will push into the stack to read it back later. For example, in PostScript you can write something like:
0 exch {add} forall
However, this is not as good if you want to use the first element as the initial value instead, but still it can be done but it is then not as simple (unlike in programming languages that do not use RPN but instead with function call with arguments, in which case it might be simpler).
I guess names as SELECT and WHERE are like SQL (although SQL works differently than other programming langauges).
In GNU Guile `reduce` is described as a special case of `fold`, where the first element is suitable to be used as initial value, while `fold` is more general and lets you specify another initial value. I think that makes a lot of sense.
In rust iterators there's both fold (you supply the initial value) and reduce (it uses the first element as the initial value, doesn't work on empty iterators)
Reduces the list to another list three times as long.
It's a reduction in the sense of a transformation (also often seen in complexity theory), not in the "this makes this smaller" everyday usage that I think about first.
While map is a great name, I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them.
I mean, it’s like a colander: you filter noodles and water, but which one do you keep? The noodles, right? But, replace noodles with tea and now you want to keep the water part.
There's always the Ruby strategy of just making all the names work. `select` and `filter` are buddies and you can use whichever you want or even go back and forth. Not a fan of `reduce`? That's fine, `inject` has got your back. Miss getting to type `collect` from Java or Rust? Don't worry, just use it instead of `map`, it's the same thing.
Talking about un-guessable, misleading function names,
C++ std::remove.
I would never have guessed what it does exactly. (It moves elements that match the filter to the front, and moves the end-marker forward. Leaves all the elements in the collection. You need to erase them yourself. )
Smalltalk has #reject: which does that. You could, of course, just wrap a not around the test in the closure, but sometimes reject with a well-named predicate is easier to read.
The filter keeps the tea... it's just that you then lift the filter out of the cup, carrying the tea with it. Flip your brain around to see it from that direction and it might help you with the mnemonics.
Kotlin has filter and filterNot (it also has separate "reduce" and "fold" functions, dependingon whether you want to specify an initial accumulator value or not)
I was thinking an apt analogy might be making stock -- you filter out all the solid food you don't want to keep in the liquid.
And it's a doubly-good analogy, because I have occasionally gotten that confused in real-life as well. Twice in the past ten years I've had a stock boil away for three hours, and then set a colander in the sink and poured it through, only to watch my beautiful stock swirl down the drain because motor-memory made me forget that I wasn't draining pasta but should have put the colander in a bowl...
It doesn't help that fold/reduce often have different orders depending on the ecosystem. Every few months when I have a reason to reach for `fold` in nutshell I forget that it has the next element as the first arg instead of the second, which is what I'm used to from Rust. I guess I should just be happy I don't need to specify which direction I want like in OCaml.
> Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.
I don't understand. Map takes input of type a and size n and returns output of type b and size n.
Filter takes input of type a and size n and returns output of type a and size ≤ n.
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, to help users avoid "footguns". 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.
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`.
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'.
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.
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.
def reduce(acc, f):
for v in self:
acc = f(acc, v)
return acc
The current acc goes out of scope each time you call f. There's no shared reference (assuming f doesn't sneak store it elsewhere, which for string combining, f should just be `return a+b`?).
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?
Fair, I suppose there's no end to the level of insanity that a programmer can do in a dynamic language. I'd think it could perhaps still look to see there's no catch, but maybe eval makes even that impossible.
It might - let's assume it does. 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.
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.
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?
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.
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.
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:
>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.
>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.
I liked reduce. You know, back when writing code was actually a thing we all did.
However, in those times of yore, I would often go back and remove it before committing. Unless you’re surrounded by other clever people, or it’s a personal project, you’re leaving behind some very elegant looking anxiety for the less gifted developers. Usually just to save one or two lines of code.
Reduce is a good illustration of the principle of least power[1]: it's powerful, flexible, general and low-level and can technically achieve any combination of summation, map, filter, find/includes, some/any/every, etc. But reduce is misused if it's reimplementing patterns available in higher-level form.
In cases when reduce is required because (for example) JS doesn't have a sum function, it should be kept simple. `arr.reduce((acc, el) => el + acc, 0)` is acceptable if lodash _.sum() is not available.
In cases when reduce is required because the higher-level operations like map/filter aren't flexible enough, decompose the reduction operation into simpler steps and use map/filter with multiple passes, or write a traditional for..of loop.
This principle also explains why enhanced/range/of loops are preferred over counter-based `for` loops, and counter-based loops over `while`. Technically all loops can be handled by `while`, but it's seldom needed because enhanced loops handle the common case with the cleanest syntax. Reduce/while/counter-based `for` loops are antipatterns where higher-level, less powerful abstractions exists.
One could also phrase this principle in terms of entropy (in the information-theoretic sense): If I read some code and come across filter() and map(), I already have a pretty good idea of what the code is doing, without even looking at the filter criterion or the mapping function. Entropy is low. (There's only so many filter and map functions you could write for any given type or pair of types.)
Meanwhile, if I see reduce(), "anything" could happen. (Well, of course not anything but the set of possible reducers is surely much larger.) So entropy is high.
Avoid high-entropy constructs in your code. Try to keep entropy as low as possible. (For the same reason, code with a principled approach regarding side effects is a lot better than code where any function could mutate global state at any given time.)
For me it's about the speed of understanding what the code does. Because filter and map are very constrained in what they can do they quickly tell me a lot about the shape of the computation I'm working with. In contrast reduce is much more flexible and so I need to do a much more detailed analysis to just answer a basic question like "is the result a scalar or another collection?".
Chained filter and map don't necessarily iterate multiple times. They certainly can but depending on how things are built they very often run as a single loop with the operations chained.
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.
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[1] 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.
[1]Or if they have, their only encounter with it is the "a monad is just a monoid in the category of endofunctors" meme.
It just means if you have some functor F (generic type with a well-behaved `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 an "identity" function wrap: A->F[A] (e.g. x -> [x]). Identity in the sense that "multiplying" (flattening) with wrap does nothing. i.e. wrap(flatten(x)) = flatten(wrap(x)) = x when those things make sense.
So basically wrapping and flattening behave in a sane way. Flatten is your multiply, wrap is your multiplicative identity, and it's like a monoid if you squint.
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.
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.
> 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.
> 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.
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
I assume OP refers to the cases where "while" is used to re-implement existing operations... imagine finding code like this:
i = 0
while i != len(todo):
process(todo[i])
i = i + 1
sure, there may be a good reason to implement things this way (maybe "todo" grows during iteration?), but maybe not, and then the loop should be instead simplified to:
for value in todo:
process(value)
(as an aside, this is exactly the case where the comments are required: "# not using for loop because todo might grow" will make it clear it's an intentional decision and not hallucination or something written from ignorance)
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.
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.
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.
There are way more places where a simple typo will ruin you in a for loop than a reduce or fold or map. Using briefer abstractions in place of nested loops is almost always preferable.
Nah. It involves multiple passes and setting the answer to the wrong value before (hopefully) setting it to the right value.
Plus it forces you out of whatever lazy/streaming paradigm you had going on. If your foldr produces a list, downstream can start consuming it in constant memory as long as you let it do its thing.
fold kinda does too, for setting the first combined value that you are assembling, and thus on an empty list you end up with that wrong value, same as the for loop
For me it's the name[0]. map puts out an array that has been mapped from another array. filter puts out an array that is a filter of the input array. both of those are always true. reduce, on the other hand, may put out a reduction of the input array (probably most of the time), but the fact that it may not means that what is happening is not actually a reduction. In languages like js/ts, you don't even have to return anything of the same type as the input array's elements. You could literally "reduce" and array of integers to a cancellation token, or a state object, or anything else.
I realize it's not the most efficient way to work, but I like my code to read like instructions. There's nothing reduce will do that a for loop won't accomplish and the for loop (+ an accumulator, of course) is more clearly "readable" than reduce. If I read map, I know what's going on. If I read filter, I know what's going on. If I read reduce, I have to figure out what's going on, even if I'm pretty sure what is going on. If I could rely on reduce to always give me back an element of the input array, I would use it more. But since it can give back anything, I prefer the simplicity of a for loop.
[0] I don't have any suggestions for "better" names because the whole operation is hard to sum up in a word? "dispatch" makes sense, as a function dispatching a function over each element in an array, but it masks the concept of accumulation from return values. "transform" is accurate, but hardly descriptive at all. the list goes on. It's an undeniably useful little function, it's just hard to make it easy to understand and therefore debug.
But I honestly very rarely use it (by either name) outside of a couple of pasted-in snippets (that I can't recall right now) where the strategy fits exceptionally well, probably because of the dumb reason that I tend to forget which block argument comes first (accumulator, or iterated item)! With other two-item argument lists such as `Hash#map` it being `key, value` makes sense, but with reduce/inject I don't see an obvious order. And I guess I learned before it was likely that some kind of AI autocomplete would be filling the args in for me.
It reduces n items to one item, recursively. The items don’t have to have the same type. Arguably accumulate is a more fitting name. I think of “reduce” as in cooking, boiling a volume of stuff down to some essence.
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
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.
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.
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.
Speaking as someone who often tries to reduce my use of reduce by replacing it with map and filter where possible, for me, falling back to reduce is analogous to falling back to a while loop or a for loop: I avoid it if I can.
The problem with reduce is that it can do so much, and therefore it is less clear when reading it quickly what it might be doing.
I think this is because in an imperative language, `reduce` does not actually give you much over a `for item in collection` loop. With `map` and `filter`, you immediately learn something about the result (it's a list of the same length as the original, with each item only depending on the corresponding original item; it's a list containing some of the original elements unchanged and nothing else). This is useful, so `map` and `filter` are good.
With `reduce`, the result could be anything, and in an imperative language, side effects are also possible. So it's just a loop with worse syntax.
(Admittedly, in an imperative language, `map` and `filter` could also have side effects, though I think most people would consider this bad style.)
I think that in every imperative language that offers `map`, `filter`, `reduce`, or similar, the written contract of this API should state that any higher-order function handed to it as an argument must be free from side effects.
I think I’ve seen several language core APIs have this in their contract, e.g. `Stream#reduce` in Java [0] (emphasis mine):
> accumulator - an *associative, non-interfering, stateless* function for combining two values
In Rust these specifically take `FnMut`, a function which can update internal/borrowed state, rather than `Fn` which can't easily. In `map` or `filter` you shouldn't rely on the iteration order so that's not often useful – maybe something 'logically' stateless but which needs a mutable connection/threadpool/cache, or eg a counter which is really an ancillary reduction. There's even `inspect` which is explicitly for such side effects. In `fold`, the order is guaranteed and you could use it for a state machine, a fiddly `zip` with other mutable iterators, etc – something you need to perform the reduction, but which isn't really an output, I think you could reasonably write either
I mean, most of the code that I write would be side-effect free anyway. In an imperative loop, this would also be true except for updating local variables. If this is the case, `reduce` really is the same as a loop over a collection, except that the names for the state passed between iterations come out better. In the `reduce` version, you can name the parameters to the reducer, but often not the return values. As a reader, one needs to connect the return values to the parameters by position.
(Note that by "loop over a collection", I explicitly mean a looping construct that gives the elements of the collection directly, instead of looping over indices and extracting the elements manually.)
I think what makes reduce less popular is that it takes two lambdas:
- a slightly awkward one that takes a partial result and the next value to produce a new partial result
- one that maps the final partial result to the result
Also, in many languages, when reading the code, you have to skip initialization of the partial result, read the lambda, and then jump back to make sense of the initial values
I think something like awk’s syntax, with BEGIN and END blocks would improve on that. Example of a first go at such syntax (needs work):
Items.BEGIN
min = ∞
max = -∞
sum = 0
n = 0
ITER
min = Min(min,_)
max = Max(max,_)
n += 1
sum += _
RETURN
average = sum / n
(min, max, average)
Advantages:
- items in the partial results have names, making them easier to understand
- result also is easier to understand
Price paid is wordiness, and you cannot simply write a function name for either of the lambdas.
However, I think the latter only is useful in case the partial result is the final result. There, you can keep
(JS/TS is my main language)
I love reduce()! It's a hammer/nail method for me. Everything looks like a problem solvable by reduce. (I'm often wrong on that, but I quite enjoy learning why by trying).
I really like taking the implementation away from the call site, so that the call site reads
const myNewValue = data.reduce(doSomethingMagic);
(and then `doSomethingMagic` is defined somewhere else). So simple.
I failed a job interview once by using reduce() in a coding test. The reviewer didn't understand why I hadn't used a loop. Loops are easier, for sure, but they sprawl and are open to hacking. They can bring in state from outside the loop. They make the call site long (you always have to read the implementation to learn that you don't need to read it). The same interviewer actively liked to have loop bodies modify the loop conditions (e.g. by taking items out of the source array and decrementing the end condition, so the loop would end earlier). That's the kind of "clever" I find unpredictable and hard to think about. Probably a good thing he rejected me.
> The same interviewer actively liked to have loop bodies modify the loop conditions (e.g. by taking items out of the source array and decrementing the end condition, so the loop would end earlier).
Wow. That is the kind of monkey business that would have me running for the exits. Yikes.
Nah. Reduce is less performant and less readable than a regular loop. In my anecdotal experience, only people who want to appear smart and minimize the number of characters prefer reduce.
Reduce definitely does not reduce character count. It's the loop-hacking that does that.
However, I agree it might be less performant, and it's a certain kind of thinking that isn't quickly grokked (and doesn't have to be). I deliberately tried to write my story about the interview so as to make it sound like there's positives and negatives to both positions expressed. _I_ have a preference for that functional style, but I know it's not for everyone. That's totally fine.
I am a typescript dev and I like reduce but also feel like I am the exception.
The standard linter plugin eslint-plugin-unicorn even has a rule "no-array-reduce" that is part of the recommended config, which means most people using this plugin will have no reduce in their codebases:
You didn't get that complaint in Clojure, just like you wouldn't in Scala or Haskell, is that once you have any expectation that your users know a little bit of category theory, and possibly also thinking in types, it's all quite easy. Even fold is kind of easy, with the more complex signature. But passing [A][A,A =>A] kind of sucks for those that don't think of functional programming. and [A][A,B => A] is even worse. It's often bad enough to get people to build a comparator.
Every industry language keeps gaining more and more functional features: Many a new Java version is adding a bunch of scala features with worse syntax. But we don't train people on functional programming at all, so by the time they've built their instincts, passing functions makes no sense to them, immutability is alien, and the idea of a pure function seems irrelevant to them. Thus, they don't get exposed to the building blocks that make reduce seem simple. We always teach them recursion, but the rest? Too little, too late.
I could tell you of a bunch of ways to simplify the signature by, say, mandating that one passes a monoid or something like that, but while the signature would be easier, the very same people that are only used to imperative OO will not have an easier time, because they might have studied 2 years of calculus, but they've never even smelled abstract algebra. You can walk out of not just a programming bootcamp, but many a computer science degree without learning a word of this. Therefore, it all remains complicated.
Clojure specifically elevated the status of the reduce function because of transducers, a powerful but not very intuitive (imo) approach to composing functions.
I like it conceptually, but the main issue for me with reduce is that it's hard to know exactly how the reduction will actually be executed.
The FUBAR potential with map and filter is much smaller, with reduce it depends on deep knowledge of the internals of the reduction itself, which makes it not as useful as a safe abstraction.
It's easy but it ain't simple. Because `f` can do arbitrary things to `x` you have to look at it just to know the general shape of the computation. Reduce gives you a lot of the flexibility of imperative programming but with that also a lot of the problems. Sometimes that's the right trade-off but it is good to be aware that it is a trade-off.
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
I am always happy when I find an opportunity to reduce or zip, so handy.
I also like Lodash'es transform[1]. It's like reduce, but expressly for transforming one collection to another. The signature is a slightly different from reduce in that the accumulator is a collection that is passed as an argument to the iteratee who is expected to mutate the accumulator with no need to return it. This frees up the return value from the iteratee for a new purpose: if the iteratee returns a boolean false, then transform early outs. I have used that feature more than once!
It's simple really: looping is something we've all done a ton. Map is just a specialized version of something you do all the time, made better/simpler: what's not to like (and learn quickly)?
Reduces are used much, much less often. Most devs don't get familiar with them as a result, so every time they have to read a `reduce` they have to re-learn it. And of course, it's a much more involved/complex function, so that exacerbates it.
> reduce is less elegant in languages I use, like JavaScript, Python, and Swift. In my blissful stint as a Clojure developer, I did not get this feedback.
Two notes:
1. reduce if a part of functional programming vocab, so, obviously, a Clojure dev has to internalize it to be able to use the language properly. For other mentioned languages it is not that necessary.
2. As a (mostly) Python dev, I think that list comprehensions and generator expressions are much easier to read and understand than map and filter. Although, people coming from other languages and having limited experience with Python specifically might disagree with me. Perhaps, we should think about inventing some nice syntax sugar that around the concept of `reduce`ing and `fold`ing, similar to what list comp/gen expr in Python did to concepts of `map`ing and `filter`ing.
Actually, now that I think about it, with this new(-ish) (in)famous walrus operator and itertools recipes, I could sort of emulate reduce using gen expr
First, I will need to steal a "consume" function from Itertools Recipes [0]:
from collections import deque
from itertools import islice
def consume(iterator, n=None):
"Advance the iterator n-steps ahead. If n is None, consume entirely."
# Use functions that consume iterators at C speed.
if n is None:
deque(iterator, maxlen=0)
else:
next(islice(iterator, n, n), None)
Isn't it a bit weird, that the fastest and easiest way to consume an iterator entirely is to feed it to a zero length deque? It is weird, but it was just an apéritif, lets move to the main course:
lst = [1, 2, 3]
acc = 0
consume((acc := acc + item for item in lst)) # this is the actual reduce
print(acc)
This is the line where the actual `reduce`ing happens:
consume((acc := acc + item for item in lst))
Basically, we use the fact that a "walrus" expression has a side effect and we just throw away the actual results of the iterator, because we don't need them.
Is it more readable then normal reduce? I'm not sure. If I seen it in the actual production code, it would certainly raised my eyebrows. It is not a part of the normal Python "vocab" - a set of idioms that are considered "pythonic" and that you expect every Python dev to intuitively understand, so I would be very cautious in using it in the code that is intended to be read by other people.
Why did I do it? I don't know, just a fun "what if?" thought experiment.
Of course it is also possible to just create a temporary list and throw it away immediately:
lst = [1, 2, 3]
acc = 0
[acc := acc + item for item in lst] # this is the actual reduce
print(acc)
This way you wouldn't need to take that weird function from Itertools Recipes.
It should be possible to optimize away the creation of the temporary list and avoid wasting CPU and memory on it. But I don't know if CPython actually has this optimization, that's why I didn't mention it initially. I would love someone more knowledgeable in CPython internals to tell me how this would work.
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 remember finally getting what closures and reduce are when I learned Ruby in 2008 for my first Rails job.
A pivotal moment on the same level as when I finally understood how recursion and pointers work in 1995 in my first semester CS classes (taught in Modula 2), two concepts I had only ever read about in programming books, but not been able to understand on my own.
In 2024 I did Advent of Code in Swift, without using mutable state, custom data types or loops, and used reduce rahther generously. [1]
I've seen a lot of technical points about reduce, all of which are true.
But I think the real reason might be even simpler: you can't tell what it does just from the name. What `map` does is consistent with well-known programming jargon. What `filter` does is consistent with the word's everyday meaning. But if you don't already know what `reduce` does, it's name isn't even enough to hazard an educated guess.
That's not true in Clojure because for lisp programmers for two reasons. First, `reduce` is a ubiquitous and well-known concept in lisp.
Second, in most lisps manually doing the same task with imperative code is an ugly verbose eyesore. But in algol-style languages, the imperative alternative is only 1-2 extra lines of very simple code, so using `reduce` is arguably just code golf.
map() and reduce() are equivalent in terms of jargon, IMO. Map also suffers from name collision with dictionaries/objects/whatever your language wants to call a key-value pairing.
I think this along with the other answers discussing the difficulty remembering the specific arguments of `reduce` (especially when varying by language!) are key reasons. After reading this conversational thread, I think maybe Microsoft got it right with LINQ:
- `Where` is perhaps more intuitive than `filter`
- `Select` seems no worse than `map` by invoking SQL-like syntax
- While `reduce` is preserved as `Aggregate`, provide `GroupBy` and other handy methods as the preferred methods. In the code I write, it's probably these other methods that get called 95+% of the time. Who wants to `Aggregate` when they can simply `Sum` for example?
I dislike reduce because people sometimes do wild things in the callback that take a lot of mental effort to understand.
Sometimes people abuse .map as well to do things that are not obvious (i.e. instead of mapping elements of an array to another array, they modify global variables in a for-loop fashion, and discard the result).
But reduce is abused more often and you always need to think really hard if e.g. the initial accumulator is passed or not (it's optional in some languages!), if a correct one is passed (when a compound type is used) and so on.
The only part of "hard to read" that has ever made sense is that the callback takes multiple args and sometimes I can't remember the order of the initial value versus the accumulator.
Incidentally, reduce is also powerful enough to implement both map and filter in terms of itself, though that's more of a teaching exercise than a good recommendation.
I mostly interpret it as of the same spirit with those who oppose proper tail calls because it "ruins" their debugging stack traces.
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.
IDK, in JS I love reduce and think it is invaluable. If you don't care about closures, never used underscore/lodash, and have not written several hundred var self = this; then you don't share my pain. IMO fat arrow const/let kids don't know about walking uphill to school both ways. Also I agree with commenters who use prev instead of acc, it is much easier on my brain to use prev.
TypeScript basically ruined reduce for me though, so there is that.
In my experience, it depends a lot on the language and the folks you work with. I’ve gotten an eyebrow and a stern talking to for using ‘map’ in JavaScript once. Some people are die-hard about statements and keywords and imperative programming and their world view and be myopic.
“We can’t have map in our codebase, we need to be able to hire anyone off the street and have them comfortable in our codebase.”
Well… since when did we hire random people off the street?
I’m used to functional programming. For me, reduce is perfectly normal. Fewer intermediate variables. No pesky statements, just a nice expression. Great.
Buuuut… some languages think implementing tail call optimization is too hard or bad or for ivory tower academics. Or they’re dynamically typed. And then reduce does become difficult to special case and make performant. So even if you like the juice it’s probably not worth the squeeze.
It was a great time working with Haskell professionally. I didn’t have to constantly defend my style of programming! But in “everything” languages… well you do. Everyone has to agree on which subset to use. And programmers are like cats. Good luck getting them to agree on anything. Even once you agree there will always be that one challenging the decree.
In python: I've always thought it's funny that of the list functions (map, filter, reduce?), reduce is the one that was removed, but is the only one that I occasionally reach for. (When I remember it doesn't exist, I'm usually happy to write the more readable three-line for loop.)
The other two can be simply expressed as a list comprehension, but afaik you can't with reduce (and if you can, it's probably awful).
I personally find recursive functions mentally easier to write than folds. Maybe because I can never remember the argument ordering and the inferred types throw me off.
reduce has complexity to handle the edge case of an empty iterable, and also for the case of a binary function with different types for inputs and outputs. That makes it harder to reason about and "uglier" than map and filter. People probably hate sum and product significantly less, both those also have the edge cases of empty iterable, in which case the natural result is 0 for sum and 1 for product sure, but of what type?
While we're on the subject, can someone explain to me why in Rust, you need to annotate the type when you call .sum() on an iterable? For example
let p: i32 = [1i32, 2, 3].iter().sum();
println!("hello {}", p);
That works, but fails if I replace `p: i32` with `p` or `p: i64`, and I cannot find a satisfactory answer in any thread or llm. The obvious question is why the compiler cannot infer the type from the element type of the container, and the naive response to that is for flexibility summing into a bigger type. But in that case, why would `p: i64` be rejected? And what other type is allowed besides i32?
I was going to write a question asking if reduce is the thing I know as accumulate (I think I picked this up from SICP). But then I went to wikipedia, and it seems that an even more common name is fold.
Here's a hypothesis: The fact that the same operation has half a dozen different names makes it sound like there is a lot to learn. If I am totally familiar with fold, and i come upon a reduce, I may need to think more about what's going on, which is distracting.
I don't think map and filter have so many synonyms? I know select for filter, but it seems to me less common.
And in some contexts you have the subtle distinction that fold is linear and reduce requires an associative operation and an identity element (aka a monoid)
My favorite gotcha is Java's `Stream.reduce(accumulator)` doesn't call the accumulator if your stream has zero or one elements. This is used for `min(comparator)` and `max(comparator)`. It's very funny when the comparator throws, but only when you have 2 or more elements.
How is that a gotcha? If there aren't two elements how could you possibly expect a function with two arguments to be called? What would you call it with?
I came to like reduce when I learned clojure transducers. even in clojure, I always go for looping construct before transducer and then both reduce and transducer just clicked at the same time and I like reduce more now.
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.
I’m so confused, how are you supposed to perform aggregation without reduce? This is like saying “I like plus and times, but I don’t like divide because it’s hard.” I mean sure, but you need it??
Not in Elixir. Unless you use tail recursion to simulate the loop. I love reduce and the other functions of the Enum module, so I have 165 calls to reduce in my code base (plus 338 map and 116 filter). It's the swiss army knife of functional programming and I don't see any problem with its usage.
I'm the weird one here. In JS at least, I reach for reduce before map and filter in most cases. Often it is because I want the accumulator, particularly when I have a list of objects with various properties that I wish to sum together in a reduced object.
I agree, but I think a lot of it is variable name abuse on the accumulator, making it unclear.
I've seen a lot of single letter or worse, a coworker who named it "cum" for short which is super not okay
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.
At least in Python, I've found that "reduce" is very rarely needed. Most of the times, "sum" is enough, sometimes with "start" values customized (set it to [] to flatten an array for example). It is both easier to read, faster, and needs no imports. It also works great with list comprehensions - "sum(foo(x) for x in input if x > 5)" is much easier to read than reduce equivalent.
If you are multiplying, you are likely doing heavy math, and you'll be using numpy - which does not need reduce either.
If you are going to return a list of dict, then it's much faster to mutate the results, so using "reduce" will have significant performance implications (unless you want to return input argument, mis-using it as a glorified "for" loop)
And if returning not a list/dict, if you can use "min" or "max" or "any" or "all" or "next" (take the first element), then you should use it - it will be easier to read and faster too.
So what does this leave us for "reduce"? Frankly, not much. I've only seen it in merging immutable status codes, and that was pretty niche usecase to begin with.
(this was all for Python. In other languages without nice list of built-ins reduce might make more sense)
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… :)
Python 3.13.5 (main, Jul 15 2026, 20:25:40) [GCC 14.2.0] on linux
>>> x = [[n]*1000 for n in range(1000)]; import timeit, itertools, functools, operator
>>> timeit.timeit("len(list(sum(x, [])))", number=10, globals=globals())
13.009033881127834
>>> timeit.timeit("len(list(list(functools.reduce(operator.add, x, []))))", number=10, globals=globals())
12.941937348805368
>>> timeit.timeit("len(list(itertools.chain.from_iterable(x)))", number=10, globals=globals())
0.0706032607704401
>>> timeit.timeit("out=[]; [out.extend(i) for i in x]; len(out)", number=10, globals=globals())
0.06334403157234192
>>> timeit.timeit("len([i for a in x for i in a])", number=10, globals=globals())
0.1232151910662651
mutable is fastest, itertools is just a bit slower, list comprehension is 2x slower, both "sum(..., [])" and "reduce" are 200 times slower!
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
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.
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.
Sure, I'm up for some bike-shedding. [0][1] Unless performance demands otherwise, I prefer map+filter because:
1. It's cheaper/faster at communicating intent to humans reading your code. Since a reduce call can do all sorts of interesting things, people need to stare harder to realize "oh, it's just doing a a map and filter together."
2. Things are easier to debug. I can vet the process of transformation (and its intermediate results) and then vet the process of excluding some of those results.
_____
With respect to debugging, a sample form Elixir's REPL where the piping (|>) to the dbg() function reveals the intermediate state:
iex(1)> [5,34,6,2,7,3,1] |>
Enum.map(fn x -> x * x end) |>
Enum.filter(fn x -> x < 10 end) |>
dbg()
[iex:4: (file)]
[5, 34, 6, 2, 7, 3, 1] #=> [5, 34, 6, 2, 7, 3, 1]
|> Enum.map(fn x -> x * x end) #=> [25, 1156, 36, 4, 49, 9, 1]
|> Enum.filter(fn x -> x < 10 end) #=> [4, 9, 1]
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.
Most programmers aren't comfortable with higher-order functions, in my experience. Map and filter are special cases that they may have learnt, but other less common cases they don't understand.
Also, in many languages reduce is hobbled by the fact operators aren't functions. I used it Common Lisp all the time, but it's awkward to use in, say, Python as the function you want is so often an operator. It's also more beautiful if the operators are n-ary like in CL, so the result of (reduce #'+ '()) is the same as (+), ie. 0.
I had a client call me up and complain about my reduce code because it was hard to read and he couldn't tell what was going on. I broke through to him when I added comments to it that showed a particular data structure going in, and what was coming out. Once the transformation was clear, the apparent complexity was no longer a problem, leaving me to believe that the problem with reduce is almost entirely about legibility.
Reduce always makes me question the performance and order of operations. The most I'll do in Python is like
sum(x[1] for x in args)
which is map + reduce. And that's only if x[1] is a number. That's about it. No equivalent in JS. Whenever some JS code has map, I'm like why, and rewrite it as a loop.
This is also assuming we're talking about regular code and not an actual map-reduce framework like Spark.
Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.
Reduce has an accumulator and a 2-arg function and languages are not very consistent amongst each other as to whether it's reduce(initial_acc, callback(acc, elem)) or reduce(callback(acc, elem), initial_acc) or reduce(callback(elem, acc), initial_acc) or what.
Hard to remember. Also some languages have a version of reduce that doesn't take an initial accumulator at all, which is just a footgun waiting for you to hit an empty collection. Also ALSO, the accumulator can easily become awkward in languages that don't support anonymous types or don't support easy mutation of an anonymous type record. Which is most of them!
Haskell got this right. You have foldr (right fold) and foldl' (left fold), and the order of the callback is opposite. If you do a left fold, then the initial accumulator is applied on the left; if you do a right fold, then the initial accumulator is applied on the right.
The mnemonic here is that the folding function (aka the callback) replaces the comma.I find this slightly easier to remember than other languages. In contrast most other languages do not simultaneously provide a left fold and a right fold, so they do not consider this aspect, making things more difficult to remember.
That said I totally agree this requires more brainpower to read and write than map or filter. For this reason I have sometimes refactored code to use foldMap instead of foldr or foldl', so one no longer needs to think of the direction of the fold or the order of arguments.
It's still a complex and more abstract function than map or filter. Those do a single thing that's easy to grasp. reduce/fold can be easily abused to duplicate the effect of most other collection functions, at the cost of making the code less readable. Although for slightly-too-clever people, that could mean you only need to know one function instead of all of them.
But it hurts readability. If you're going to do it, at least don't use it anonymously, but give it a name that clearly describes what's going on.
But even then, there can be hidden performance traps. I've often seen javascript that used reduce and created the new accumulator by using a spread on the old accumulator and adding the new one: `[...acc, newValue]`. But that spread is another iteration inside a loop, turning it from O(n) to O(n^2). A for loop where you append it is much faster.
Since you mention mnemonics, here are the mnemonics I use to remember the (symmetrical) differences between foldr and foldl
https://arialdomartini.github.io/fold-mnemonics
I admit that I have always looked at an explanation like yours with x1,...,xn when using fold because I could never keep it straight in my mind.
In other words, look at the types. The type of the folding function (the first argument) indicates how each fold works.
That's what I tend to do, but since foldr/foldl' is so ubiquitous in Haskell it would be nice if I could just remember the argument order of the callback. kccqzy's explanation (in particular "it replaces the comma") might just help me do that :)
In some programming languages with RPN you can avoid this problem, because it makes sense to put it in the stack as the initial value, and then you can as easily have multiple initial values; and then the callback function can read that from the stack that you had put there, like anything else you will push into the stack to read it back later. For example, in PostScript you can write something like:
However, this is not as good if you want to use the first element as the initial value instead, but still it can be done but it is then not as simple (unlike in programming languages that do not use RPN but instead with function call with arguments, in which case it might be simpler).I guess names as SELECT and WHERE are like SQL (although SQL works differently than other programming langauges).
In GNU Guile `reduce` is described as a special case of `fold`, where the first element is suitable to be used as initial value, while `fold` is more general and lets you specify another initial value. I think that makes a lot of sense.
Also reduce is a weird name.
What about fold?
In rust iterators there's both fold (you supply the initial value) and reduce (it uses the first element as the initial value, doesn't work on empty iterators)
https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...
https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...
Why? It does, after all, reduce a collection to a single value.
The resulting value can be anything you want. You can turn a list into a tree, or another list.
Bad example:
Reduces the list to another list three times as long.It's a reduction in the sense of a transformation (also often seen in complexity theory), not in the "this makes this smaller" everyday usage that I think about first.
I suppose it's just so ... reductive, you know?
In the book "Simply Scheme", map is "every", filter is "keep", and reduce is "accumulate".
> … to call them Select and Where.
While map is a great name, I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them.
I mean, it’s like a colander: you filter noodles and water, but which one do you keep? The noodles, right? But, replace noodles with tea and now you want to keep the water part.
Naming is hard I guess.
There's always the Ruby strategy of just making all the names work. `select` and `filter` are buddies and you can use whichever you want or even go back and forth. Not a fan of `reduce`? That's fine, `inject` has got your back. Miss getting to type `collect` from Java or Rust? Don't worry, just use it instead of `map`, it's the same thing.
I believe Ruby uses names inspired by SmallTalk.
Yeah, Smalltalk has select, reject (inverted filter), collect (map) and inject.
Talking about un-guessable, misleading function names,
C++ std::remove.
I would never have guessed what it does exactly. (It moves elements that match the filter to the front, and moves the end-marker forward. Leaves all the elements in the collection. You need to erase them yourself. )
It returns the new end marker
Oh it's a bit like unordered-delete when using an arena. I guess I would have expected an ordered-delete instead
I've never run into a generic "filter" function which keeps only the non-matching elements.
Smalltalk has #reject: which does that. You could, of course, just wrap a not around the test in the closure, but sometimes reject with a well-named predicate is easier to read.
bsnpApproved := tvShows reject: [ :eachShow | eachShow hasNaughtyContent ].
Common Lisp's filter is remove-if which works this way.
(It also has remove-if-not but that's deprecated and if you use it your code smells.)
The filter keeps the tea... it's just that you then lift the filter out of the cup, carrying the tea with it. Flip your brain around to see it from that direction and it might help you with the mnemonics.
`filter(where:)` like in swift...?
Doesn't seem to help the ambiguity to me.
Maybe those two could be filter_for (the “where” case) and filter_out.
Kotlin has filter and filterNot (it also has separate "reduce" and "fold" functions, dependingon whether you want to specify an initial accumulator value or not)
If you're making tea with a colander something is very wrong ;)
I was thinking an apt analogy might be making stock -- you filter out all the solid food you don't want to keep in the liquid.
And it's a doubly-good analogy, because I have occasionally gotten that confused in real-life as well. Twice in the past ten years I've had a stock boil away for three hours, and then set a colander in the sink and poured it through, only to watch my beautiful stock swirl down the drain because motor-memory made me forget that I wasn't draining pasta but should have put the colander in a bowl...
depends on the size of the sieve, but sometimes one does cook a whole stewpot of tea at once (f.e. in canteen)
> While map is a great name, I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them.
In Common Lisp both functions exist, under the names `remove-if` and `remove-if-not`.
select/reject (Ruby)
It doesn't help that fold/reduce often have different orders depending on the ecosystem. Every few months when I have a reason to reach for `fold` in nutshell I forget that it has the next element as the first arg instead of the second, which is what I'm used to from Rust. I guess I should just be happy I don't need to specify which direction I want like in OCaml.
> Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.
I don't understand. Map takes input of type a and size n and returns output of type b and size n.
Filter takes input of type a and size n and returns output of type a and size ≤ n.
They look nothing alike?
Exactly, and sometimes you also get the indez as argument of the function. `reduce(acc,(acc,elem,idx)=>…)`
and in many case the accumulator is a tuple, and in many cases you need to know the length of the collection ( like average)
all in all, it’s a lot just to avoid a for loop.
An IDE can fix that
Meh, if you need a computer program to understand an API its a bad api.
APIs should make sense inherently. An IDE can band-aid a bad design, but that doesn't make it a good design.
There are lots of APIs where the order of argument isn't obvious, it doesn't mean they're bad designs
That's why I only program in punched cards. If you need a visual editor you're a bad programmer.
Luxury! All I need is a magnetic needle and a steady hand to flip the bits directly on the silicone.
excuse me, but real programmers use butterflies.
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:
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, to help users avoid "footguns". 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...
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`.
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'.
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.
The problem with:
is that it re-allocates O(n) times, even if ret is referenced only once.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.
The binding for acc in the reduce call is still active during the f call, which means there are at least two references to acc.
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?
Does Python actually do that? If the f call throws, you can still observe the (unchanged) binding of acc in reduce.
Fair, I suppose there's no end to the level of insanity that a programmer can do in a dynamic language. I'd think it could perhaps still look to see there's no catch, but maybe eval makes even that impossible.
It might - let's assume it does. 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.
So rather than provide a runtime or compiler optimization, we force the programmer to do it by hand. This is why I don’t like Python philosophically.
I don't believe Python had a compiler in 2006...
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.
It had a runtime
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?
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.
Python has optimized string appending in the form of:
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
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.
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.
2006...would that have been Mondrian?
Yes!
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...
The way I understand it, the map,filter,reduce functions in python exist as pythonic language constructs:
-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
That one is built in:
Maybe the closest is 'join' similar to `",".join([...])`? If we could replace the string with an operator
I liked reduce. You know, back when writing code was actually a thing we all did.
However, in those times of yore, I would often go back and remove it before committing. Unless you’re surrounded by other clever people, or it’s a personal project, you’re leaving behind some very elegant looking anxiety for the less gifted developers. Usually just to save one or two lines of code.
Reduce is a good illustration of the principle of least power[1]: it's powerful, flexible, general and low-level and can technically achieve any combination of summation, map, filter, find/includes, some/any/every, etc. But reduce is misused if it's reimplementing patterns available in higher-level form.
In cases when reduce is required because (for example) JS doesn't have a sum function, it should be kept simple. `arr.reduce((acc, el) => el + acc, 0)` is acceptable if lodash _.sum() is not available.
In cases when reduce is required because the higher-level operations like map/filter aren't flexible enough, decompose the reduction operation into simpler steps and use map/filter with multiple passes, or write a traditional for..of loop.
This principle also explains why enhanced/range/of loops are preferred over counter-based `for` loops, and counter-based loops over `while`. Technically all loops can be handled by `while`, but it's seldom needed because enhanced loops handle the common case with the cleanest syntax. Reduce/while/counter-based `for` loops are antipatterns where higher-level, less powerful abstractions exists.
[1]: https://wiki.c2.com/?PrincipleOfLeastPower
One could also phrase this principle in terms of entropy (in the information-theoretic sense): If I read some code and come across filter() and map(), I already have a pretty good idea of what the code is doing, without even looking at the filter criterion or the mapping function. Entropy is low. (There's only so many filter and map functions you could write for any given type or pair of types.)
Meanwhile, if I see reduce(), "anything" could happen. (Well, of course not anything but the set of possible reducers is surely much larger.) So entropy is high.
Avoid high-entropy constructs in your code. Try to keep entropy as low as possible. (For the same reason, code with a principled approach regarding side effects is a lot better than code where any function could mutate global state at any given time.)
Why is arr.filter().map() better than arr.reduce()? Doesn't arr.reduce() only loop once through the array?
For me it's about the speed of understanding what the code does. Because filter and map are very constrained in what they can do they quickly tell me a lot about the shape of the computation I'm working with. In contrast reduce is much more flexible and so I need to do a much more detailed analysis to just answer a basic question like "is the result a scalar or another collection?".
Exactly. If I need just filter/map/some etc., I use it. But if I need a combination of more than one, that's a job for reduce().
Chained filter and map don't necessarily iterate multiple times. They certainly can but depending on how things are built they very often run as a single loop with the operations chained.
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.
Isn't reduce usually used for monoidal operations? Or do people implicitly absue ordering?
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)
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[1] 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.
[1]Or if they have, their only encounter with it is the "a monad is just a monoid in the category of endofunctors" meme.
I do know what a monoid is, but a monad in the category of endofunctors is the scary word for me :sob:
It just means if you have some functor F (generic type with a well-behaved `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 an "identity" function wrap: A->F[A] (e.g. x -> [x]). Identity in the sense that "multiplying" (flattening) with wrap does nothing. i.e. wrap(flatten(x)) = flatten(wrap(x)) = x when those things make sense.
So basically wrapping and flattening behave in a sane way. Flatten is your multiply, wrap is your multiplicative identity, and it's like a monoid if you squint.
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:
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)
If the contraint is not in the signature, and cannot trigger a test failure with typical implementation, it doesn't exist.
It's pairwise, not global reasoning.
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.
> 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.
> 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.
Right. It's just one more thing you have to think about with Reduce that's not something you have to consider with Map/Filter.
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.
Reduce is like `fold` in Haskell right? Fold in Haskell has many variant, I forgot exactly which, but I remember there were many.
I never met so many different variants of the `map` or `filter` function in Haskell.
Maybe this shows, in a different way from the reasons in the article, why reduce is harder than map/filter.
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
> or recursion schemes
Fold is a recursion scheme
More complicated recursion schemes are progressively harder to read. Probably not great if you are not doing code golf
I’ve never ever heard while described as a smell, or even slightly smelly.
Care to explain?
I assume OP refers to the cases where "while" is used to re-implement existing operations... imagine finding code like this:
sure, there may be a good reason to implement things this way (maybe "todo" grows during iteration?), but maybe not, and then the loop should be instead simplified to: (as an aside, this is exactly the case where the comments are required: "# not using for loop because todo might grow" will make it clear it's an intentional decision and not hallucination or something written from ignorance)You can use iterators in a while loop like your for example, making it look as clean as the for.
I feel like this is a case of personal preference over actual issue.
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.
If you can smell it, there's something fishy in the neighborhood
Ive only used reduce at work half a dozen times and it does raise an eyebrow each time.
But for unioning a bunch of spark dataframes together i think
is much nicer than People just get a bit funny, especially now you have to import it from functoolsCame here to comment this. I work on a team of functional-adverse devs, but they all happily use this one.
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.
> Put me anecdotally in the opposite bucket.
The fact that you wrote this comment with Hindley-Milner-ish notation already makes your an outlier.
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.
> `fold` is awesome and super useful. It's the easiest and most convenient way to turn a collection into a single value.
You will eventually learn about something called "for loop", and it will be nice.
There are way more places where a simple typo will ruin you in a for loop than a reduce or fold or map. Using briefer abstractions in place of nested loops is almost always preferable.
> Using briefer abstractions in place of nested loops is almost always preferable.
Indeed, this is why everyone knows the J programming language.
Nah. It involves multiple passes and setting the answer to the wrong value before (hopefully) setting it to the right value.
Plus it forces you out of whatever lazy/streaming paradigm you had going on. If your foldr produces a list, downstream can start consuming it in constant memory as long as you let it do its thing.
fold kinda does too, for setting the first combined value that you are assembling, and thus on an empty list you end up with that wrong value, same as the for loop
japgolly’s signature for reduce above is slightly wrong, it should be `[A] -> ((A,A) -> A) -> Maybe A`.
I.e. there is no initial value to pass in, but the result is an Optional to handle the empty iterator case. That’s how rust does it, for example:
https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...
No, the sum of the first ten natural numbers is always 55. It is not "initialised" to some other number beforehand.
For me it's the name[0]. map puts out an array that has been mapped from another array. filter puts out an array that is a filter of the input array. both of those are always true. reduce, on the other hand, may put out a reduction of the input array (probably most of the time), but the fact that it may not means that what is happening is not actually a reduction. In languages like js/ts, you don't even have to return anything of the same type as the input array's elements. You could literally "reduce" and array of integers to a cancellation token, or a state object, or anything else.
I realize it's not the most efficient way to work, but I like my code to read like instructions. There's nothing reduce will do that a for loop won't accomplish and the for loop (+ an accumulator, of course) is more clearly "readable" than reduce. If I read map, I know what's going on. If I read filter, I know what's going on. If I read reduce, I have to figure out what's going on, even if I'm pretty sure what is going on. If I could rely on reduce to always give me back an element of the input array, I would use it more. But since it can give back anything, I prefer the simplicity of a for loop.
[0] I don't have any suggestions for "better" names because the whole operation is hard to sum up in a word? "dispatch" makes sense, as a function dispatching a function over each element in an array, but it masks the concept of accumulation from return values. "transform" is accurate, but hardly descriptive at all. the list goes on. It's an undeniably useful little function, it's just hard to make it easy to understand and therefore debug.
Ruby adds an alias `inject` for reduce. The #1 way I see it used there is like this:
But I honestly very rarely use it (by either name) outside of a couple of pasted-in snippets (that I can't recall right now) where the strategy fits exceptionally well, probably because of the dumb reason that I tend to forget which block argument comes first (accumulator, or iterated item)! With other two-item argument lists such as `Hash#map` it being `key, value` makes sense, but with reduce/inject I don't see an obvious order. And I guess I learned before it was likely that some kind of AI autocomplete would be filling the args in for me.The name inject and the argument order comes from Smalltalk (Ruby is heavily inspired by it). In Smalltalk arguments are part of the message name:
collection inject: aValue into: aBlock
Ruby inject appears to be derived from Smalltalk #inject:into:
#(1 2 3 4 5 6 7) inject: 10 into: [ :sum :each | sum + each squared ].
or from your example:
someHash := myArray inject: (Dictionary new) into: [ :accumulator :item | ... ].
The way I remember the order is it reflects the assignment you'd do is a while loop, sum := sum + each.
It reduces n items to one item, recursively. The items don’t have to have the same type. Arguably accumulate is a more fitting name. I think of “reduce” as in cooking, boiling a volume of stuff down to some essence.
I also agree that a for loop is often clearer.
I like the name `fold` as used by Haskell, Racket, et al. It gives me an image of folding up a long list into a ball, one chunk at a time.
I like fold too, but I can never remember foldl vs foldr, it's always backwards to what I expect somehow
https://news.ycombinator.com/item?id=49736033 may help :)
> You could literally "reduce" and array of integers to a cancellation token, or a state object, or anything else
This is what reduce does, though? It reduces a list to a single thing. It seems like you're thinking of filter.
There is a big difference in there I think.
'for' loop is mutating.
Using 'reduce', you can do the same functionally. In some (somewhat) purely functional languages, there is no choice.
It doesn't have to be exactly correct. It just need to express intuitively the most common use(es?).
Aggregate, accumulate, combine for example.
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
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.
The type annotation gymnastics you sometimes have to do when reducing to an object in TypeScript are annoying.
allTasks.reduce((acc, item) => { acc[item.label] = t => t.item.label === item.label; return acc; }, {} as Record<string, (t: typeof tasks[number]) => boolean>)
I agree it's a bit annoying, but a better solution than using `as` is just telling reduce what its generic type should be:
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 })
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.
It literally may be a syntax thing, but I too can never remember the exact arguments to put where so I never use it.
I think if `reduce` looked more functional or more like Erlang code, it'd be easier to read and digest.
> accumulator
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 );
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.
Speaking as someone who often tries to reduce my use of reduce by replacing it with map and filter where possible, for me, falling back to reduce is analogous to falling back to a while loop or a for loop: I avoid it if I can.
The problem with reduce is that it can do so much, and therefore it is less clear when reading it quickly what it might be doing.
I think this is because in an imperative language, `reduce` does not actually give you much over a `for item in collection` loop. With `map` and `filter`, you immediately learn something about the result (it's a list of the same length as the original, with each item only depending on the corresponding original item; it's a list containing some of the original elements unchanged and nothing else). This is useful, so `map` and `filter` are good.
With `reduce`, the result could be anything, and in an imperative language, side effects are also possible. So it's just a loop with worse syntax.
(Admittedly, in an imperative language, `map` and `filter` could also have side effects, though I think most people would consider this bad style.)
I think that in every imperative language that offers `map`, `filter`, `reduce`, or similar, the written contract of this API should state that any higher-order function handed to it as an argument must be free from side effects.
I think I’ve seen several language core APIs have this in their contract, e.g. `Stream#reduce` in Java [0] (emphasis mine):
> accumulator - an *associative, non-interfering, stateless* function for combining two values
[0]: https://docs.oracle.com/javase/8/docs/api/java/util/stream/S...
In Rust these specifically take `FnMut`, a function which can update internal/borrowed state, rather than `Fn` which can't easily. In `map` or `filter` you shouldn't rely on the iteration order so that's not often useful – maybe something 'logically' stateless but which needs a mutable connection/threadpool/cache, or eg a counter which is really an ancillary reduction. There's even `inspect` which is explicitly for such side effects. In `fold`, the order is guaranteed and you could use it for a state machine, a fiddly `zip` with other mutable iterators, etc – something you need to perform the reduction, but which isn't really an output, I think you could reasonably write either
I mean, most of the code that I write would be side-effect free anyway. In an imperative loop, this would also be true except for updating local variables. If this is the case, `reduce` really is the same as a loop over a collection, except that the names for the state passed between iterations come out better. In the `reduce` version, you can name the parameters to the reducer, but often not the return values. As a reader, one needs to connect the return values to the parameters by position.
(Note that by "loop over a collection", I explicitly mean a looping construct that gives the elements of the collection directly, instead of looping over indices and extracting the elements manually.)
Even though it makes print debugging harder, I think it would be better if the language enforced such a contract.
I think what makes reduce less popular is that it takes two lambdas:
- a slightly awkward one that takes a partial result and the next value to produce a new partial result
- one that maps the final partial result to the result
Also, in many languages, when reading the code, you have to skip initialization of the partial result, read the lambda, and then jump back to make sense of the initial values
I think something like awk’s syntax, with BEGIN and END blocks would improve on that. Example of a first go at such syntax (needs work):
Advantages:- items in the partial results have names, making them easier to understand
- result also is easier to understand
Price paid is wordiness, and you cannot simply write a function name for either of the lambdas.
However, I think the latter only is useful in case the partial result is the final result. There, you can keep
if you want to.(JS/TS is my main language) I love reduce()! It's a hammer/nail method for me. Everything looks like a problem solvable by reduce. (I'm often wrong on that, but I quite enjoy learning why by trying).
I really like taking the implementation away from the call site, so that the call site reads
(and then `doSomethingMagic` is defined somewhere else). So simple.I failed a job interview once by using reduce() in a coding test. The reviewer didn't understand why I hadn't used a loop. Loops are easier, for sure, but they sprawl and are open to hacking. They can bring in state from outside the loop. They make the call site long (you always have to read the implementation to learn that you don't need to read it). The same interviewer actively liked to have loop bodies modify the loop conditions (e.g. by taking items out of the source array and decrementing the end condition, so the loop would end earlier). That's the kind of "clever" I find unpredictable and hard to think about. Probably a good thing he rejected me.
> The same interviewer actively liked to have loop bodies modify the loop conditions (e.g. by taking items out of the source array and decrementing the end condition, so the loop would end earlier).
Wow. That is the kind of monkey business that would have me running for the exits. Yikes.
> Everything looks like a problem solvable by reduce. (I'm often wrong on that, but I quite enjoy learning why by trying).
I agree, but I think that’s kind of the objection. It can be tempting to write your code as little brainteasers but…
> I failed a job interview once by using reduce() in a coding test. The reviewer didn't understand why I hadn't used a loop.
Honestly, sounds like the reviewer failed the interview, not the other way around.
Nah. Reduce is less performant and less readable than a regular loop. In my anecdotal experience, only people who want to appear smart and minimize the number of characters prefer reduce.
Reduce definitely does not reduce character count. It's the loop-hacking that does that.
However, I agree it might be less performant, and it's a certain kind of thinking that isn't quickly grokked (and doesn't have to be). I deliberately tried to write my story about the interview so as to make it sound like there's positives and negatives to both positions expressed. _I_ have a preference for that functional style, but I know it's not for everyone. That's totally fine.
I don't know about JavaScript, but those statements are definitely not universally true in other languages.
I am a typescript dev and I like reduce but also feel like I am the exception.
The standard linter plugin eslint-plugin-unicorn even has a rule "no-array-reduce" that is part of the recommended config, which means most people using this plugin will have no reduce in their codebases:
https://github.com/sindresorhus/eslint-plugin-unicorn/blob/m...
You didn't get that complaint in Clojure, just like you wouldn't in Scala or Haskell, is that once you have any expectation that your users know a little bit of category theory, and possibly also thinking in types, it's all quite easy. Even fold is kind of easy, with the more complex signature. But passing [A][A,A =>A] kind of sucks for those that don't think of functional programming. and [A][A,B => A] is even worse. It's often bad enough to get people to build a comparator.
Every industry language keeps gaining more and more functional features: Many a new Java version is adding a bunch of scala features with worse syntax. But we don't train people on functional programming at all, so by the time they've built their instincts, passing functions makes no sense to them, immutability is alien, and the idea of a pure function seems irrelevant to them. Thus, they don't get exposed to the building blocks that make reduce seem simple. We always teach them recursion, but the rest? Too little, too late.
I could tell you of a bunch of ways to simplify the signature by, say, mandating that one passes a monoid or something like that, but while the signature would be easier, the very same people that are only used to imperative OO will not have an easier time, because they might have studied 2 years of calculus, but they've never even smelled abstract algebra. You can walk out of not just a programming bootcamp, but many a computer science degree without learning a word of this. Therefore, it all remains complicated.
> once you have any expectation that your users know a little bit of category theory
I don't know that's a safe assumption tbh. Try throwing them some chapter 2 exercises from any category theory textbook.
Clojure specifically elevated the status of the reduce function because of transducers, a powerful but not very intuitive (imo) approach to composing functions.
I like it conceptually, but the main issue for me with reduce is that it's hard to know exactly how the reduction will actually be executed.
The FUBAR potential with map and filter is much smaller, with reduce it depends on deep knowledge of the internals of the reduction itself, which makes it not as useful as a safe abstraction.
What's hard to understand about it? It's just
It's easy but it ain't simple. Because `f` can do arbitrary things to `x` you have to look at it just to know the general shape of the computation. Reduce gives you a lot of the flexibility of imperative programming but with that also a lot of the problems. Sometimes that's the right trade-off but it is good to be aware that it is a trade-off.
The name itself is confusing to begin with.
I 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.
It's because it reduces data dimensionality. From 2d to 1d and from 1d to 0d (scalar).
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
No, reduce has exactly the same time complexity as map and filter.
Sorry I changed problems a bit and started talking about me trying to understand matrices lol
I am always happy when I find an opportunity to reduce or zip, so handy.
I also like Lodash'es transform[1]. It's like reduce, but expressly for transforming one collection to another. The signature is a slightly different from reduce in that the accumulator is a collection that is passed as an argument to the iteratee who is expected to mutate the accumulator with no need to return it. This frees up the return value from the iteratee for a new purpose: if the iteratee returns a boolean false, then transform early outs. I have used that feature more than once!
[1] https://lodash.com/docs#transform
It's simple really: looping is something we've all done a ton. Map is just a specialized version of something you do all the time, made better/simpler: what's not to like (and learn quickly)?
Reduces are used much, much less often. Most devs don't get familiar with them as a result, so every time they have to read a `reduce` they have to re-learn it. And of course, it's a much more involved/complex function, so that exacerbates it.
It would be clearer if the operation were part of the name. The most common operations have good names, like sum(), product(), concat(), and so on.
If there's no standard function for it, it's trivial to write a utility function.
And as part of writing the function, give it a good name and think a bit about the order of operations?
So I think reduce() is just unnecessarily generic, unless it's part of a more complicated system like running a map-reduce.
Some conventions are socially made... In C, some uses
#if 0
#endifbut most of the cases people just use
/* comments
* these_lines_are();
* not_executed();
*
* end comment */
Then, why?
#if 0
#endif
looks clear and it definitely says how a computer skips many lines.
But we just don't use it because it implies low-level knowledge "that every C developers have"
My C is really rusty but aren't those different ? If using #if/#endif the compiler won't even see the comments.
> reduce is less elegant in languages I use, like JavaScript, Python, and Swift. In my blissful stint as a Clojure developer, I did not get this feedback.
Two notes:
1. reduce if a part of functional programming vocab, so, obviously, a Clojure dev has to internalize it to be able to use the language properly. For other mentioned languages it is not that necessary.
2. As a (mostly) Python dev, I think that list comprehensions and generator expressions are much easier to read and understand than map and filter. Although, people coming from other languages and having limited experience with Python specifically might disagree with me. Perhaps, we should think about inventing some nice syntax sugar that around the concept of `reduce`ing and `fold`ing, similar to what list comp/gen expr in Python did to concepts of `map`ing and `filter`ing.
Actually, now that I think about it, with this new(-ish) (in)famous walrus operator and itertools recipes, I could sort of emulate reduce using gen expr
First, I will need to steal a "consume" function from Itertools Recipes [0]:
Isn't it a bit weird, that the fastest and easiest way to consume an iterator entirely is to feed it to a zero length deque? It is weird, but it was just an apéritif, lets move to the main course: This is the line where the actual `reduce`ing happens: Basically, we use the fact that a "walrus" expression has a side effect and we just throw away the actual results of the iterator, because we don't need them.Is it more readable then normal reduce? I'm not sure. If I seen it in the actual production code, it would certainly raised my eyebrows. It is not a part of the normal Python "vocab" - a set of idioms that are considered "pythonic" and that you expect every Python dev to intuitively understand, so I would be very cautious in using it in the code that is intended to be read by other people.
Why did I do it? I don't know, just a fun "what if?" thought experiment.
[0] https://docs.python.org/3/library/itertools.html#itertools-r...
Of course it is also possible to just create a temporary list and throw it away immediately:
This way you wouldn't need to take that weird function from Itertools Recipes.It should be possible to optimize away the creation of the temporary list and avoid wasting CPU and memory on it. But I don't know if CPython actually has this optimization, that's why I didn't mention it initially. I would love someone more knowledgeable in CPython internals to tell me how this would work.
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 remember finally getting what closures and reduce are when I learned Ruby in 2008 for my first Rails job.
A pivotal moment on the same level as when I finally understood how recursion and pointers work in 1995 in my first semester CS classes (taught in Modula 2), two concepts I had only ever read about in programming books, but not been able to understand on my own.
In 2024 I did Advent of Code in Swift, without using mutable state, custom data types or loops, and used reduce rahther generously. [1]
[1] https://github.com/search?q=repo%3Aantfarm%2FAdventOfCode202...
I've seen a lot of technical points about reduce, all of which are true.
But I think the real reason might be even simpler: you can't tell what it does just from the name. What `map` does is consistent with well-known programming jargon. What `filter` does is consistent with the word's everyday meaning. But if you don't already know what `reduce` does, it's name isn't even enough to hazard an educated guess.
That's not true in Clojure because for lisp programmers for two reasons. First, `reduce` is a ubiquitous and well-known concept in lisp.
Second, in most lisps manually doing the same task with imperative code is an ugly verbose eyesore. But in algol-style languages, the imperative alternative is only 1-2 extra lines of very simple code, so using `reduce` is arguably just code golf.
map() and reduce() are equivalent in terms of jargon, IMO. Map also suffers from name collision with dictionaries/objects/whatever your language wants to call a key-value pairing.
Every single `reduce` can be replaced with a more intuitive `groupBy`, `partition`, `mapValues`, `keyBy`, etc.
Reduce can approximate anything, that doesn't mean we should use it.
My favorite antipattern is
Like, why? Not only is this ridiculously inefficient O(N^2), it's also longer and less understandable than "build a new map" version.I think this along with the other answers discussing the difficulty remembering the specific arguments of `reduce` (especially when varying by language!) are key reasons. After reading this conversational thread, I think maybe Microsoft got it right with LINQ: - `Where` is perhaps more intuitive than `filter` - `Select` seems no worse than `map` by invoking SQL-like syntax - While `reduce` is preserved as `Aggregate`, provide `GroupBy` and other handy methods as the preferred methods. In the code I write, it's probably these other methods that get called 95+% of the time. Who wants to `Aggregate` when they can simply `Sum` for example?
This one doesn't seem expressible in those terms:
I dislike reduce because people sometimes do wild things in the callback that take a lot of mental effort to understand.
Sometimes people abuse .map as well to do things that are not obvious (i.e. instead of mapping elements of an array to another array, they modify global variables in a for-loop fashion, and discard the result).
But reduce is abused more often and you always need to think really hard if e.g. the initial accumulator is passed or not (it's optional in some languages!), if a correct one is passed (when a compound type is used) and so on.
> sometimes do wild things in the callback that take a lot of mental effort to understand
And even when they don't, you have to spend effort to determine that they aren't.
One of the books that most affected my understanding, ability, and joy of programming was Mark Jason Dominus' "Higher Order Perl."
So I love reduce, and have for many years.
I am using reduce to replace the nonlinear loop in the code instead of the for statement.
I like it, but it is by far the most ungainly of the three with the most footguns in it's usage.
While not as functionally pure, I always appreciate the Ruby each_with_object https://ruby-doc.org/3.4.1/Enumerable.html#method-i-each_wit... as a more pleasant interface for it.
I find `reduce` useful for operations where:
- arg1, arg2 and return value are all of the same type e.g `ADD`, `MAX`, `CONCAT` etc
- and there is an identity value e.g zero for `ADD`, -math.inf for `MAX`
I recommend checking this article[1] on how monoids play nicely with reduce.
[1] https://fsharpforfunandprofit.com/posts/monoids-without-tear...
The only part of "hard to read" that has ever made sense is that the callback takes multiple args and sometimes I can't remember the order of the initial value versus the accumulator.
Incidentally, reduce is also powerful enough to implement both map and filter in terms of itself, though that's more of a teaching exercise than a good recommendation.
I mostly interpret it as of the same spirit with those who oppose proper tail calls because it "ruins" their debugging stack traces.
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.
It's part of the functional trio: map, filter, reduce--and half of MapReduce.
IDK, in JS I love reduce and think it is invaluable. If you don't care about closures, never used underscore/lodash, and have not written several hundred var self = this; then you don't share my pain. IMO fat arrow const/let kids don't know about walking uphill to school both ways. Also I agree with commenters who use prev instead of acc, it is much easier on my brain to use prev.
TypeScript basically ruined reduce for me though, so there is that.
In my experience, it depends a lot on the language and the folks you work with. I’ve gotten an eyebrow and a stern talking to for using ‘map’ in JavaScript once. Some people are die-hard about statements and keywords and imperative programming and their world view and be myopic.
“We can’t have map in our codebase, we need to be able to hire anyone off the street and have them comfortable in our codebase.”
Well… since when did we hire random people off the street?
I’m used to functional programming. For me, reduce is perfectly normal. Fewer intermediate variables. No pesky statements, just a nice expression. Great.
Buuuut… some languages think implementing tail call optimization is too hard or bad or for ivory tower academics. Or they’re dynamically typed. And then reduce does become difficult to special case and make performant. So even if you like the juice it’s probably not worth the squeeze.
It was a great time working with Haskell professionally. I didn’t have to constantly defend my style of programming! But in “everything” languages… well you do. Everyone has to agree on which subset to use. And programmers are like cats. Good luck getting them to agree on anything. Even once you agree there will always be that one challenging the decree.
In python: I've always thought it's funny that of the list functions (map, filter, reduce?), reduce is the one that was removed, but is the only one that I occasionally reach for. (When I remember it doesn't exist, I'm usually happy to write the more readable three-line for loop.)
The other two can be simply expressed as a list comprehension, but afaik you can't with reduce (and if you can, it's probably awful).
I personally find recursive functions mentally easier to write than folds. Maybe because I can never remember the argument ordering and the inferred types throw me off.
reduce has complexity to handle the edge case of an empty iterable, and also for the case of a binary function with different types for inputs and outputs. That makes it harder to reason about and "uglier" than map and filter. People probably hate sum and product significantly less, both those also have the edge cases of empty iterable, in which case the natural result is 0 for sum and 1 for product sure, but of what type?
While we're on the subject, can someone explain to me why in Rust, you need to annotate the type when you call .sum() on an iterable? For example
That works, but fails if I replace `p: i32` with `p` or `p: i64`, and I cannot find a satisfactory answer in any thread or llm. The obvious question is why the compiler cannot infer the type from the element type of the container, and the naive response to that is for flexibility summing into a bigger type. But in that case, why would `p: i64` be rejected? And what other type is allowed besides i32?I was going to write a question asking if reduce is the thing I know as accumulate (I think I picked this up from SICP). But then I went to wikipedia, and it seems that an even more common name is fold.
Here's a hypothesis: The fact that the same operation has half a dozen different names makes it sound like there is a lot to learn. If I am totally familiar with fold, and i come upon a reduce, I may need to think more about what's going on, which is distracting.
I don't think map and filter have so many synonyms? I know select for filter, but it seems to me less common.
And in some contexts you have the subtle distinction that fold is linear and reduce requires an associative operation and an identity element (aka a monoid)
Map maps a value into another value. It's a function call. Easy to understand.
Filter picks values according to a rule. It's a select from where condition. Maybe not as easy as map but familiar.
Reduce is, what? Even the name is ill fated. Who wants to be reduced? Hence, harder to understand and probably not as common as the other two.
My favorite gotcha is Java's `Stream.reduce(accumulator)` doesn't call the accumulator if your stream has zero or one elements. This is used for `min(comparator)` and `max(comparator)`. It's very funny when the comparator throws, but only when you have 2 or more elements.
How is that a gotcha? If there aren't two elements how could you possibly expect a function with two arguments to be called? What would you call it with?
I came to like reduce when I learned clojure transducers. even in clojure, I always go for looping construct before transducer and then both reduce and transducer just clicked at the same time and I like reduce more now.
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.
I’m so confused, how are you supposed to perform aggregation without reduce? This is like saying “I like plus and times, but I don’t like divide because it’s hard.” I mean sure, but you need it??
Yeah, but you never _need_ reduce. You can just have a boring loop.
I like boring code.
Not in Elixir. Unless you use tail recursion to simulate the loop. I love reduce and the other functions of the Enum module, so I have 165 calls to reduce in my code base (plus 338 map and 116 filter). It's the swiss army knife of functional programming and I don't see any problem with its usage.
I'm the weird one here. In JS at least, I reach for reduce before map and filter in most cases. Often it is because I want the accumulator, particularly when I have a list of objects with various properties that I wish to sum together in a reduced object.
In imperative languages, it's a leaky abstraction not reducing the cognition overhead, compared with the plain loop.
Reduce introduces state (accumulator), unlike map/filter which normally are used for immutability.
I use both, but do not like reduce at all. It's harder to read, yes. But I see the point of using them all.
I agree, but I think a lot of it is variable name abuse on the accumulator, making it unclear. I've seen a lot of single letter or worse, a coworker who named it "cum" for short which is super not okay
Totally get it. `reduce` feels like a hammer for every nail; often `map` or `filter` makes intent clearer for others.
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.
Reduce with barriers is essential (and amazingly powerful) in parallel functional programming languages like CUDA Thrust.
Yea, reduce is most useful as a parallel operation, like in MapReduce
(Or, at minimum, when the reduction operation is commutative)
Yeah, it usually adds cognitive load for anything beyond basic summation. Simpler to just use a good old `for` loop.
I like it, but I don't use it anywhere near as much as other built-in closures.
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.
At least in Python, I've found that "reduce" is very rarely needed. Most of the times, "sum" is enough, sometimes with "start" values customized (set it to [] to flatten an array for example). It is both easier to read, faster, and needs no imports. It also works great with list comprehensions - "sum(foo(x) for x in input if x > 5)" is much easier to read than reduce equivalent.
If you are multiplying, you are likely doing heavy math, and you'll be using numpy - which does not need reduce either.
If you are going to return a list of dict, then it's much faster to mutate the results, so using "reduce" will have significant performance implications (unless you want to return input argument, mis-using it as a glorified "for" loop)
And if returning not a list/dict, if you can use "min" or "max" or "any" or "all" or "next" (take the first element), then you should use it - it will be easier to read and faster too.
So what does this leave us for "reduce"? Frankly, not much. I've only seen it in merging immutable status codes, and that was pretty niche usecase to begin with.
(this was all for Python. In other languages without nice list of built-ins reduce might make more sense)
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… :)
wow, TIL!
mutable is fastest, itertools is just a bit slower, list comprehension is 2x slower, both "sum(..., [])" and "reduce" are 200 times slower!Yeah this is the kind of reason people dislike reduce
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
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.
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.
Sure, I'm up for some bike-shedding. [0][1] Unless performance demands otherwise, I prefer map+filter because:
1. It's cheaper/faster at communicating intent to humans reading your code. Since a reduce call can do all sorts of interesting things, people need to stare harder to realize "oh, it's just doing a a map and filter together."
2. Things are easier to debug. I can vet the process of transformation (and its intermediate results) and then vet the process of excluding some of those results.
_____
With respect to debugging, a sample form Elixir's REPL where the piping (|>) to the dbg() function reveals the intermediate state:
[0] https://en.wikipedia.org/wiki/Law_of_triviality[1] https://www.smbc-comics.com/comic/noun
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 can have another set of variables in the header too. You can simulate it more readably even if you need to call the lambda.
reduce is great - love it.
Most programmers aren't comfortable with higher-order functions, in my experience. Map and filter are special cases that they may have learnt, but other less common cases they don't understand.
Also, in many languages reduce is hobbled by the fact operators aren't functions. I used it Common Lisp all the time, but it's awkward to use in, say, Python as the function you want is so often an operator. It's also more beautiful if the operators are n-ary like in CL, so the result of (reduce #'+ '()) is the same as (+), ie. 0.
Not really, programmers only educated in traditional imperative programming I would assert.
I've always like reduce myself, didn't realize others had a negative attitude towards it.
I had a client call me up and complain about my reduce code because it was hard to read and he couldn't tell what was going on. I broke through to him when I added comments to it that showed a particular data structure going in, and what was coming out. Once the transformation was clear, the apparent complexity was no longer a problem, leaving me to believe that the problem with reduce is almost entirely about legibility.
reduce with barriers is essential in parallel functional programming. See the CUDA thrust package.
Reduce always makes me question the performance and order of operations. The most I'll do in Python is like
which is map + reduce. And that's only if x[1] is a number. That's about it. No equivalent in JS. Whenever some JS code has map, I'm like why, and rewrite it as a loop.This is also assuming we're talking about regular code and not an actual map-reduce framework like Spark.
I like neither of the three and prefer for loops and if statements instead. Yay for shallower stacks!
Alternative theory - reduce is badly named.
combine, accumulate it aggregate would have way more use.
I like it, but don't care for the name. I find it easier to think about in terms of an accumulator.
you guys still reading and review code with ur eyes and brain?