Haskell: beginner function syntax confusion

Question

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

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

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

Answer 1

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

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

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

Since the Haskell functions are curried , these are just two ways to look at the same thing.

Answer 2

It may be useful to define a pair of type aliases to make it more explicit what all of these arrows and brackets do:

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

now you can write a signature of type map as:

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

which, if you are more familiar with Java or C ++ or any other, looks syntactically more similar:

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

So you might think so: map takes a function and a list and returns another list. However, since functions are executed in Haskell, you do not need to pass all parameters at once. You can leave with a partial application of map only to its first argument. So really his 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 one argument to fun , gives you something like:

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

So, 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 list s to list t"

The first is beautiful; the latter is more useful.

Answer 3

What about "map" is a function that maps a (function s to t) over a (list s), giving (list t) "? This is a direct translation of the type signature into English (although not very elegant English).

Answer 4

Read the signature from the end: -> [t] means returns a list of t . The rest are "regular" parameters.

So map accepts a function that from s makes a t and a list s .

Now it’s easy: take the function s->t , apply it to each element [s] , and the result is [t] .