`(a -> b) -> (c -> d)` in Haskell?

• A+
Category：Languages

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.