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