Haskell: beginner function syntax confusion

Question

I'm currently trying to learn Haskell, but I'm struggling with understanding the syntax. For example, take the map function:

map :: (s -> t) -> [s] -> [t]
map f [] = []
map f (x:xs) = f x : map f xs

I understand what the function does, and that map has a function f :: s -> t as a parameter. But I read map :: (s -> t) -> [s] -> [t] as "map is a function which maps a function mapping from s to t to s and then to t", which is obviously wrong. Could someone clear this up for me?

Answer 1

The type (s -> t) -> [s] -> [t] can be read in two ways. One way is to treat it as a function of two arguments, the first a function of type s -> t and the second a list of type [s]. The return value is of type [t].

The other way is to understand that function arrows are right-associative, so the type is equivalent to (s -> t) -> ([s] -> [t]). Under this interpretation, map is a function that takes a function from element to element s -> t and turns it into a function from list to list [s] -> [t].

Similarly, when using the function, you can think of map foo xs as applying the function map to two arguments foo and xs. Or, since function application is left-associative, you can think of it as (map foo) xs, applying map to the single argument foo to get back a new function which you then apply to xs.

Since Haskell functions are curried, these are just two ways of looking at the exact same thing.

Answer 2

It might be helpful to define a couple type aliases, to make it a bit more explicit what all those arrows and brackets are doing:

type F1 a b = a -> b  -- type synonym for single-argument functions
type List a = [a]  -- type synonym for lists

so now you can write map's type signature as:

map :: F1 s t -> List s -> List t

which, if you're more familiar with Java or C++ or whatever, looks syntactically a bit more like:

List<T> map(F1<S, T> fun, List<S> list); // applies fun to each element in list

So you can think of it this way: map takes a function and a list, and returns another list. However, since functions are curried in Haskell, you don't have to pass all parameters at once. You could get away with partially applying map to just its first argument. So really its type signature is more like:

F1<List<S>, List<T>> map(F1<S, T> fun); // returns a function that applies fun to each element in a list

... which, when you call map with just that one fun argument, gives you something that sort of looks like:

List<T> mapFun(List<S> list); // applies fun to each element in list

So now back to Haskell: you can read map :: (s -> t) -> [s] -> [t] either as:

• "map takes a function from s to t, and a list of s, and returns a list of t"
• "map takes a function from s to t, and turns it into a function from a list of s to a list of t"

The former is fine; the latter is more helpful.