Why is `pure` only required for Applicative and not already for Functor? [duplicate]

Question

Reading this Wikibook about Haskell and Category Theory basics, I learn about Functors:

A functor is essentially a transformation between categories, so given categories C and D, a functor F : C -> D

maps any object A in C to F(A), in D.

maps morphisms f : A -> B in C to F(f) : F(A) -> F(B) in D.

... which sounds all nice. Later an example is provided:

Let's have a sample instance, too:

instance Functor Maybe where
  fmap f (Just x) = Just (f x)
  fmap _ Nothing  = Nothing

Here's the key part: the type constructor Maybe takes any type T to a new type, Maybe T. Also, fmap restricted to Maybe types takes a function a -> b to a function Maybe a -> Maybe b. But that's it! We've defined two parts, something that takes objects in Hask to objects in another category (that of Maybe types and functions defined on Maybe types), and something that takes morphisms in Hask to morphisms in this category. So Maybe is a functor.

I understand how the definition of fmap is key. I am confused about how the "type constructor Maybe" provides the first part. I would have rather expected something like pure.

If I get it right, Maybe rather maps C to D. (Thus being a morphism on category level, which might be a requirement for a Functor)

I guess you could rephrase my question like this: Is there a Functor that does not have an obvious implementation of pure?

Answer 1

I think you're getting confused between types and values. Here's the definition of a functor:

Let C and D be categories. A functor F from C to D is a mapping that:

• associates to each object X ∈ C an object F(X) ∈ D.

• associates to each morphism f : X → Y ∈ C a morphism F(f) : F(X) → F(Y) ∈ D such that the following conditions hold:

  • F(id : X → X) = id : F(X) → F(X) for every object X ∈ C.
  • F(g ∘ f) = F(g) ∘ F(f) for all morphisms f : X → Y and g : Y → Z.

A category consists of objects and morphisms between objects.

All code in Haskell is a part of Hask, the Haskell category. In Hask:

1. Types are objects.
2. Functions are morphisms between types.

Hence, all Functor instances in Haskell are functors from Hask to Hask (i.e. they are endofunctors).

To put it more rigorously, for all instances of Functor in Haskell:

1. C = Hask.
2. D = Hask.

Now, each functor F is a mapping that associates to each object X ∈ C an object F(X) ∈ D.

1. Note that X and F(X) are objects of C and D respectively.
2. Since both C and D are Hask, both X and F(X) are types and not values.
3. Thus, F : Type → Type or in Haskell f : * -> *.

Indeed, this is precisely how the Functor type class is defined in Haskell:

class Functor (f : * -> *) where
    fmap :: (x -> y) -> (f x -> f y)

Here, fmap is the second part of the functor. It's a function from values to values. However, the Functor itself is a type constructor (i.e. a mapping from types to types). This is the reason Maybe is a functor and [] is a functor but Maybe Int and [Int] are not functors.

Note that pure does not form the first part of the functor definition because it's a mapping from an instance of X to an instance of F(X) (i.e. it's a function from values to values). However, we need a mapping from X to F(X) (i.e. a mapping from types to types).

Answer 2

If I get it right, Maybe rather maps C to D. (Thus being a morphism on category level, which might be a requirement for a Functor)

Not really, as C and D there are categories, and not Haskell types. A Functor (that is, an instance of the type class, as opposed to a functor in general) is a mapping from the Hask category (the category of Haskell types and functions) to Hask itself; that is, C and D are both Hask in that case. The Wikibook chapter mentions that in the section Functors on Hask. In your example, the Maybe type constructor provides the first part of the mapping by taking some type a (an object in Hask) to the type Maybe a (another object in Hask).

I guess you could rephrase my question like this: Is there a Functor that does not have an obvious implementation of pure?

One example is the pair Functor, (,) a. fmap is easy to write -- \f (x, y) -> (x, f y) -- but pure and (<*>) require a Monoid constraint on a, as there would be no way of dealing with the extra a values otherwise. For more discussion and other examples, see Good examples of Not a Functor/Functor/Applicative/Monad?