Map and Filter are nice because they let you reason locally about a single element in isolation. Reduce(Fold) forces you to reason globally about intermediate results. Reduce also forces you to conjure up a "zero" value of the relevant type, which isn't usually difficult but it does constitute some extra mental overhead.
The accumulator is global state. If you're folding from list<int> to int you're right that it's (usually) effectively a pairwise operation on ints. If the fold is something like list<foo> -> tree<bar> then you have to reason about each intermediate (tree<bar>, foo) -> tree<bar>, i.e. how global state should evolve over time with each update.
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.
"The meme" literally comes from a book that was offering it as an intuitive explanation of a long definition, assuming you know what a monoid is. All the laws and stuff boil down to "if you generalize the idea of a monoid a little bit, and if you have some functor+flatten+wrap forming a monoid, we call that a monad." If you don't know what that stuff means then obviously it's not for you, but if you do, then it's actually a concise way to give an intuition for "what (or why) it is," which is basically just that flatten is associative and wrap is neutral.
Like if someone says they know about rings and modules, you might say that an ideal is just an R-submodule of R, which grants an interesting perspective and gives a quick, memorable definition. But if they don't know about modules, you might not give them that definition.
The point is that the terminology surrounding this is impenetrable and non intuitive. Rather than acknowledge that, we get a lesson on category theory, which is missing the point.
The person I replied to said they know what monoid means, so they're familiar with algebra. The explanation is intuitive for someone familiar with undergraduate algebra (adapted to also assume some familiarity with programming and show how it connects). That's literally where the meme comes from, an intuitive remark from an introductory text on category theory. If you think it's impenetrable, it's not for you. You don't have the correct background, so ignore it.
It may have come from an old textbook, but its origin as a meme is a 2009 joke blog post that gets its humor from making fun of how obtuse and pedagogically inept that explanation is. When people reference it today, this is what they are referencing: <a href="https://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html?m=1" rel="nofollow">https://james-iry.blogspot.com/2009/05/brief-incomplete-and-...
I'm aware of the meme, but it's not obtuse or pedagogically inept.
Like if someone says they're familiar with groups and Fourier transforms, but not what it means to say wavelets are the Fourier basis for the affine group, and I break that down, and you don't know what any of those words mean, that's not me giving an obtuse explanation of wavelets; that's you wandering into the wrong conversation.
Do you want to understand monads, or do you want to understand the original quote that the joke you referenced was based on?
For the record, the original quote by Saunders Mac Lane is "a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor."
That quote is a statement in category theory. The author probably never heard of, say, Haskell - he was a pure mathematician. You can't usefully express that quote in Haskell code. You can treat it as a kind of formal description of what monads are, and Haskell generally conforms to that. But in that context, the quote itself is essentially using category theory as a metalanguage, in the same sort of way as one might write a mathematical statement that captures the semantics of some programming language expression.
That said, the quote can be handwavingly understood if you know what a monoid is, and that for monads, the identity object is the identity functor, its product is `join`[1] and its unit and multiplication satisfy the usual monoid laws.
For a concrete example, consider this Haskell expression using the `Maybe` monad:
do
x <- Just 3
return (x + 1)
That desugars to:
Just 3 >>= \x -> Just (x + 1)
Which we can desugar to an expression in terms of the monad's monoidal product, `join`, by substituting the definition of `>>=` in terms of `join`[1] to get:
join (fmap (\x -> Just (x + 1)) (Just 3))
You can evaluate that in Haskell and you'll get `Just 4`, just like the original expression.
So what happened there? The inner expression `fmap (\x -> Just (x + 1)) (Just 3)` applies the anonymous function to `Just 3` to get the double-wrapped `Just (Just 4)`. One of the `Just` wrappers is then eliminated with `join`.
(Btw, the fact that we have a Maybe within a Maybe here is related to the fact "monads are monoids in the category of endofunctors" - a category that maps to itself. That's where that part of the quote comes from.)
In this simple example, there's some unnecessary machinery - you can get the same result with `fmap (\x -> x + 1) (Just 3)`, without the extra `Just` wrapper or the `join` to eliminate it. But then you lose the ability to do things "in the monad": the anonymous function becomes just an ordinary function, it doesn't have access to the monadic wrapper. Many of the useful things that monads can do are because the wrapper is available in every function, so you can store state in it (Reader monad), create new wrapper instances with different state and pass those on (Writer and State monad), etc.
> Reduce also forces you to conjure up a "zero" value of the relevant type, which isn't usually difficult but it does constitute some extra mental overhead.
It's always worthwhile to consider what the result will be when you pass in an empty list.
If you have need of a reducing operation though, you will still need to think about that value. If you are summing up a list of numbers, it doesn't matter whether you use reduce or a loop, you need to set some initial value.
I agree, although most of the time you do end up needing to consider it with Map/Filter. It's just, it doesn't force you to. Which means either you think about it later, or it bites you in the ass because you didn't consider the empty case. Not always—and for those cases where you don't end up needing the empty case, Reduce is probably not necessary, and Map/Filter is sufficient.
> Reduce also forces you to conjure up a "zero" value of the relevant type
It's more accurately an identity. If you are multiplying the identity is 1. While I think most people are comfortable saying the sum of no elements is 0 it's perhaps less intuitive that the product of no elements is 1. This makes me think reduce might be preferred by those with a mathematical background.
snackbroken · · focus · HN ↗
mrkeen · · focus · HN ↗
snackbroken · · focus · HN ↗
[deleted] · · focus · HN ↗
[deleted]
sigbottle · · focus · HN ↗
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)
snackbroken · · focus · HN ↗
[1]Or if they have, their only encounter with it is the "a monad is just a monoid in the category of endofunctors" meme.
sigbottle · · focus · HN ↗
ndriscoll · · focus · HN ↗
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.
adastra22 · · focus · HN ↗
ndriscoll · · focus · HN ↗
Like if someone says they know about rings and modules, you might say that an ideal is just an R-submodule of R, which grants an interesting perspective and gives a quick, memorable definition. But if they don't know about modules, you might not give them that definition.
adastra22 · · focus · HN ↗
ndriscoll · · focus · HN ↗
adastra22 · · focus · HN ↗
ndriscoll · · focus · HN ↗
Like if someone says they're familiar with groups and Fourier transforms, but not what it means to say wavelets are the Fourier basis for the affine group, and I break that down, and you don't know what any of those words mean, that's not me giving an obtuse explanation of wavelets; that's you wandering into the wrong conversation.
antonvs · · focus · HN ↗
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)
txhwind · · focus · HN ↗
mcphage · · focus · HN ↗
It's always worthwhile to consider what the result will be when you pass in an empty list.
snackbroken · · focus · HN ↗
Lvl999Noob · · focus · HN ↗
mcphage · · focus · HN ↗
globular-toast · · focus · HN ↗
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.