13

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?

9
  • Thanks for all the helpful answers. I selected the most detailed one to be "correct".
    – ruben.moor
    Oct 30, 2015 at 18:06
  • 2
    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.) Oct 30, 2015 at 18:55
  • @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. Oct 30, 2015 at 22:17
  • 3
    "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. Oct 31, 2015 at 18:16
  • @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)?
    – ruben.moor
    Nov 2, 2015 at 11:52

4 Answers 4

16

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

4

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?

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.

2
  • Makes sense ... the arbitrariness in connection with implementing pure is deferred until someone implements Applicative (and at that point a choice must be made).
    – ruben.moor
    Oct 30, 2015 at 17:15
  • 1
    @ruben.moor 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).
    – Ben
    Dec 3, 2016 at 21:32
2

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.

3
  • 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 ?
    – ruben.moor
    Oct 30, 2015 at 17:16
  • 1
    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. Oct 30, 2015 at 17:32
  • @user2407038 indeed, now I get it.
    – ruben.moor
    Oct 30, 2015 at 18:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.