13 ms·

Algebraic patterns – Semigroup

82 points by lebek 10y ago

kccqzy 10y ago
Might be slightly off topic but in the recently released Glasgow Haskell Compiler, semigroups are now built into the base library. No more dependencies when using it.
- Bromskloss 10y ago
  How does that work in Haskell? Is the user of a semigroup somehow guaranteed that its operation is associative?
  - wereHamster 10y ago
    The person who implements Semigroup for a data type must ensure that the laws hold.
    - deleted 10y ago
      [deleted]
    - haimez 10y ago
      Which is where property based testing really shines. Still requires the implementer to be a good citizen and write those tests though.
      - kristianp 10y ago
        AKA QuickCheck. https://en.wikipedia.org/wiki/QuickCheck https://en.wikipedia.org/wiki/QuickCheck
  - tikhonj 10y ago
    No. Guaranteeing typeclass laws like associativity is hard. People have looked into various ways to do that, but haven't found anything completely satisfying. It's either hard for the programmer (dependent typing) or hard to implement (automatic theorem proving). I hope that'll change, but for now Haskell does not have any facilities for specifying or enforcing typeclass laws. As it is, it works more or less exactly like interfaces from other languages. When you implement Comparable in Java you implicitly expect certain laws (ie that it's a valid ordering), but there is also no way to specify or verify them.
    - Bromskloss 10y ago
      Clueless suggestion: What about the programmer (who implements the semigroup) also providing a proof (that can be automatically checked) that it satisfies associativity? Is that method perhaps already covered by one of the examples you mentioned?
      - reuben364 10y ago
        That is the dependent typed aspect mentioned. This is actually done in Idris with VerifiedSemigroup and other verified instances.
        Bromskloss 10y ago
        OK. I'm afraid I don't know enough to make the connection. Actually, I never understood the point of dependent types. They seem to do away with the neat order that types introduce. ¯\_(ツ)_/¯
vikiomega9 10y ago
I really wish the applications section had more detail or perhaps an "editorial". I don't really follow the consequence of a frequency map being associative.
- noelwelsh 10y ago
  Yeah, the application section is pretty poor. The number one large-scale practical application of semigroups (and, more often, their extension the monoid) is in parallel and concurrent systems. Associativity says that order of operations doesn't matter, which in turn implies you can distribute computations however you like across multiple machines and still get the correct result. This is the big idea leveraged in systems like Summingbird and other big data frameworks (e.g. https://arxiv.org/abs/1304.7544 https://arxiv.org/abs/1304.7544) and in CRDTs.
  - vit_tucek 10y ago
    Associativity says that the order of __evaluation__ of operations doesn't matter. You are talking about commutativity.
    - noelwelsh 10y ago
      I meant associativity, but was not precise in my description. Commutativity is also useful.
  - deepnet 10y ago
    And yet the article concludes : "The form of parallelism induced by the associativity of the semigroup operation is heavily relied upon in the Map-Reduce programming model. We’ll expound on this in more detail in a later article, as this is more easily developed algebraically after defining the concept of a Monoid."
    - noelwelsh 10y ago
      Right. So my HN comment has more information on this than the entire blog post, which is kinda the point.
