haskellmonoids

A monoid can see its elements all in the same shape

I'm not looking for the mathematical definition of a monoid, I'm looking for why monoid are important in haskell. (I'm not talking about Monoid class, just I'm talking about monoid structure)

Is it correct to describe the following as one of the characteristics of a monoid? "A monoid can see its elements all in the same shape" For example, the monoid of natural numbers,+, including 0, allows all its members to be viewed in the shape _ + _. I'm assuming that associativity law is used to modularize expressions that can be viewed as such.

Solution

  • If you're asking whether an element x of a monoid M can always be written in the form _ + _, then this is trivially true because x ≡ x <> mempty holds always, it's right there in the monoid laws. But that's not very enlightening.

    I suppose what you meant was, every element n ∈ ℕ can be written in the form

         ... + 1 + 1 + 1 + ...

    Even that isn't completely true, because what about 0? But of course we do also have 0, it's literally just mempty.

    Monoids with such a property are the free monoids. In Haskell, free monoids are usually identified with lists, which may be surprising because I just said the natural numbers are a free monoid. The key is, this sort of thing generally holds up to isomorphism. The natural numbers are isomorphic to the Haskell type [()], e.g. 4 is represented by [(),(),(),()]. For lists of other types the freeness is witnessed by e.g.

       "Hello, World" ≡ "H"<>"e"<>"l"<>"l"<>"o"<>","<>" "<>"W"<>"o"<>"r"<>"l"<>"d"

    Specifically, for a free monoid this decomposition is unambiguous.

    But are all monoids free? No. For a counterexample, you need to go no further than the integers with addition. Naïvely one might think that this is a free monoid with the generators 1 and -1, but it's not – for example, the number 2 could be written both as 1 + 1 and as 1 + (-1) + 1 + 1, etc..
    (The integers are however a free group.)

    In practice, for many monoids, even when they could be considered as free monoids, this is not necessarily a useful perspective. For lists, it's clear that we're talking free over the set specified by the type of list, but in other cases it's not. For example, Maybe (Char, String) is isomorphic to String and thus also a free monoid, but when using that type you would probably want to express something different.