Comment by chubot | Hacker News Reader

Comment by chubot | Hacker News Reader

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

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)

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

Even with these examples, the absence of an identity can be useful. e.g. Non-empty lists form a semigroup.

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

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.

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.

Reply on news.ycombinator.com