On Saturday 27 February 2010 3:54:25 am Günther Schmidt wrote:
I see the term "free monad" quite a lot, but don't really see an explanation what a free monad is. What sets a monad free and why in this day and age are there unfree monads?
Free structures originate (I think) in algebra. There you'll find talk of free groups, free rings, free monoids, etc. The plain English explanation is that you want to take some 'underlying' structure, and promote it into the structure in question, but to do so in the simplest way possible in a sense. In the algebra case, the underlying structure is typically a set, so you'll have the free monoid over a set, the free group over a set, etc. Monoids are pretty simple, so they're probably easiest to explain. So, monoids are: A set M A binary operation m : M x M -> M An identity element e : M and follow the laws: a `m` (b `m` c) = (a `m` b) `m` c e `m` a = a = a `m` e So, for a free monoid over a set S, we want to produce a structure satisfying the above, with an additional constraint that we need to have an: i : S -> M to inject elements of S into the monoid. And by "simplest" above, we mean something like: 1) All the elements of M should be required to exist either by i, or by the operations for the structure. 2) The only equational laws that should hold for the structure should be those that are required to hold for structures of that type. These may be kind of vague, and I apologize. They can be made more precise in category theory (at least). So, for the above rules, we get that the free monoid over a set is the monoid of lists of elements of that set with concatenation and nil. M = [S] e = [] m = (++) i = \x -> [x] -- \x -> x : [] [] ++ xs = xs = xs ++ [] xs ++ (ys ++ zs) = (xs ++ ys) ++ zs In category theory, this is usually presented in terms of adjoint functors. What you do is specify a "forgetful" or "underlying" functor, from, say, the category of monoids to the category of sets. Then, a left adjoint to that functor is called (I believe) the free monoid functor, and it takes sets to the free monoid thereover. I don't really have the wherewithal to give an explanation of adjoint functors, but adjunctions are what capture the two rules for "free" things above. So, now we want free monads over a (endo)functor F. As it turns out, monads are monoid objects in the category of endofunctors over a category, which is a generalization of the above monoids to categories other than sets. So, we can hopefully use the above intuitive idea of a free monoid to figure out what might be going on with free monads. So, first we have an endofunctor F which is going to be analogous to the underlying set. And we'll need some type of injection i : F -> M M being the functor part of the free monad over F. But arrows in the category in question are natural transformations, so in Haskell, this would be more like: i :: forall a. F a -> M a Monads are also required to have a couple operations: return :: forall a. a -> M a join :: forall a. M (M a) -> M a And they should satisfy some monad laws. I can't explain to you how to figure out what M, return and join should be, because I don't know how myself; I'm kind of winging it at this point. But Daniel Peebles has given the right answer. It's datatype: data M a = Return a | Roll (F (M a)) with: return = Return join (Return m) = m join (Roll fmm) = Roll (fmap join fmm) i f = Roll (fmap Return f) -- this should look vaguely similar to to \x -> x : [] which, you might notice, is similar in character to the free monoid above. In the free monoid, you can inject elements of the set, and you can multiply together lists to get arbitrarily long strings of elements of the underlying set. In the free monad, there's a way to 'inject' the functor into the monad, and you can 'multiply' in the monad to get arbitrarily deep composition 'strings' of F (by repeatedly Rolling). There are also cofree structures, as was mentioned. The difference is that while free functors are left adjoints to underlying functors, cofree functors are right adjoints. I don't have much to say beyond that, though. Anyhow, hope that gave some insight. -- Dan