What is the main difference between Free Monoid and Monoid?

Question

Looks like I have a pretty clear understanding what a Monoid is in Haskell, but last time I heard about something called a free monoid.

What is a free monoid and how does it relate to a monoid?

Can you provide an example in Haskell?

Cromagnon

is this a math question? Maybe it's more suitable for math.stackexchange.com – Banian

@Coderino Javarino I prefer to have an answer with a programming point of view. I think I don't have enough competence to understand math guys response. In case I won't find a response, I'll definitely try there. Thanks! – Cromagnon

en.wikipedia.org/wiki/Free_monoid – Palma

I'm voting to close this question as off-topic because it belongs on a Math site. (If the "maths guys" answers are too hard to understand, use math.stackexchange.com rather than mathoverflow.net/.) – Palma

The programming point of view is that this is not a programming question :-) (Category theory is for theoretical computer scientists.) – Palma

The fact that monoids originated in mathematics does not take away from their relevance as a very common interface in certain functional programming languages. Many functional programmers don't have a background in mathematics, so that framing their questions as programming questions on SO will lead to answers much more suitable to them than a math-centered forum, whether professional or casual. – Oregano

Answer 1

In a programming context, I usually translate free monoid to [a]. In his excellent series of articles about category theory for programmers, Bartosz Milewski describes free monoids in Haskell as the list monoid (assuming one ignores some problems with infinite lists).

The identity element is the empty list, and the binary operation is list concatenation:

Prelude Data.Monoid> mempty :: [Int]
[]
Prelude Data.Monoid> [1..3] <> [7..10]
[1,2,3,7,8,9,10]

Intuitively, I think of this monoid to be 'free' because it a monoid that you can always apply, regardless of the type of value you want to work with (just like the free monad is a monad you can always create from any functor).

Additionally, when more than one monoid exists for a type, the free monoid defers the decision on which specific monoid to use. For example, for integers, infinitely many monoids exist, but the most common are addition and multiplication.

If you have two (or more integers), and you know that you may want to aggregate them, but you haven't yet decided which type of aggregation you want to apply, you can instead 'aggregate' them using the free monoid - practically, this means putting them in a list:

Prelude Data.Monoid> [3,7]
[3,7]

If you later decide that you want to add them together, then that's possible:

Prelude Data.Monoid> getSum $ mconcat $ Sum <$> [3,7]
10

If, instead, you wish to multiply them, you can do that as well:

Prelude Data.Monoid> getProduct $ mconcat $ Product <$> [3,7]
21

In these two examples, I've deliberately chosen to elevate each number to a type (Sum, Product) that embodies a more specific monoid, and then use mconcat to perform the aggregation.

For addition and multiplication, there are more succinct ways to do this, but I did it that way to illustrate how you can use a more specific monoid to interpret the free monoid.

Hilliary

In Haskell, a language that embraces infinity, I don't think [] is free enough. For example, mconcat (repeat (Last Nothing)) <> Last (Just 42) gives an observable value, but mconcat (Last <$> (repeat Nothing <> [Just 42])) does not. – Vituline

@Vituline You are correct. It's better to go with something like data FreeMonoid a = FreeMonoid { runFreeMonoid :: forall b. Monoid b => (a -> b) -> b }. Details in this post. – Barefoot

Answer 2

As you already know, a monoid is a set with an element e and an operation <> satisfying

e <> x = x <> e = x  (identity)
(x<>y)<>z = x<>(y<>z)  (associativity)

Now, a free monoid, intuitively, is a monoid which satisfies only those equations above, and, obviously, all their consequences.

For instance, the Haskell list monoid ([a], [], (++)) is free.

By contrast, the Haskell sum monoid (Sum Int, Sum 0, \(Sum x) (Sum y) -> Sum (x+y)) is not free, since it also satisfies additional equations. For instance, it's commutative

x<>y = y<>x

and this does not follow from the first two equations.

Note that it can be proved, in maths, that all the free monoids are isomorphic to the list monoid [a]. So, "free monoid" in programming is only a fancy term for any data structure which 1) can be converted to a list, and back, with no loss of information, and 2) vice versa, a list can be converted to it, and back, with no loss of information.

In Haskell, you can mentally substitute "free monoid" with "list-like type".

Anandrous

Good answer. Worth noting that (as discussed on other answers), in Haskell [a] is actually not quite a free monoid – Uphroe

Answer 3

A monoid (M,•,1) is a mathematical structure such that:

1. M is a set
2. 1 is a member of M
3. • : M * M -> M
4. a•1 = a = 1•a
5. Given elements a, b and c in M, we have a•(b•c) = (a•b)•c.

A free monoid on a set M is a monoid (M',•,0) and function e : M -> M' such that, for any monoid (N,*,1), given a (set) map f : M -> N we can extend this to a monoid morphism f' : (M',•,0) -> (N,*,1), i.e

f a = f' (e a)
f' 0 = 1
f' (a•b) = (f' a) • (f' b)

In other words, it is a monoid that does nothing special.

An example monoid is the integers with the operation being addition and the identity being 0. Another monoid is sequences of integers with the operation being concatenation and the identity being the empty sequence. Now the integers under addition is not a free monoid on the integers. Consider the map into sequences of integers taking n to (n). Then for this to be free we would need to extend this to a map taking n + m to (n,m), i.e. it must take 0 to (0) and to (0,0) and to (0,0,0) and so on.

On the other hand if we try to look at sequences of integers as a free monoid on the integers, we see that it seems to work in this case. The extension of the map into the integers with addition is one that takes the sum of a sequence (with the sum of () being 0).

So what is the free monoid on a set S? Well one thing we could try is just arbitrary binary trees of S. In a Haskell type this would look like:

data T a = Unit | Single a | Conc (T a) (T a)

And it would have an identity of Unit, e = Single and (•) = Conc.

And we can write a function to show how it is free:

-- here the second argument represents a monoid structure on b
free :: (a -> b) -> (b -> b -> b, b) -> T a -> b
free f ((*),zero) = f' where
  f' (Single a) = f a
  f' Unit = zero
  f' (Conc a b) = f' a * f' b

It should be quite obvious that this satisfies the required laws for a free monoid on a. Except for one: T a is not a monoid because it does not quite satisfy laws 4 or 5.

So now we should ask if we can make this into a simpler free monoid, ie one that is an actual monoid. The answer is yes. One way is to observe that Conc Unit a and Conc a Unit and Single a should be the same. So let’s make the first two types unrepresentable:

data TInner a = Single a | Conc (TInner a) (TInner a)
data T a = Unit | Inner (TInner a)

A second observation we can make is that there should be no difference between Conc (Conc a b) c and Conc a (Conc b c). This is due to law 5 above. We can then flatten our tree:

data TInner a = Single a | Conc (a,TInner a)
data T a = Unit | Inner (TInner a)

The strange construction with Conc forces us to only have a single way to represent Single a and Unit. But we see we can merge these all together: change the definition of Conc to Conc [a] and then we can change Single x to Conc [x], and Unit to Conc [] so we have:

data T a = Conc [a]

Or we can just write:

type T a = [a]

And the operations are:

unit = []
e a = [a]
(•) = append

free f ((*),zero) = f' where
  f' [] = zero
  f' (x:xs) = f x * f' xs

So in Haskell, the list type is called the free monoid.

Delivery

Answer 4

A free monoid is a specific type of monoid. Specifically, it’s the monoid you get by taking some fixed set of elements as characters and then forming all possible strings from those elements. Those strings, with the underlying operation being string concatenation, form a monoid, and that monoid is called the free monoid.

Breakout