Understanding Haskell Type Signatures

Question

I am in the process of teaching myself Haskell and I was wondering about the following type signatures:

Prelude> :t ($)
($) :: (a -> b) -> a -> b
Prelude>

How should I interpret (no pun intended) that?

A semi-similar result is also proving to be puzzling:

Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Prelude>

Answer 1

I'll start with map. The map function applies an operation to every element in a list. If I had

add3 :: Int -> Int
add3 x = x + 3

Then I could apply this to a whole list of Ints using map:

> map add3 [1, 2, 3, 4]
[4, 5, 6, 7]

So if you look at the type signature

map :: (a -> b) -> [a] -> [b]

You'll see that the first argument is (a -> b), which is just a function that takes an a and returns a b. The second argument is [a], which is a list of values of type a, and the return type [b], a list of values of type b. So in plain english, the map function applies a function to each element in a list of values, then returns the those values as a list.

This is what makes map a higher order function, it takes a function as an argument and does stuff with it. Another way to look at map is to add some parentheses to the type signature to make it

map :: (a -> b) -> ([a] -> [b])

So you can also think of it as a function that transforms a function from a to b into a function from [a] to [b].

---

The function ($) has the type

($) :: (a -> b) -> a -> b

And is used like

> add3 $ 1 + 1
5

All it does is take what's to the right, in this case 1 + 1, and passes it to the function on the left, here add3. Why is this important? It has a handy fixity, or operator precedence, that makes it equivalent to

> add3 (1 + 1)

So whatever to the right gets essentially wrapped in parentheses before being passed to the left. This just makes it useful for chaining several functions together:

> add3 $ add3 $ add3 $ add3 $ 1 + 1

is nicer than

> add3 (add3 (add3 (add3 (1 + 1))))

because you don't have to close parentheses.

Answer 2

($) is just function application. It gets a function of type a->b, an argument of type a, applies the function and returns a value of type b.

map is a wonderful example for how reading a function type signature helps understanding it. map's first argument is a function that takes a and returns b, and its second argument is a list of type [a]. So map applies a function of type a->b to a list of a values. And the result type is indeed of type [b] - a list of b values!

(a->b)->[a]->[b] can be interpreted as "Accepts a function and a list and returns another list", and also as "Accepts a function of type a->b and returns another function of type [a]->[b]". When you look at it this way, map "upgrade" f (the term "lift" is often used in this context) to work on lists: if double is a function that doubles an integer, then map double is a function that double every integer in a list.

Answer 3

Well, as said already, $ can be easily understood if you just forget about currying and see it like, say, in C++

template<typename A, typename B>
B dollar(std::function<B(A)> f, A x) {
  return f(x);
}

But actually, there is more to this than just applying a function to a value! The apparent similarity between the signatures of $ and map has in fact a pretty deep category-theory meaning: both are examples of the morphism-action of a functor!

In the category Hask that we work with all the time, objects are types. (That is a bit confusionsome, but don't worry). The morphisms are functions.

The most well-known (endo-)functors are those which have an instance of the eponymous type class. But actually, mathematically, a functor is only something that maps both objects to objects and morphisms to morphisms¹. map (pun intended, I suppose!) is an example: it takes an object (i.e. type) A and maps it to a type [A]. And, for any two types A and B, it takes a morphism (i.e. function) A -> B, and maps it to the corresponding list-function of type [A] -> [B].

This is just a special case of the functor class signature operation:

fmap :: Functor f   =>   (a->b) -> (f a->f b)

Mathematics doesn't require this fmap to have a name though. And so there can be also the identity functor, which simply assigns any type to itself. And, every morphism to itself:

($) :: (a->b) -> (a->b)

"Identity" exists obviously more generally, you can also map values of any type to themselves.

id :: a -> a
id x = x

And sure enough, a possible implementation is then

($) = id

---

¹Mind, not anything that maps objects and morphisms is a functor... it does need to satisfy the functor laws.