chubot 10y ago
I think of these programming constructs as Monoids rather than semigroups. A monoid is just a semigroup with an identity element: http://mathworld.wolfram.com/Monoid.html http://mathworld.wolfram.com/Monoid.html Most of his examples have an identity, giving a monoid. * (string, concat): identity '' * numbers with addition/multiplication: identity 0/1 * numbers with min/max: Numbers in computers are finite, so this is quite useful. stdint.h defines INT32_MAX, INT32_MIN, etc. * booleans with && / || : true / false * function composition: identity function f(x) = x * frequency map: {} or {A: 0, B:0, ...} depending on how you define it Comparators: Is this a bug in the post? It doesn't seem to follow the pattern because the arity of the functions is different. In a semigroup or monoid all the elements are supposed to be drawn from the same set. Other examples I can think of: * Python's dict with respect to member .update() (if you think of it as an operator rather than mutating member). Identity is {} * Unix Pipes: identity 'cat' (note that the shell supports point-free programming)
- cottonseed 10y ago
  As you say, most semigroups are just monoids where you forget the identity. Here's an MO thread on examples of monoids that aren't trivial restrictions: http://math.stackexchange.com/questions/460/are-there-any-interesting-semigroups-that-arent-monoids http://math.stackexchange.com/questions/460/are-there-any-in...
  - moomin 10y ago
    Even with these examples, the absence of an identity can be useful. e.g. Non-empty lists form a semigroup.
    - JadeNB 10y ago
      > e.g. Non-empty lists form a semigroup. If I take everyone's meanings correctly, what you describe (a monoid with the identity removed) is different from what cottonseed (https://news.ycombinator.com/item?id=12110936 https://news.ycombinator.com/item?id=12110936) describes, which is a monoid with the identity forgotten. That is, it's still there, but we don't require it to be there axiomatically. Note that every monoid is a semigroup (because it satisfies a stronger collection of axioms), but not every monoid with identity removed is a semigroup (because it's possible to combine two non-identity elements to get the identity element): consider, for example, the integers without 0.
skybrian 10y ago
I'm not sure how useful this is in practice. For example, addition in actual computer languages isn't necessarily associative and compilers often can't treat them as associative. Floating point numbers added in the wrong order can result in catastrophic cancellation. So for example, as far as JavaScript is concerned, numbers aren't associative. Integers may overflow. Twos-complement addition is associative, but only because if you get the same bogus answer in the case of overflow. If you actually detect overflow, you may get overflow or not depending on the order in which you add the numbers. Oftentimes we ignore these issues, but it seems like if you're talking about taking advantage of associative rules to reorder calculations, you have to think about it. Thinking in terms of semigroups instead of concrete datatypes seems like a likely source of bugs when your model makes assumptions that aren't actually true.
- noelwelsh 10y ago
  At a certain level you are correct. A compiler certainly should not be reordering FP calculations, for instance. However, at the level these abstractions are typically used they are absolutely fine. For example, if you want to add up the number of hits your web site has received you will be absolutely fine to use a 64-bit integer and treat addition as associative. There is no possibility of overflow. Similarly, if you train a machine learning model using gradient descent you can compute your gradients in parallel and then sum them, taking advantage of associativity, and this will work out fine. (See Hogwild! for some proofs that #YOLO is an acceptable strategy for SGD https://people.eecs.berkeley.edu/~brecht/papers/hogwildTR.pdf https://people.eecs.berkeley.edu/~brecht/papers/hogwildTR.pd...) So, basically, semigroups and other abstractions are a-ok where they are typically used.
- GFK_of_xmaspast 10y ago
  Is unsigned arithmetic non-associative?
  - groovy2shoes 10y ago
    Integer addition is associative, even for fixed-bitwidth integers (which constitute "the integers modulo 2^n" for some bitwidth n; e.g. 8-bit bytes under addition form the group of integers modulo 2^8 (i.e., integers modulo 256)). Note that both the full integers as well as the integers modulo n are groups under addition. As groups are more restrictive than semigroups, all groups are also semigroups (groups are semigroups that also have an identity element and where every element is invertible). Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse. So, it's usually said that "the non-zero integers" form a group.
dkarapetyan 10y ago
Incidentally the typical mathematical curriculum does not even bother with monoids and semigroups when it comes to the initial introduction. The introductory material jumps right into the definition of a group and then mentions on the side that removing a few key pieces leaves you with a monoid and a semigroup. Same with fields, rings, rigs, etc. The most constrained piece is introduced first and then dropping requirements leaves you with something less constrained for which you can prove fewer theorems. I learned groups and fields first and then learned about the more relaxed versions. I'm not sure which approach is better though. Groups are certainly more fun to play with but monoids probably show up in more contexts.

82 points by lebek 10y ago

Might be slightly off topic but in the recently released Glasgow Haskell Compiler, semigroups are now built into the base library. No more dependencies when using it.

Bromskloss 10y ago
How does that work in Haskell? Is the user of a semigroup somehow guaranteed that its operation is associative?
- wereHamster 10y ago
  The person who implements Semigroup for a data type must ensure that the laws hold.
  - deleted 10y ago
    [deleted]
  - haimez 10y ago
    Which is where property based testing really shines. Still requires the implementer to be a good citizen and write those tests though.
    - kristianp 10y ago
      AKA QuickCheck. https://en.wikipedia.org/wiki/QuickCheck https://en.wikipedia.org/wiki/QuickCheck
- tikhonj 10y ago
  No. Guaranteeing typeclass laws like associativity is hard. People have looked into various ways to do that, but haven't found anything completely satisfying. It's either hard for the programmer (dependent typing) or hard to implement (automatic theorem proving). I hope that'll change, but for now Haskell does not have any facilities for specifying or enforcing typeclass laws. As it is, it works more or less exactly like interfaces from other languages. When you implement Comparable in Java you implicitly expect certain laws (ie that it's a valid ordering), but there is also no way to specify or verify them.
  - Bromskloss 10y ago
    Clueless suggestion: What about the programmer (who implements the semigroup) also providing a proof (that can be automatically checked) that it satisfies associativity? Is that method perhaps already covered by one of the examples you mentioned?
    - reuben364 10y ago
      That is the dependent typed aspect mentioned. This is actually done in Idris with VerifiedSemigroup and other verified instances.
      - Bromskloss 10y ago
        OK. I'm afraid I don't know enough to make the connection. Actually, I never understood the point of dependent types. They seem to do away with the neat order that types introduce. ¯\_(ツ)_/¯

