Why is `pure` only required for Applicative and not already for Functor?
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 ?
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 morphism f : X → Y ∈ C a morphism F(f) : F(X) → F(Y) ∈ D such that the following conditions hold:
A category consists of objects and morphisms between objects.
All code in Haskell is a part of Hask, the Haskell category. In Hask:
Hence, all Functor instances in Haskell are functors from Hask to Hask (ie they are endofunctors).
To put it more rigorously, for all instances of Functor in Haskell:
C = Hask . D = Hask . Now, each functor F is a mapping that associates to each object X ∈ C an object F(X) ∈ D.
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 (ie 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) (ie it's a function from values to values). However, we need a mapping from X to F(X) (ie a mapping from types to types).
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, fy) -- 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?
I'd say that Applicative instance kind of becomes a stretch for Either (which I'd be perfectly fine with just having an instance for Bifunctor , but on the other hand using it as a Monad is convenient), and would (IMHO) be inappropriate for something like:
data ABC a = A a | B a | C a
Where all of A,B,C are "equally OK". Since there's no obvious choice for which should be used for pure , it shouldn't be provided at all. Having fmap is still perfectly fine, though.