`(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.