[Haskell-cafe] Re: What are "free" Monads?
Heinrich Apfelmus
apfelmus at quantentunnel.de
Sat Feb 27 05:25:04 EST 2010
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
More information about the Haskell-Cafe
mailing list