Anecdotally, programmers dislike "reduce"(evanhahn.com) |
Anecdotally, programmers dislike "reduce"(evanhahn.com) |
combine, accumulate it aggregate would have way more use.
I like boring code.
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 find the two ways that you call it to be a bit annoying (not a showstopper). It just seems a bit "kludgy" to me.
(Or, at minimum, when the reduction operation is commutative)
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)
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]
sum(x[1] for x in args)
This is also assuming we're talking about regular code and not an actual map-reduce framework like Spark.
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.
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
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!
Reduce can approximate anything, that doesn't mean we should use it.
My favorite antipattern is
items.reduce(
(acc, item) => ({
...acc,
[item.id]: item,
}), {}
);
from functools import reduce
df = reduce(DataFrame.union, dfs)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.
And even when they don't, you have to spend effort to determine that they aren't.
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.
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...
So I love reduce, and have for many years.
- 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...
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.
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.
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.
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.
x = mapreduce(f, r, arr, init)
equivalent to
x=init
for e in arr
r(x, f(e))
Of course, if r is ever something different than a simple operator, slap yourself. But otherwise it’s an absurdly powerful construct.
“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.
TypeScript basically ruined reduce for me though, so there is that.
#if 0
these_lines_are();
not_executed();
but 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"
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.
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).
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);
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.
myStream.min(Comparator.comparingDouble((obj) -> { ... }));
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)
lst = [1, 2, 3]
acc = 0
consume((acc := acc + item for item in lst)) # this is the actual reduce
print(acc)
consume((acc := acc + item for item in lst))
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...
lst = [1, 2, 3]
acc = 0
[acc := acc + item for item in lst] # this is the actual reduce
print(acc)
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.
min is a generic method. All it knows is it has a Stream<T> and a function taking two Ts. The only thing it can do is plug in Ts it gets from the stream.
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!
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
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.
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.
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> bYou want the accumulator second to match up with `cons` and similar functions that expect an initial/existing value second.
Luckily the functional languages I use the most are sane in that respect.
0 exch {add} forall
I guess names as SELECT and WHERE are like SQL (although SQL works differently than other programming langauges).
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.
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. )
> I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them
`filter(where:)` like in swift...?
In Common Lisp both functions exist, under the names `remove-if` and `remove-if-not`.
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...
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?
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.
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
...
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...
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.
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)
[1]Or if they have, their only encounter with it is the "a monad is just a monoid in the category of endofunctors" meme.
In languages like python or Java though, you don't really have access to many of the higher power functional traversals however. So that puts you into a similar kind of bind as working in a language with only while loops
Care to explain?
i = 0
while i != len(todo):
process(todo[i])
i = i + 1
for value in todo:
process(value)
That said, I personally don’t think it’s smelly at all.
Fold is a recursion scheme
More complicated recursion schemes are progressively harder to read. Probably not great if you are not doing code golf
`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.
But for unioning a bunch of spark dataframes together i think
df = reduce(DataFrame.union, list_of_dfs)
df, *rest = list_of_dfs
for other in rest:
df = df.union(other)
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.)
Reduce could mean one of quite a few things. (How many folds does Haskell have? At least six.) And most of them are, in a sense, so trivial that there is no real benefit to spelling it “fold” or “reduce” instead of just calculating it explicitly. (Okay, one can sometimes lazily fold a lazy list, for example by applying the identity. This is not the normal case, especially in eager languages, which is most of them.) And, if you just write a loop instead of “reduce”, then it’s more obvious what’s going on and why the code might be inefficient.
IMO the actually interesting case of reduce is the associative case, which can be parallelized. This is not the default in most languages.
array.reduce(
(accumulator, currentItem) => {...},
initialValue,
)
I use .filter() more often, so that argument ordering where currentItem is right next to the array is more intuitive for me
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.
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 really like taking the implementation away from the call site, so that the call site reads
const myNewValue = data.reduce(doSomethingMagic);
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.
Wow. That is the kind of monkey business that would have me running for the exits. Yikes.
I agree, but I think that’s kind of the objection. It can be tempting to write your code as little brainteasers but…
Honestly, sounds like the reviewer failed the interview, not the other way around.
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.
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.
Maybe there's just a better way to think about it and I'm still thinking about it way too much like a programmer
You "accumulate" an answer one item at a time, but there's no guarantee any dimensions are getting reduced.
You can easily duplicate the effects of map with reduce, for example, so the dims would stay the same. You could even expand dimensions, if you like, turning a 1-d array with n elements into an s X t 2-d array. If the reducing function tracks the total number of elements seen, it can easily know when to start a new row.
This is part of why people keep pointing out the name, "reduce", is a bit misleading.
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.
I don't know that's a safe assumption tbh. Try throwing them some chapter 2 exercises from any category theory textbook.
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.
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.
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.
Filter and map are easy because you can make more assertions about them without inspection:
- they take a list-like as input
- they take a function as input
- they return a list-like as output
As opposed to reduce:
- it takes a list-like as input
- it takes a function as input
The output type is not fixed, and its behavior is not fixed. If you pass the right function, reduce is filter, or map, or something else we've never seen.
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.
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...
x = initial
for y in collection:
x = f(y, x)So in effect, as some other commenter said, it's just the loop with worse syntax.
The footgun isn't `reduce` in particular, but failing to use `join`.
That is, why couldn't they have done the essentially same trick that you reference for += with reduce?
There is an optimization for lists, and maybe that's what GP is remembering. l += is functionally different from l = l +. The former mutates l, whereas the latter creates a new l. The difference matters when the line above is m = l. The mutation version will mutate m as well (they're the same reference), the creates new version will not. This optimization can just as easily turn into a footgun if the programmer is unaware of it, and in that sense is unpythonic.
> He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later.
That would explain why they're so inconvenient to chain.
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.
https://github.com/python/cpython/commit/a70b19147fd163744be...
-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
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.)
It's always worthwhile to consider what the result will be when you pass in an empty list.
It's more accurately an identity. If you are multiplying the identity is 1. While I think most people are comfortable saying the sum of no elements is 0 it's perhaps less intuitive that the product of no elements is 1. This makes me think reduce might be preferred by those with a mathematical background.
The fact that you wrote this comment with Hindley-Milner-ish notation already makes your an outlier.
Associativity also makes fold hard. It's not super trivial to know when you might need e.g. left fold vs right fold
Suppose we have foldr as in [A] -> B -> ((A, B) -> B) -> B, foldl as in [A] -> B -> ((B, A) -> B) -> B, and reduce as in [A] -> ((A, A) -> A) -> A.
Then we have foldr list value operator = reduce [\b -> operator a b | a <- list] (.), foldl list value operator = foldr (reverse list) value (flip operator), and in the case of a finite non-empty list and associative operator, we have reduce list operator = foldr (tail list) (head list) operator = foldl (init list) (last list) operator.
So these are all basically slight re-parametrizations of each other.
You will eventually learn about something called "for loop", and it will be nice.
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 sum 0 collection
acc = 0
for x in collection:
acc = acc + x
int acc = 0;
for(int x = 0; x < collection.length; ++x) {
acc += collection[x];
}
A for loop gives you better memory management and speed, but the tradeoff only makes sense to me if you're doing embedded work or something. Otherwise, eat the .000000000001% speed loss to reduce the risk of logic errors, typos, etc. and to improve developer ergonomics.
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...
.fold(init, move |acc, x| {…}) // or
.fold((state, init), |(state, acc), x| {…}).1(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.)
Does the written contract for for-loops specify this as well? Because that's the obvious alternative for a reduce that an imperative programmer would reach for: a for-loop with the programmer managing the accumulation manually.
I also don't see why a reduce should be side-effect free. There's nothing wrong with having a type def't for reduce be
base.data.List.foldLeft : (b ->{e} a ->{e} b) -> b -> [a] ->{e} b
- 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)
- 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
sum = items.reduce(0,+)
allTasks.reduce((acc, item) => { acc[item.label] = t => t.item.label === item.label; return acc; }, {} as Record<string, (t: typeof tasks[number]) => boolean>)
tasks.reduce<Record<string, (t: typeof tasks[number]) => boolean>>((acc, item) => ..., {})
Also imo it's cleaner to reduce to an object with something like this as the callback:
(acc, item) => ({ ...acc, [item.label]: t => t.label === item.label })
That means you have to await the accumulator at some point before you return it, but anything you do before that call all gets fired off immediately. Then each invidivual iteration waits for the one before it to finish before finishing itself.
It's a pretty niche pattern, but it's a good way to make your coworkers do a double take while giving you quite a bit of control over exactly how it behaves. Similar to Promise.all, but more expressive I feel.
That said, when I’m reducing a list, I still use reduce.
I think if `reduce` looked more functional or more like Erlang code, it'd be easier to read and digest.
I had similar trouble, but I know call the "accumulator" just "previous" which makes it more logical in my head:
.reduce( (previous, current) => previous+current, 0 );
In general, I find that if something is hard to describe in plain language, it's hard to code. Reducers are a bit clunky to talk about, which could make them harder to reason about, too.
some_hash = my_array.inject({}) {|accumulator, item| ... }
collection inject: aValue into: aBlock
#(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.
I also agree that a for loop is often clearer.
This is what reduce does, though? It reduces a list to a single thing. It seems like you're thinking of filter.
'for' loop is mutating.
Using 'reduce', you can do the same functionally. In some (somewhat) purely functional languages, there is no choice.
Aggregate, accumulate, combine for example.
bsnpApproved := tvShows reject: [ :eachShow | eachShow hasNaughtyContent ].
(It also has remove-if-not but that's deprecated and if you use it your code smells.)
Scheme has `filter` and `filter-not` in the SRFI-1 list library. Both of which can easily be written using a fold to bring this vaguely on topic.
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...
Bad example:
reduce(lambda x,y: x+x.extend([y+2,y*2,y**2]), [1,2,3,4], [])
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.
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.
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)
Just 3 >>= \x -> Just (x + 1)
join (fmap (\x -> Just (x + 1)) (Just 3))
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)
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.
s = s + "foo"
and
s += "foo"
Since 2005 with the release of Python 2.4:
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.
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.
arr.reduce((acc, el) => {
if (el % 2 === 0) {
acc.push(el * 2);
}
return acc;
}, []);
arr.filter(e => e % 2 === 0).map(e => e * 2)
const result = [];
for (const el of arr) {
if (el % 2 === 0) {
result.push(el * 2);
}
}
Indeed, this is why everyone knows the J programming language.
Adding numbers like this is not common in real world code. Now let's say instead of adding x, you have too look up X in a cache with an additional "type" param and update a metric of cache hits (or misses). You have to define a free function to keep your fold readable and understandable. In for loop it's much easier to understand.
ret = ""
for s in strings:
ret += s
def reduce(acc, f):
for v in self:
acc = f(acc, v)
return acc
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...