3 ms·

> I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. There's so many cool things r

by leshow 8y ago

> I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. There's so many cool things related to programming & monoids. For example, monoids are parallelizeable. Since they are associative, you can group monoids arbitrarily, then use their monoidal operation to get your final result, think MapReduce, or a parallel fold operation. Sorting operations are monoidal (think merge sort), sums, products, so many cool things. There is a huge amount of application to computing.

mlthoughts2018 8y ago
I am probably wrong, but I think all the examples you mention only rely on associativity, and you’re essentially talking about why fold / reduce can be parallelized (literally a parallel reduction). For example, just make up some associative operation with no identity element. Imagine a string binary operator that prepends the character ‘a’ to the second operand, then concatenates them. f(‘foo’, ‘bar’) = ‘fooabar’ x `f` y `f` z = ‘{x}a{y}a{z}’ = x `f` (y `f` z) = (x `f` y) `f` z but no string e can result in e `f` x == x, so there’s no identity and so no monoid arises from this.
- 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.
    - 8y ago
- theoh 8y ago
  What you have described is a semigroup. Sometimes an application might naturally involve semigroups and sure, they share the benefits of associativity with monoids. Semigroups generalise monoids, which are one step further up on the ladder to full groups. Monoids occur more frequently in practice both because it's often practically useful and semantically meaningful to have an "empty" value (the identity) when accumulating results. So even if the application has an underlying semigroup structure, you might sometimes want to use a sum type to add an identity and make it into a monoid: "Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e • s = s = s • e for all s ∈ S." So from a programming point of view, the monoid is a handier pattern than the semigroup, and you can almost always turn a semigroup into a monoid if that would make things more convenient. There are a couple of articles here that make a weak case for the applicability of semigroups in software: https://blog.ploeh.dk/2017/11/27/semigroups/ https://blog.ploeh.dk/2017/11/27/semigroups/
platz 8y ago
associativity is the key to parallelism Four Solutions to a Trivial Problem - Guy Steele Jr. https://www.youtube.com/watch?v=ftcIcn8AmSY https://www.youtube.com/watch?v=ftcIcn8AmSY (using a monoid-cached tree)

by leshow 8y ago

mlthoughts2018 8y ago

I am probably wrong, but I think all the examples you mention only rely on associativity, and you’re essentially talking about why fold / reduce can be parallelized (literally a parallel reduction). For example, just make up some associative operation with no identity element. Imagine a string binary operator that prepends the character ‘a’ to the second operand, then concatenates them. f(‘foo’, ‘bar’) = ‘fooabar’ x `f` y `f` z = ‘{x}a{y}a{z}’ = x `f` (y `f` z) = (x `f` y) `f` z but no string e can result in e `f` x == x, so there’s no identity and so no monoid arises from this.

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.
  - 8y ago
theoh 8y ago
What you have described is a semigroup. Sometimes an application might naturally involve semigroups and sure, they share the benefits of associativity with monoids. Semigroups generalise monoids, which are one step further up on the ladder to full groups. Monoids occur more frequently in practice both because it's often practically useful and semantically meaningful to have an "empty" value (the identity) when accumulating results. So even if the application has an underlying semigroup structure, you might sometimes want to use a sum type to add an identity and make it into a monoid: "Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e • s = s = s • e for all s ∈ S." So from a programming point of view, the monoid is a handier pattern than the semigroup, and you can almost always turn a semigroup into a monoid if that would make things more convenient. There are a couple of articles here that make a weak case for the applicability of semigroups in software: https://blog.ploeh.dk/2017/11/27/semigroups/ https://blog.ploeh.dk/2017/11/27/semigroups/

platz 8y ago

associativity is the key to parallelism Four Solutions to a Trivial Problem - Guy Steele Jr. https://www.youtube.com/watch?v=ftcIcn8AmSY https://www.youtube.com/watch?v=ftcIcn8AmSY (using a monoid-cached tree)