4 ms·

There is a requirement for identity, take sorting for example, you need to be able to sort the empty set. It's a monoidal operation. The same is true for folds

by leshow 8y ago

There is a requirement for identity, take sorting for example, you need to be able to sort the empty set. It's a monoidal operation. The same is true for folds: fold(xs) = fold(xs ++ []) = fold(xs) ++ fold([]) fold(xs) = fold([] ++ xs) = fold([]) ++ fold(xs)

mlthoughts2018 8y ago
There is no monoid type requirement for fold. See the type signature in Haskell (where Monoid happens to be used for fold despite not being necessary) vs Scala (which does not require a monoid) for example. Applying fold to an empty argument has nothing to do with monoidal identities, for example you could just specify what the “seed” result should be (like with Python’s reduce function).
- leshow 8y ago
  Have a look at this blog post, it contains the bit I got that fold description from: https://philipnilsson.github.io/Badness10k/algebraic-patterns-monoid/ https://philipnilsson.github.io/Badness10k/algebraic-pattern... Back to my first post, I don't think it's not wrong to describe these operations as monoidal. Or to say that a monoidal operation implies something can be run in parallel, this whole thing feels a bit pedantic. edit: I don't know how you can say monoids for lists have nothing to do w/ empty lists considering the definition is literally: -- Identity laws x <> mempty = x mempty <> x = x Which is exactly what I posted before
  - leshow 8y ago
    should read: "It's not wrong to describe these operations as monoidal..."
- aseipp 8y ago
  `foldMap` and `fold` in Haskell only require Monoid because there are many common cases where you're folding over a monoidal type; they are simply conveniences. The alternative is to always define things in terms of `foldr` which is more "fundamental" (since its type represents a church encoding of the underlying type) which, as you note, does not require a Monoid. All that said, as another commentor noted, most of the time people actually want to talk about Monoids and not Semigroups, because identities are extremely convenient for accumulating results, and all Semigroups can be upgraded to Monoids (in Haskell this is as easy as changing type `a` to `Maybe a` for any Semigroup `a`). Arrays or counters are easy examples. You can of course use specifically designated "seed" values and argue Monoids aren't necessary but you're probably going to start adding code that does stuff like "if value == seed then ..." -- and at that point you probably are dealing with a Monoid, whether you recognize it or not. Again, the easiest example would be in Haskell, where you say "I can combine these things of type `a`. But I can't always produce a result, so instead I want `Maybe a`, and occasionally I'll produce Nothing instead, and then..." -- and that's exactly the Monoid you get by upgrading any Semigroup. So you are correct that fold has no a priori requirement for a Monoid, but in practice you probably will want monoidal composition semantics a lot of the time.
- pyrale 8y ago
  Haskell doesn't require Monoid, Semigroup or even associativity for foldl or foldr.

by leshow 8y ago

mlthoughts2018 8y ago

There is no monoid type requirement for fold. See the type signature in Haskell (where Monoid happens to be used for fold despite not being necessary) vs Scala (which does not require a monoid) for example. Applying fold to an empty argument has nothing to do with monoidal identities, for example you could just specify what the “seed” result should be (like with Python’s reduce function).

leshow 8y ago
Have a look at this blog post, it contains the bit I got that fold description from: https://philipnilsson.github.io/Badness10k/algebraic-patterns-monoid/ https://philipnilsson.github.io/Badness10k/algebraic-pattern... Back to my first post, I don't think it's not wrong to describe these operations as monoidal. Or to say that a monoidal operation implies something can be run in parallel, this whole thing feels a bit pedantic. edit: I don't know how you can say monoids for lists have nothing to do w/ empty lists considering the definition is literally: -- Identity laws x <> mempty = x mempty <> x = x Which is exactly what I posted before
- leshow 8y ago
  should read: "It's not wrong to describe these operations as monoidal..."
aseipp 8y ago
`foldMap` and `fold` in Haskell only require Monoid because there are many common cases where you're folding over a monoidal type; they are simply conveniences. The alternative is to always define things in terms of `foldr` which is more "fundamental" (since its type represents a church encoding of the underlying type) which, as you note, does not require a Monoid. All that said, as another commentor noted, most of the time people actually want to talk about Monoids and not Semigroups, because identities are extremely convenient for accumulating results, and all Semigroups can be upgraded to Monoids (in Haskell this is as easy as changing type `a` to `Maybe a` for any Semigroup `a`). Arrays or counters are easy examples. You can of course use specifically designated "seed" values and argue Monoids aren't necessary but you're probably going to start adding code that does stuff like "if value == seed then ..." -- and at that point you probably are dealing with a Monoid, whether you recognize it or not. Again, the easiest example would be in Haskell, where you say "I can combine these things of type `a`. But I can't always produce a result, so instead I want `Maybe a`, and occasionally I'll produce Nothing instead, and then..." -- and that's exactly the Monoid you get by upgrading any Semigroup. So you are correct that fold has no a priori requirement for a Monoid, but in practice you probably will want monoidal composition semantics a lot of the time.
pyrale 8y ago
Haskell doesn't require Monoid, Semigroup or even associativity for foldl or foldr.