4

In Category Theory, a Functor is a morphism between categories, that is, it maps each object in category A to another object in B, as well as mapping each morphism C -> D onto the respective objects in B, while preserving composition of morphisms. So one could say a functor is composed of two "parts", one that maps Objects to Objects, and one that maps Morphisms to Morphisms. In Haskell if I understood it properly, each Type in The Functor typeclass can be "mapped onto", that is a function of Type a -> b can be mapped onto a function F a -> F b. Now why doesn't there exist a return :: Functor f => a -> f a function, specifically for Functor? Is there no need, since we can simply utilize the definition of return in the Monad instance, since return is really only working on the functor part of a Monad, or is there another reason?

It striked me as strange, because if that were the way, why would't return be included in the Functor instance? I mean every monad has a functor part, so to me, that would make sense. Can anyone enlighten me in that matter?

Al Sneed
  • 93
  • 6
  • 3
    In category theory, a functor in general does not allow `return::a->F a` for all `a`. E.g., in the category of sets, defining `F a = emptySet` (and `F anyMorphism = identity_emptySet`) constructs a functor, but no `a -> F a` is possible for nonempty `a`. – chi Jan 18 '23 at 01:09
  • 1
    There is in fact a `Pointed` typeclass in `data.pointed` with `point :: a -> p a`. But not every functor can be made into an instance of `Pointed`, for example `data Void a deriving Functor` (essentially for reasons given by @chi) – sigfpe Jan 18 '23 at 01:12
  • See https://stackoverflow.com/a/67192985/745903 for an alternative implementation of the `Functor` class in which the "objects to objects" mapping appears explicitly. (And it is very different from `return`.) – leftaroundabout Jan 18 '23 at 09:55
  • In Haskell, type class resolution is type-directed so the structure of a `Functor f`-instance is determined by `f`. `f` itself is the object-mapping (mapping `Type -> Type`) and `fmap @f` is the arrow-mapping (maps `a -> a'` to `f a -> f a'`). Those are the two mappings, and the object-mapping determines the arrow-mapping. – Iceland_jack Jan 24 '23 at 02:20

1 Answers1

9

