23

For as far as I understand, a functor is a mapping between two categories, for example from objects in C to objects in D where C and D are categories.

In Haskell there is Hask in which the objects are Haskell types and the morphisms are Haskell functions. However, the Functor type class has a function fmap which maps between these types (which are thus objects and not categories themselves):

fmap :: (a -> b) -> f a -> f b

f a and f b are both objects in Hask. Does this mean every instance of Functor in Haskell is an endofunctor, and if not does Functor really represent a functor?

What am I missing here? Are types also categories in Haskell?

Community
  • 1
  • 1

3 Answers3

27

An instance of Functor specifies two things: a type constructor F of kind * -> *, that is, a mapping from objects of Hask to objects of Hask, and a function of type (a -> b) -> (F a -> F b), that is, a mapping from arrows of Hask to arrows of Hask compatible with the object-mapping F. So, yes, all instances of Functor are endofunctors. There are several generalizations available on Hackage, e.g. Control.Categorical.Functor.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • You say *arrows of Hask compatible with the object-mapping `F`*. Is that a subcategory of Hask? –  Feb 11 '13 at 20:28
  • 3
    @Zoidberg Yup, it's the subcategory of Hask whose objects are the types whose outermost type constructor is `F`. – Daniel Wagner Feb 11 '13 at 20:29
  • Do I understand this correctly: theoretically these endofunctors not necessarily must work on types with kind `* -> *`, I mean functor could map a function `Int -> Char` to function `String -> Double`. As I understand, in theory functors work on any morphisms. But I guess that's not too practical. Or am I completely wrong here? – dimsuz Jul 11 '17 at 22:22
  • @dimsuz Hm. I'm fuzzy on exactly what you're proposing with your `Int -> Char`/`String -> Double` comment. Your other comment is also making me squint: you seem to be implying that there are morphisms that the existing `Functor` instances do not work on, but this is not correct. So I suspect there is still some misunderstanding; but I'm having trouble pinpointing exactly where. If you gave some more details about what source and target categories you were considering with your "map a function" comment, and what morphisms you think aren't mapped by existing `Functor`s, I could say more. – Daniel Wagner Jul 12 '17 at 04:09
  • 1
    my line of thoughts: the definition of functor: maps objects to objects, maps functions to functions (in Hask). So potentially some functor can map any function in this category to any other function in this category. So *potentially* there can be functor which maps some `Int -> Char` to `String -> Double`. I.e. `a -> b` to `c -> d`. Or is this false? I understand that Functor maps `a -> b` to `F a -> F b`, but could there ever be a functor which does the mapping without using a type constructor on the other end? Again, I mean at least in theory. – dimsuz Jul 12 '17 at 10:47
  • 1
    @dimsuz Yes, that would be allowed. Of course there are *some* rules about the mappings -- notably that the mapping on functions has to be compatible with the mapping on objects -- but the particular proposal you made doesn't obviously violate that rule yet. Modern Haskell even *almost* makes it possible via type families; languages that support first-class type-level functions would support it pretty naturally. – Daniel Wagner Jul 12 '17 at 15:01
  • thank you for clarification! Wanted to confirm that I got at least these basic points understood more or less right... – dimsuz Jul 12 '17 at 16:54
19

Yes, all Functor instances are endofunctors on Hask--in fact, endofunctors from all of Hask to a proper subcategory whose objects are the types obtained by applying a particular type constructor. That type constructor is what the Functor instance is associated with, and gives the mapping for objects; the mapping for morphisms is fmap, which (because we're only concerned with endofunctors on a cartesian closed category) is itself a family of morphisms in Hask.

It does make sense to consider other functors besides those which can have Functor instances, such as contravariant functors (from Hask to its opposite category). The arr function in the Arrow class also corresponds to a functor, from all of Hask to the category whose objects are the same as those of Hask and whose morphisms are described by the type constructor the Arrow instance is associated with.

Further generalizations are also possible (as Daniel Wagner notes), but tend to become increasingly awkward to use.

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
4

One important point about this is that what you really want is functors enriched in Hask, not just plain old functors. Hask is cartesian closed (not really, but it tries hard to be onesuch), and so it is naturally enriched in itself.

Now, enriched endofunctors give you a way of restricting to those implementable within the language: an enriched functor Hask -> Hask is a function at the level of objects (types) f a and for each pair of objects a, b a morphism in Hask going f : Hask(a,b) -> Hask(fa,fb). Of course, this is just fmap :: (a -> b) -> f a -> f b

Eduardo Pareja Tobes
  • 3,060
  • 1
  • 18
  • 19