Functors and free objects in Hask

Question

Based on Wikipedia's definition of a free object, it seems to me that every Functor is Free in Hask. Conversely, every free object should also be a Functor. Is this correct, or am I misunderstanding?

Answer 1

I'm not sure what you mean. Often times categorical definitions are written in greater generality than one wants in a functional programing contexts. Rather than using the wikipedia definition using concrete categories, consider the definition you get where you treat the kind of thing you want free as a parameter.

Definition: free foo. A free foo on type T is an object FT such that F is a foo, and a function i :: T -> FT such that any other foo S and a function f :: T -> S there exists a unique foo morphism f' such that f' . i = f.

Insert say "monoid" and you get free monoids, groups and you get free groups, etc. Note, this definition uses essentially no category theory and most certainly does not talk about functors. It is less formal than the definition given by wikipedia, but should work intuitively. Given this definition, a free construction is a general way of making free objects. For example [] provides a free construction for monoids, in that [a] is the free monoid on a for all a.

I don't think it is the case that all functors are free functors. I also don't think it is the case that all free constructions in Hask are Haskell functors (that all free constructions lead to abstract functors is trivial).

My definition of "free" applied only to things of kind *, but a more general definition would also apply to other kinds. For example, free monads.

You could go all out and do crazy things. For example, you could probably define the free boolean algebra on Sing k (the singleton types of kind k) where k is enumerable using GADTs. That this involves something "functorial" will be highly non-obvious in Hask.