4 ms·

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

by 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.
OscarCunningham 10y ago
For the comparators I think that what he means is that for any given set X the set of comparators on X forms a semigroup where the composition is "compare using the first comparator and then the second". Of course this too is a monoid with the identity being the comparator that says all things are equal.
alipang 10y ago
Comparators are not composed by ordinary function composition, but by pointwise composition in the domain. If you can read Haskell instance Monoid a => Monoid (b -> a) where f <> g = \x -> f x <> g x Here they type a is the set `{ EQ, LESS, GREATER }` which is in turn composed in a left-biased way with `EQ` as an identity. If you have two comparators, `lastNameComparator` and `firstNameComparator` and compose them into a comparator that compares first by firstName, then by lastName, surely that is a closed operation. It is also associative, and comparators do have an identity, so, yes they are also monoids.

by chubot 10y ago

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.

OscarCunningham 10y ago

For the comparators I think that what he means is that for any given set X the set of comparators on X forms a semigroup where the composition is "compare using the first comparator and then the second". Of course this too is a monoid with the identity being the comparator that says all things are equal.

alipang 10y ago

Comparators are not composed by ordinary function composition, but by pointwise composition in the domain. If you can read Haskell instance Monoid a => Monoid (b -> a) where f <> g = \x -> f x <> g x Here they type a is the set `{ EQ, LESS, GREATER }` which is in turn composed in a left-biased way with `EQ` as an identity. If you have two comparators, `lastNameComparator` and `firstNameComparator` and compose them into a comparator that compares first by firstName, then by lastName, surely that is a closed operation. It is also associative, and comparators do have an identity, so, yes they are also monoids.