How to "read" Elm's -> operator

Question

I'm really loving Elm, up to the point where I encounter a function I've never seen before and want to understand its inputs and outputs.

Take the declaration of foldl for example:

foldl : (a -> b -> b) -> b -> List a -> b

I look at this and can't help feeling as if there's a set of parentheses that I'm missing, or some other subtlety about the associativity of this operator (for which I can't find any explicit documentation). Perhaps it's just a matter of using the language more until I just get a "feel" for it, but I'd like to think there's a way to "read" this definition in English.

Looking at the example from the docs…

foldl (::) [] [1,2,3] == [3,2,1]

I expect the function signature to read something like this:

Given a function that takes an a and a b and returns a b, an additional b, and a List, foldl returns a b.

Is that correct?

What advice can you give to someone like me who desperately wants inputs to be comma-delineated and inputs/outputs to be separated more clearly?

Answer 1

Short answer

The missing parentheses you're looking for are due to the fact that -> is right-associative: the type (a -> b -> b) -> b -> List a -> b is equivalent to (a -> b -> b) -> (b -> (List a -> b)). Informally, in a chain of ->s, read everything before the last -> as an argument and only the rightmost thing as a result.

Long answer

The key insight you may be missing is currying -- the idea that if you have a function that takes two arguments, you can represent it with a function that takes the first argument and returns a function that takes the second argument and then returns the result.

For instance, suppose you have a function add that takes two integers and adds them together. In Elm, you could write a function that takes both elements as a tuple and adds them:

add : (Int, Int) -> Int
add (x, y) = x+y

and you could call it as

add (1, 2)  -- evaluates to 3

But suppose you didn't have tuples. You might think that there would be no way to write this function, but in fact using currying you could write it as:

add : Int -> (Int -> Int)
add x =
  let addx : Int -> Int
      addx y = x+y
  in
    addx

That is, you write a function that takes x and returns another function that takes y and adds it to the original x. You could call it with

((add 1) 2)  -- evaluates to 3

You can now think of add in two ways: either as a function that takes an x and a y and adds them, or as a "factory" function that takes x values and produces new, specialized addx functions that take just one argument and add it to x.

The "factory" way of thinking about things comes in handy every once in a while. For instance, if you have a list of numbers called numbers and you want to add 3 to each number, you can just call List.map (add 3) numbers; if you'd written the tuple version instead you'd have to write something like List.map (\y -> add (3,y)) numbers which is a bit more awkward.

Elm comes from a tradition of programming languages that really like this way of thinking about functions and encourage it where possible, so Elm's syntax for functions is designed to make it easy. To that end, -> is right-associative: a -> b -> c is equivalent to a -> (b -> c). This means if you don't parenthesize, what you're defining is a function that takes an a and returns a b -> c, which again we can think of either as a function that takes an a and a b and returns a c, or equivalently a function that takes an a and returns a b -> c.

There's another syntactic nicety that helps call these functions: function application is left-associative. That way, the ugly ((add 1) 2) from above can be written as add 1 2. With that syntax tweak, you don't have to think about currying at all unless you want to partially apply a function -- just call it with all the arguments and the syntax will work out.