[Haskell-cafe] Re: What are "free" Monads?

[Heinrich Apfelmus]

Günther Schmidt wrote:
> Daniel Peebles wrote:
>> Given any functor you can get a monad for free!
>>
>> data Free f a = Either a (f (Free f a))
>
> that looks lovely, but it doesn't help me much :)

Alas, that you get one "for free" is not the reason why it's called the
free monad. Rather, for algebraic structures like groups or rings,
"freeness" refers to the fact that there are no other relations than the
imposed ones.


The simplest example are probably the natural numbers. As you may know,
there are two fundamental operations

   0 :: Nat           -- nullary "operation"
   s :: Nat -> Nat    -- successor function, unary

and the natural numbers are exactly the  free  algebra over these
operations, which intends to rule out any "superfluous" relations like

   s (s (s (s 0))) = s 0

or similar.

This is a distinguishing property, for there are other sets that support
these two operations, for instance the "clock numbers" where you have

   12 = s (s (s ... (s 0)..))       = 0
        ^^^ 12 times the successor

which corresponds to the time on a clock. In Haskell:

   newtype Clock = Clock Int

   0 = Clock 0
   s = \(Clock k) -> Clock $ (k+1) `mod` 12


Another example that is not free either:

   newtype Foo13 = Foo13 Int

   0 = Foo13 0
   s = \(Foo13 k) -> Foo13 $ if k == 13 then 13 else k+1


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com