vikiomega9 10y ago

I really wish the applications section had more detail or perhaps an "editorial". I don't really follow the consequence of a frequency map being associative.

noelwelsh 10y ago
Yeah, the application section is pretty poor. The number one large-scale practical application of semigroups (and, more often, their extension the monoid) is in parallel and concurrent systems. Associativity says that order of operations doesn't matter, which in turn implies you can distribute computations however you like across multiple machines and still get the correct result. This is the big idea leveraged in systems like Summingbird and other big data frameworks (e.g. https://arxiv.org/abs/1304.7544 https://arxiv.org/abs/1304.7544) and in CRDTs.
- vit_tucek 10y ago
  Associativity says that the order of __evaluation__ of operations doesn't matter. You are talking about commutativity.
  - noelwelsh 10y ago
    I meant associativity, but was not precise in my description. Commutativity is also useful.
- deepnet 10y ago
  And yet the article concludes : "The form of parallelism induced by the associativity of the semigroup operation is heavily relied upon in the Map-Reduce programming model. We’ll expound on this in more detail in a later article, as this is more easily developed algebraically after defining the concept of a Monoid."
  - noelwelsh 10y ago
    Right. So my HN comment has more information on this than the entire blog post, which is kinda the point.

chubot 10y ago

I think of these programming constructs as Monoids rather than semigroups. A monoid is just a semigroup with an identity element: http://mathworld.wolfram.com/Monoid.html http://mathworld.wolfram.com/Monoid.html Most of his examples have an identity, giving a monoid. * (string, concat): identity '' * numbers with addition/multiplication: identity 0/1 * numbers with min/max: Numbers in computers are finite, so this is quite useful. stdint.h defines INT32_MAX, INT32_MIN, etc. * booleans with && / || : true / false * function composition: identity function f(x) = x * frequency map: {} or {A: 0, B:0, ...} depending on how you define it Comparators: Is this a bug in the post? It doesn't seem to follow the pattern because the arity of the functions is different. In a semigroup or monoid all the elements are supposed to be drawn from the same set. Other examples I can think of: * Python's dict with respect to member .update() (if you think of it as an operator rather than mutating member). Identity is {} * Unix Pipes: identity 'cat' (note that the shell supports point-free programming)

cottonseed 10y ago
As you say, most semigroups are just monoids where you forget the identity. Here's an MO thread on examples of monoids that aren't trivial restrictions: http://math.stackexchange.com/questions/460/are-there-any-interesting-semigroups-that-arent-monoids http://math.stackexchange.com/questions/460/are-there-any-in...
- moomin 10y ago
  Even with these examples, the absence of an identity can be useful. e.g. Non-empty lists form a semigroup.
  - JadeNB 10y ago
    > e.g. Non-empty lists form a semigroup. If I take everyone's meanings correctly, what you describe (a monoid with the identity removed) is different from what cottonseed (https://news.ycombinator.com/item?id=12110936 https://news.ycombinator.com/item?id=12110936) describes, which is a monoid with the identity forgotten. That is, it's still there, but we don't require it to be there axiomatically. Note that every monoid is a semigroup (because it satisfies a stronger collection of axioms), but not every monoid with identity removed is a semigroup (because it's possible to combine two non-identity elements to get the identity element): consider, for example, the integers without 0.

skybrian 10y ago

I'm not sure how useful this is in practice. For example, addition in actual computer languages isn't necessarily associative and compilers often can't treat them as associative. Floating point numbers added in the wrong order can result in catastrophic cancellation. So for example, as far as JavaScript is concerned, numbers aren't associative. Integers may overflow. Twos-complement addition is associative, but only because if you get the same bogus answer in the case of overflow. If you actually detect overflow, you may get overflow or not depending on the order in which you add the numbers. Oftentimes we ignore these issues, but it seems like if you're talking about taking advantage of associative rules to reorder calculations, you have to think about it. Thinking in terms of semigroups instead of concrete datatypes seems like a likely source of bugs when your model makes assumptions that aren't actually true.

noelwelsh 10y ago
At a certain level you are correct. A compiler certainly should not be reordering FP calculations, for instance. However, at the level these abstractions are typically used they are absolutely fine. For example, if you want to add up the number of hits your web site has received you will be absolutely fine to use a 64-bit integer and treat addition as associative. There is no possibility of overflow. Similarly, if you train a machine learning model using gradient descent you can compute your gradients in parallel and then sum them, taking advantage of associativity, and this will work out fine. (See Hogwild! for some proofs that #YOLO is an acceptable strategy for SGD https://people.eecs.berkeley.edu/~brecht/papers/hogwildTR.pdf https://people.eecs.berkeley.edu/~brecht/papers/hogwildTR.pd...) So, basically, semigroups and other abstractions are a-ok where they are typically used.
GFK_of_xmaspast 10y ago
Is unsigned arithmetic non-associative?
- groovy2shoes 10y ago
  Integer addition is associative, even for fixed-bitwidth integers (which constitute "the integers modulo 2^n" for some bitwidth n; e.g. 8-bit bytes under addition form the group of integers modulo 2^8 (i.e., integers modulo 256)). Note that both the full integers as well as the integers modulo n are groups under addition. As groups are more restrictive than semigroups, all groups are also semigroups (groups are semigroups that also have an identity element and where every element is invertible). Integer multiplication also forms a semigroup (and in fact a monoid, due to identity), but not a full group due to zero not having an inverse. So, it's usually said that "the non-zero integers" form a group.

dkarapetyan 10y ago

Incidentally the typical mathematical curriculum does not even bother with monoids and semigroups when it comes to the initial introduction. The introductory material jumps right into the definition of a group and then mentions on the side that removing a few key pieces leaves you with a monoid and a semigroup. Same with fields, rings, rigs, etc. The most constrained piece is introduced first and then dropping requirements leaves you with something less constrained for which you can prove fewer theorems. I learned groups and fields first and then learned about the more relaxed versions. I'm not sure which approach is better though. Groups are certainly more fun to play with but monoids probably show up in more contexts.