- A+

This is yet another Haskell-through-category-theory question.

Let's take something simple and well-known as an example. `fmap`

? So `fmap :: (a -> b) -> f a -> f b`

, omitting the fact that `f`

is actually a `Functor`

. As far as I understand, `(a -> b) -> f a -> f b`

is nothing but a **syntax sugar** for the `(a -> b) -> (f a -> f b)`

; hence conclusion:

**(1)** `fmap`

is a function producing a function.

Now, **Hask** contains functions as well, so `(a -> b)`

and, in particular, `(f a -> f b)`

is **an object** of the Hask (because objects of the Hask are well-defined Haskell types - a-ka mathematical sets - and there indeed exists set of type `(a -> b)`

for each possible `a`

, right?). So, once again:

**(2)** `(a -> b)`

is an object of the Hask.

Now weird thing happens: `fmap`

, obviously, is a **morphism** of the Hask, so it is a function, that takes another function and transform it to a yet another function; **final function hasn't been applied yet**.

Hence, one needs one more Hask's morphism to get from the `(f a -> f b)`

to the `f b`

. For each item `i`

of type `a`

there exists a morphism `apply_i :: (f a -> f b) -> f b`

defined as `/f -> f (lift i)`

, where `lift i`

is a way to build an `f a`

with particular `i`

inside.

The other way to see it is `GHC`

-style: `(a -> b) -> f a -> f b`

. On the contrast with what I've written above, `(a -> b) -> f a`

is mapping to the regular object of the Hask. But such a view contradicts fundamental Haskell's axiom - no multivariate functions, but applied (curried) alternatives.

I'd like to ask at this point: is `(a -> b) -> f a -> f b`

suppose to be an `(a -> b) -> (f a -> f b) -> f b`

, sugared for simplicity, or am I missing something really, really important there?

`fmap`

is actually an entire *family* of morphisms. A morphism in **Hask** is always from a concrete type to another concrete type. You can think of a function as a morphism if the function has a concrete argument type and a concrete return type. A function of type `Int -> Int`

represents a morphism (an endomorphism, really) from `Int`

to `Int`

in **Hask**. `fmap`

, however has type `Functor f => (a -> b) -> f a -> f b`

. Not a concrete type in sight! We just have type variables and a quasi-operator `=>`

to deal with.

Consider the following set of concrete function types.

`Int -> Int Char -> Int Int -> Char Char -> Char `

Further, consider the following type constructors

`[] Maybe `

`[]`

applied to `Int`

returns a type we could call `List-of-Ints`

, but we usually just call `[Int]`

. (One of the most confusing things about functors when I started out was that we just don't have separate names to refer to the types that various type constructors produce; the output is just named by the expression that evaluates to it.) `Maybe Int`

returns the type we just call, well, `Maybe Int`

.

Now, we can define a bunch of functions like the following

`fmap_int_int_list :: (Int -> Int) -> [Int] -> [Int] fmap_int_char_list :: (Int -> Char) -> [Int] -> [Char] fmap_char_int_list :: (Char -> Int) -> [Char] -> [Int] fmap_char_char_list :: (Char -> Char) -> [Char] -> [Char] fmap_int_int_maybe :: (Int -> Int) -> Maybe Int -> Maybe Int fmap_int_char_maybe :: (Int -> Char) -> Maybe Int -> Maybe Char fmap_char_int_maybe:: (Char -> Int) -> Maybe Char -> Maybe Int fmap_char_char_maybe :: (Char -> Char) -> Maybe Char -> Maybe Char `

Each of these is a distinct morphism in **Hask**, but when we define them in Haskell, there's a lot of repetition.

`fmap_int_int_list f xs = map f xs fmap_int_char_list f xs = map f xs fmap_char_int_list f xs = map f xs fmap_char_char_list f xs = map f xs fmap_int_int_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y) fmap_int_char_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y) fmap_char_int_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y) fmap_char_char_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y) `

The definitions don't differ when the type of `f`

differs, only when the type of `x`

/`xs`

differs. That means we can define the following *polymorphic* functions

`fmap_a_b_list f xs = map f xs fmap_a_b_maybe f x = case x of Nothing -> Nothing; Just y -> Just (f y) `

each of which represents a set of morphisms in **Hask**.

`fmap`

itself is an umbrella term we use to refer to constructor-specific morphisms referred to by all the polymorphic functions.

With that out of the way, we can better understand `fmap :: Functor f => (a -> b) -> f a -> f b`

.

Given `fmap f`

, we first look at the type of `f`

. We might find out, for example, that `f :: Int -> Int`

, which means `fmap f`

has to return one of `fmap_int_int_list`

or `fmap_int_int_maybe`

, but we're not sure which yet. So instead, it returns a *constrained* function of type `Functor f => (Int -> Int) -> f Int -> f Int`

. Once that function is applied to a value of type `[Int]`

or `Maybe Int`

, we'll finally have enough information to know which morphism is actually meant.