There's no restriction at all! When I started learning the category-theoretic basis for type constructors, this very point confused me as well. We'll get to that. But first, let me clear up some confusion. These two quotes:
such a functor can only have as target category a category constructed using a type constructor
and
one may think of functors having any category as target of a functor, e.g. the category of all Haskell types
show that you are misunderstanding what a functor is (or at the very least, you are misusing terminology).
Functors do not construct categories. A functor is a mapping between categories. Functors bring objects and morphisms (types and functions) in the source category to object and morphisms in the target category.
Note that this means a functor is really a pair of mappings: a mapping on objects F_obj and mapping on morphisms F_morph. In Haskell, the object part F_obj of the functor is the name of the type constructor (e.g. List
), while the morphism part is the function fmap
(it is up to the Haskell compiler to sort out which fmap
we are referring to in any given expression). Thus, we cannot say that List
is a functor; only the combination of List
and fmap
is a functor. Still, people abuse notation; programmers call List
a functor, while category theorists use the same symbol to refer to both parts of the functor.
Furthermore, in programming, almost all functors are endofunctors, that is, the source and target category are the same - the category of all types in our language. Let's call this category Type. An endofunctor F on Type maps a type T to another type FT and a function T -> S to another function FT -> FS. This mapping must of course obey the functor laws.
Using List
as an example: we have a type constructor List : Type -> Type
, and a function fmap: (a -> b) -> (List a -> List b)
, that together form a functor. T
There is one final point to clear up. Writing List int
does not create a new type of lists of integers. This type already existed. It was an object in our category Type. List Int
is simply a way to refer to it.
Now, you're wondering why a functor can't map a type to, say, Int
or String
. But, it can! One just has to use the identity functor. For any category C, the identity functor maps every object to itself and morphism to itself. It is straightforward to verify this mapping satisfies the functor laws. In Haskell, this would be a type constructor id : * -> *
that maps every type to itself. For example, id int
evaluates to int
.
Moreover, one can even create constant functors, that map all types to a single type. For example, the functor ToInt : * -> *
, where ToInt a = int
for all types a
, and maps all morphisms to the integer identity function: fmap f = \x -> x
f
right? And in your scenario,f
should be just like a normal Haskell function and map types to types. In Haskell, the only things that are allowed to have the kind* -> *
are type constructors. Type families are more general, but they must always be fully applied