Usefulness of "function arrows associate to the right"?

Question

Reading http://www.seas.upenn.edu/~cis194/spring13/lectures/04-higher-order.html it states

In particular, note that function arrows associate to the right, that is, W -> X -> Y -> Z is equivalent to W -> (X -> (Y -> Z)). We can always add or remove parentheses around the rightmost top-level arrow in a type.

Function arrows associate to the right but as function application associates to the left then what is usefulness of this information ? I feel I'm not understanding something as to me it is a meaningless point that function arrows associate to the right. As function application always associates to the left then this the only associativity I should be concerned with ?

Answer 1

Function arrows associate to the right but [...] what is usefulness of this information?

If you see a type signature like, for example, f : String -> Int -> Bool you need to know the associativity of the function arrow to understand what the type of f really is:

1. if the arrow associates to the left, then the type means (String -> Int) -> Bool, that is, f takes a function as argument and returns a boolean.
2. if the arrow associates to the right, then the type means String -> (Int -> Bool), that is, f takes a string as argument and returns a function.

That's a big difference, and if you want to use f, you need to know which one it is. Since the function arrow associates to the right, you know that it has to be the second option: f takes a string and returns a function.

Function arrows associate to the right [...] function application associates to the left

These two choices work well together. For example, we can call the f from above as f "answer" 42 which really means (f "answer") 42. So we are passing the string "answer" to f which returns a function. And then we're passing the number 42 to that function, which returns a boolean. In effect, we're almost using f as a function with two arguments.

This is the standard way of writing functions with two (or more) arguments in Haskell, so it is a very common use case. Because of the associativity of function application and of the function arrow, we can write this common use case without parentheses.

Answer 2

When defining a two-argument curried function, we usually write something like this:

f :: a -> b -> c
f x y = ...

If the arrow did not associate to the right, the above type would instead have to be spelled out as a -> (b -> c). So the usefulness of ->'s associativity is that it saves us from writing too many parentheses when declaring function types.

Answer 3

If an operator # is 'right associative', it means this:

a # b # c # d  =  a # (b # (c # d))

... for any number of arguments. It behaves like foldr

This means that:

a -> b -> c -> d  =  a -> (b -> (c -> d))

Note: a -> (b -> (c -> d)) =/= ((a -> b) -> c) -> d ! This is very important.

What this tells us is that, say, foldr:

λ> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

Takes a function of type (a -> b -> b), and then returns... a function that takes a b, and then returns... a function that takes a [a], and then returns... a b. This means that we can apply functions like this

f a b c

because

f a b c  =  ((f a) b) c

and f will return two functions each time an argument is given.

Essentially, this isn't very useful as such, but is important information for when we want to interpret and call function types.

However, in functions like (++), associativity matters. If (++) were left associative, it would be very slow, so it's right associative.