6 ms·

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 r

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.

mrkeen 11d ago
It's pairwise, not global reasoning.
- snackbroken 11d ago
  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.
  - deleted 10d ago
    [deleted]
sigbottle 11d ago
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)
- snackbroken 11d ago
  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.
  - sigbottle 10d ago
    I do know what a monoid is, but a monad in the category of endofunctors is the scary word for me :sob:
    - ndriscoll 10d ago
      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.
      - adastra22 10d ago
        You have become the meme.
        ndriscoll 10d ago
        "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.
        9d ago
- txhwind 10d ago
  If the contraint is not in the signature, and cannot trigger a test failure with typical implementation, it doesn't exist.
mcphage 11d ago
> 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.
- snackbroken 11d ago
  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.
  - Lvl999Noob 10d ago
    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.
  - mcphage 10d ago
    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.
globular-toast 10d ago
> 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.

mrkeen 11d ago

It's pairwise, not global reasoning.

snackbroken 11d ago
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.
- deleted 10d ago
  [deleted]

sigbottle 11d ago

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)

snackbroken 11d ago
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.
- sigbottle 10d ago
  I do know what a monoid is, but a monad in the category of endofunctors is the scary word for me :sob:
  - ndriscoll 10d ago
    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.
    - adastra22 10d ago
      You have become the meme.
      - ndriscoll 10d ago
        "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.
        9d ago
txhwind 10d ago
If the contraint is not in the signature, and cannot trigger a test failure with typical implementation, it doesn't exist.

mcphage 11d ago

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

snackbroken 11d ago
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.
- Lvl999Noob 10d ago
  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.
- mcphage 10d ago
  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.

globular-toast 10d ago

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