What is the main difference between Free Monoid and Monoid?

  • A+
Category:Languages

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?

 


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.

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: