The free monoids are often being regarded as "list monoids". Yet, I am interested in other possible structures which might give us free monoids.
Firstly, let us go over the definition of free monoids. I have never quite understood how is it possible to define a free monoid as a structure which abides by monoid laws and nothing else. How do we prove that something abides by no rules but stated above? Or is this just an intuition?
Anyway, we are going to speak functors. If some monoid is free, we got it with a free functor. It is obvious that a list comes in quite handy here:
free :: Set -> Mon
free a = ([a], (++), [])
Yet, one might come up with several others. For example, here is one for Last of Data.Monoid:
freeLast :: Set -> Mon
freeLast a = (Last a, (<>) :: Last a -> Last a -> Last a, Last Nothing)
So, does this functor make Last a free monoid? More generally, if there is a law-abiding instance for Monoid (T a), is T a free monoid?
Here's one way to understand a free monoid: If somebody gives you a value, how much can you deduce about how it was created? Consider an additive monoid of natural numbers. I give you a 7 and ask you how I got it. I could have added 4+3, or 3+4, or 2+5, etc. There are many possibilities. This information was lost. If, on the other hand, I give you a list [4, 3], you know it was created from singletons [4] and [3]. Except that maybe there was a unit [] involved. Maybe it was [4]<>[3]<>[] or [4]<>[]<>[]<>[3]. But it definitely wasn't [3]<>[4].
With a longer list, [1, 2, 3], you have additional options ([1]<>[2]) <> [3], or [1] <> ([2]<>[3]), plus all possible insertions of the empty list. So the information you lose follows the unit laws and associativity, but nothing else. A free monoid value remembers how it was created, modulo unit laws and associativity.