upvote
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)

reply
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.

reply
I do know what a monoid is, but a monad in the category of endofunctors is the scary word for me :sob:
reply
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.

reply
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.

---

[1] x >>= f = join (fmap f x)

reply
If the contraint is not in the signature, and cannot trigger a test failure with typical implementation, it doesn't exist.
reply
It's pairwise, not global reasoning.
reply
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.
reply
deleted
reply
> 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.

reply
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.
reply
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.
reply
> 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.

reply