That's a common misconception and one that used to trip me up. You're right that a functor has two parts: one that maps objects to objects and one that maps functions to functions (more generally, arrows to arrows, but that's not really germane here). Now, when I have

instance Functor F where
    fmap f x = ...

You've already correctly surmised that fmap takes functions to functions. However, we already have a way to take objects to objects. Categorically, our objects are not values, they're types. So the "objects to objects" part is something that should map a type to another type. And that thing is called F. The name of our functor literally is the mapping from objects to objects. Given a type a, the type F a is some other type lifted by our functor.

Now that raises the fair question: What is return? It takes an a and produces an F a (for a monad F). More specifically, given a fixed monad F, the signature is

return :: forall a. a -> F a

Now carefully read that. That says "given any type a, I can come up with a function from a to F a". That is, it takes an object in our category (a type) and maps it into an arrow in our category (a function). A mapping from an object to an arrow is called a natural transformation, and that's exactly what return is.

Categorically speaking, a monad is a functor (the underlying type F together with fmap), together with two natural transformations:

  • return, which is a natural transformation 1 -> F (where 1 is the identity functor), and
  • join, which is a natural transformation F^2 -> F (where F^2 is F composed with itself)

That is, for any type a, return has type a -> F a and join has type F (F a) -> F a[1].

What would a typeclass with return and fmap look like? I'm not sure. I don't know of a Haskell library that implements that typeclass, and I'm not entirely sure what the laws would look like. A good guess might be fmap f . return === return . f, but we actually get that as a free theorem, so that's not our law. If you or someone else knows of this typeclass somewhere in the Hackage ecosystem, feel free to let me know.

[1] Haskell uses an equivalent definition of "monad" in terms of the bind operator (>>=) rather than join. They're equivalent mathematically, and I opted for the simpler definition here.

Silvio Mayolo
  • 62,821
  • 6
  • 74
  • 116
  • Could you elaborate on what you mean when saying "return" maps any type to an arrow or function? What does this function look like? – Al Sneed Jan 18 '23 at 01:18
  • 1
    Given any type `a`, `return` produces a function of type `a -> f a`. Usually we just think of `return` as *being* a function from `a -> f a`, but that's because Haskell hides the `forall a` in front. But there's a hidden type parameter out there. If you're comfortable with [TypeApplications](https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/type_applications.html), you can make the type argument explicit. For instance (in the specific case of `Monad Maybe`), `return` is a polymorphic function, but `return @Int` has type `Int -> Maybe Int` and is a single conrete function. – Silvio Mayolo Jan 18 '23 at 01:23
  • Last question, so really we specify the type e.g. `a` that we want to "lift" into the monad, and then "return" returns/gives us the function of type `a -> M a`. If thats the case a lot of stuff begins to make sense... – Al Sneed Jan 18 '23 at 01:30
  • 1
    Exactly! And that's exactly what a natural transformation is, in category theory. It's a thing that, when you specify a type, you get a function that does something neat with that type. – Silvio Mayolo Jan 18 '23 at 01:32
  • One finally last thing, does that mean that every functor in Haskell is an endofunctor in the category of haskell types? – Al Sneed Jan 18 '23 at 01:39
  • @AlSneed An endofunctor is just a functor from one category to itself (but not necessarily an identity functor; it could still map the objects and arrows to *different* objects and arrows in the same category). It's not actually a very interesting statement to a Haskell programmer, it's just saying that the `Functor` class can only map Haskell types to Haskell types, not to any different sort of category. – Ben Jan 18 '23 at 02:12
  • @AlSneed Haskell `Functor` is actually even more restricted than just "endofunctors on the category of Haskell types". A `Functor` always maps to a "subcategory". For example the entire structure of the category of Haskell types is mirrored under `Maybe` - for every distinct type `a` (including `Maybe` types!!) there is a distinct type `Maybe a`. A `Functor` always maps to a subcategory like that, it can't do any different sort of "rearranging" of Haskell types that a general endofunctor might be able to do. – Ben Jan 18 '23 at 02:16
  • Can I ask for a clarification? You say "A mapping from an object to an arrow is called a natural transformation, and that's exactly what return is." But your link explains a natural transformation as a mapping between *functors*, rather than a mapping from objects to arrows, and that seems to be how you're using it in the rest of the answer (e.g. where you say `return` is a natural transformation `1 -> F`, where `1` is the identity functor). It's not obvious to me how the two definitions of natural transformation are connected. – Ben Jan 18 '23 at 02:23
  • 2
    @Ben, note that the linked reference never refers to a *mapping* between functors. If F and G are two functors each from category C to D, a natural transformation "from F to G" is not a mapping from F to G. Rather, it is a collection of arrows indexed by objects in C. For each x in C, it gives an arrow F(x)->G(x) in the category D. So, it can be viewed as a mapping from objects in C to arrows in D. Or, in Haskell, it can be viewed as a mapping from types (objects in Hask) to functions (arrows in Hask) that maps each type `a` to a function with signature `F a -> G a`. – K. A. Buhr Jan 18 '23 at 03:02
  • @K.A.Buhr Right, that's making sense now (or re-making sense; I feel like I've learnt this about 5 times). And for `return` we're taking `F` as `Identity` and then leaving it out of the actual Haskell type because it's boring. I was used to natural transformations manifesting in Haskell as things with types like `(forall x. f x -> g x)`. Although technically it seems like it's not true that any old collection of arrows indexed by objects is definitely a natural transformation; a natural transformation *is* such a collection, but it has to meet some conditions to make the diagram commute. – Ben Jan 18 '23 at 03:41
  • 1
    @Ben Yes, you're right that not any old collection of arrows works. But in Haskell specifically, parametricity makes it impossible to create a collection of arrows that simultaneously is as polymorphic as necessary and violates the commuting diagrams. – Daniel Wagner Jan 18 '23 at 03:57
  • 2
    @Ben Actually, funnily enough that's basically what I meant by "free theorems" above. In the "Theorems for Free" short paper I linked, Wadler explains that any function that can be written in a type system with *parametricity* and which takes a type argument is a (lax) natural transformation. – Silvio Mayolo Jan 18 '23 at 03:58