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?

Snead

Thanks for all the helpful answers. I selected the most detailed one to be "correct". – Snead

One simple Functor that does not admit pure is data Void a. The instance looks like instance Functor Void where { fmap f x = case x of {} }. (I'm not making this an answer because I don't think this example is particularly enlightening, even though it answers the only question you actually ask in the body.) – Pampa

@DanielWagner I think that's up to isomorphism the only Functor that doesn't admit pure: if you have any value v in the Functor you can define pure x = x <$ v. And I think every choice for pure is of this form, too. Of course this is not usually very unique. – Bovill

"takes objects in Hask to objects in another category (that of Maybe types and functions defined on Maybe types)" I think you are confusing the codomain and the image. The codomain here is the same as the domain, it's Hask, so we are talking about an endofunctor. The image of Hask under Maybe is a subset of the codomain -- all the Maybe types. You can easily convince yourself that Maybe doesn't take you out of Hask because you can apply Maybe multiple times -- Maybe (Mabe a), etc. -- the inner Maybe is still in the domain of Maybe. – Shortstop

@BartoszMilewski You are right, that was my confusion. And it has been clarified by the answers below. Am I supposed to correct my question (does not seem necessary to me)? – Snead

@ØrjanJohansen I disagree with that statement, there are plenty of functors that don't admit a pure. Here are a couple examples: instance Functor ((,) a) has fmap f (a, b) = (a, f b), but how would you implement pure? pure x = (error "shit", x). If you managed to implement pure you could obtain magic = fst . pure () magic :: a which is a sort of "proof" that such a pure would inherently involve _|_. (I realize Monoid a => (,) a admits a pure, but (,) a does not. Another example is instance Functor (Map k), and yet another is instance Functor (Const m). – Sarcoid

@Sarcoid I think you have to pick one a: I am making no claim about polymorphic type constructors. If a has a value without bottoms then clearly you have a pure without bottoms too. And if a has no value, then it's isomorphic to Void. But I see now that laziness complicates matters, since (error "shit", x) isn't itself bottom in Haskell. I think for these kinds of questions it is typical to ignore all bottoms (otherwise you could just say pure x = undefined and be done with it), and then I think my claim is still true for any monomorphic example. – Bovill

@ØrjanJohansen Cool, sure it might be true for any monomorphic example. Too bad that doesn't matter because a huge amount of functors are not defined in a monomorphic way, and this question is talking about why pure is not in Functor, which it very much SHOULD NOT be. And even examples that are monomorphic don't necessarily have a "best" default. For example with lists pure 5 :: ZipList Int and pure 5 :: [Int] are very very different, but both crucial for their respective Applicative instances. – Sarcoid

@Bartosz Is it reasonable to talk about types under Maybe as their own category (a subcategory of Hask, to be sure)? If so the quote is perfectly correct. That's always how I've viewed Haskell Functors, rather than as endofunctors. They can be viewed as endofunctors of course, but because a type constructor always creates new types most endofunctors on Hask are not expressible as Haskell Functors. – Leonor

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).

Preeminence

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?

Habergeon

Answer 3

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.

Oscar

Makes sense ... the arbitrariness in connection with implementing pure is deferred until someone implements Applicative (and at that point a choice must be made). – Snead

@Snead When you've decided how you want to implement <*> in your Applicative, pure isn't arbitrary anymore: it's constrained by the applicative laws. Implementing a totally arbitrary pure as part of Functor, where you wouldn't really have to think about how pure interacts with anything else, could make it easy to accidentally write a pure that doesn't work for Applicative (or Monad). – Leonor

Answer 4

The category Hask has types as objects and functions as arrows, so the object mapping provided by the Functor instance must map types to types.

fmap maps the arrows i.e. maps functions a -> b to functions f a -> f b for the functor f. The Functor type constructor is the mapping for objects i.e. between types.

For example the Maybe type constructor maps a type t to the type Maybe t e.g. String to Maybe String.

In contrast, pure maps values of some underlying type to a value of the corresponding applicative type e.g. "abc" and (Just "abc") are both values of String and Maybe String respectively.

Demise

Would you agree that the Wikibook article confuses the category morphism with pure, where it says: maps any object A in C to F(A), in D ? – Snead

The wikibook article is correct. The f in Functor f maps objects in the category Hask to objects in the category Hask. Note that a Haskell Functor is strictly an endofunctor - its domain and codomain must both be Hask. Then, the function fmap maps morphism in Hask (functions of type a -> b) to morphisms in Hask, specifically to the morphism f a -> f b. In the article, the functor is given type Hask ~> Hask. But note that this arrow isn't the function arrow - the function arrow takes types to types, not categories to categories. – Entresol

@Entresol indeed, now I get it. – Snead