Haskell: arrow precedence with function arguments

Question

I'm a relatively experienced Haskell programmer with a few hours of experience, so the answer might be obvious.

After watching A taste of Haskell, I got lost when Simon explained how the append (++) function really works with its arguments.

So, here's the part where he talks about this.

First, he says that (++) :: [a] -> [a] -> [a] can be understood as a function which gets two lists as arguments, and returns a list after the last arrow). However, he adds that actually, something like this happens: (++) :: [a] -> ([a] -> [a]), the function takes only one argument and returns a function.

I'm not sure to understand how the returned function closure gets the first list as it expects one argument as well.

On the next slide of the presentation, we have the following implementation:

(++) :: [a] -> [a] -> [a]

[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

If I think that (++) receives two arguments and return a list, this piece of code along with the recursion is clear enough.

If we consider that (++) receives only one argument and returns a list, where does ys come from? Where is the returned function ?

Answer 1

The trick to understanding this is that all haskell functions only take 1 argument at most, it's just that the implicit parentheses in the type signature and syntax sugar make it appear as if there are more arguments. To use ++ as an example, the following transformations are all equivalent

xs ++ ys = ...
(++) xs ys = ...
(++) xs = \ys -> ...
(++) = \xs -> (\ys -> ...)
(++) = \xs ys -> ...

Another quick example:

doubleList :: [Int] -> [Int]
doubleList = map (*2)

Here we have a function of one argument doubleList without any explicit arguments. It would have been equivalent to write

doubleList x = map (*2) x

Or any of the following

doubleList = \x -> map (*2) x
doubleList = \x -> map (\y -> y * 2) x
doubleList x = map (\y -> y * 2) x
doubleList = map (\y -> y * 2)

The first definition of doubleList is written in what is commonly called point-free notation, so called because in the mathematical theory backing it the arguments are referred to as "points", so point-free is "without arguments".

A more complex example:

func = \x y z -> x * y + z
func = \x -> \y z -> x * y + z
func x = \y z -> x * y + z
func x = \y -> \z -> x * y + z
func x y = \z -> x * y + z
func x y z = x * y + z

Now if we wanted to completely remove all references to the arguments we can make use of the . operator which performs function composition:

func x y z = (+) (x * y) z    -- Make the + prefix
func x y = (+) (x * y)        -- Now z becomes implicit
func x y = (+) ((*) x y)      -- Make the * prefix
func x y = ((+) . ((*) x)) y  -- Rewrite using composition
func x = (+) . ((*) x)        -- Now y becomes implicit
func x = (.) (+) ((*) x)      -- Make the . prefix
func x = ((.) (+)) ((*) x)    -- Make implicit parens explicit
func x = (((.) (+)) . (*)) x  -- Rewrite using composition
func = ((.) (+)) . (*)        -- Now x becomes implicit
func = (.) ((.) (+)) (*)      -- Make the . prefix

So as you can see there are lots of different ways to write a particular function with a varying number of explicit "arguments", some of which are very readable (i.e. func x y z = x * y + z) and some which are just a jumble of symbols with little meaning (i.e. func = (.) ((.) (+)) (*))

Answer 2

Maybe this will help. First let's write it without operator notation which might be confusing.

append :: [a] -> [a] -> [a]
append [] ys = ys
append (x:xs) ys = x : append xs ys

We can apply one argument at a time:

appendEmpty :: [a] -> [a]
appendEmpty = append []

we could equivalently could have written that

appendEmpty ys = ys

from the first equation.

If we apply a non-empty first argument:

-- Since 1 is an Int, the type gets specialized.
appendOne :: [Int] -> [Int]
appendOne = append (1:[])

we could have equivalently have written that

appendOne ys = 1 : append [] ys

from the second equation.