Haskell function definition syntax

Question

I'm doing lists concatenation in the following ways (an example, using GHC):

myConcat :: [[a]] -> [a]
myConcat xs = foldr (++) [] xs
myConcat    = foldr (++) []

Can someone explain to me please why and how the above definitions work and this one does not:

myConcat xs = foldr (++) []

Is the last line of code intentionally not allowed (for a reason like the constructs might become confusing, it is useless, etc) or is it something deeper, maybe related to currying...

I hope I can shed some light on this, it really puzzles me :/

LATER EDIT: Besides the explanations given below, I've found a good source of information on the matter to be the section "Partial function application and currying" from Chap. 4 "Functional Programming" from the book "Real World Haskell". The book is available freely online.

Answer 1

Lets review the different versions:

myConcat xs = foldr (++) [] xs

This is the usual way, providing an argument, which is consumed by foldr. The type is [[a]] -> [a], because we have an argument of type [[a]] on the left side, which yields [a] when fed to the right side.

myConcat = foldr (++) []

Here foldr is partially applied, so we return a function which can take an additional argument, a list of lists. So what we get back from the right side is already what we need, it is not a "syntactical suger", but another way to express the same thing as the first version. The type is again [[a]] -> [a]: We have nothing on the left side, but give back a function of that signature at the right side.

myConcat xs = foldr (++) []

Here foldr is partially applied as well, and we return a function that can take an argument as before, but our definition has an additional argument xs, which isn't used on the right side. The compiler doesn't "know" that it is this argument we want to have applied to the right side. The type is t -> [[a]] -> [a]. Why?

Assume you have a square function:

sqr :: Int -> Int 
sqr x = x*x

What you are doing is essentially the same as providing an addition, unused argument:

sqr:: Int -> t -> Int 
sqr x y = x*x

The function still "works", e.g. sqr 3 "bla" yields 9, but the type signature is off, and the unused argument is... erm, unused. The unused argument has no fixed type, as it can be virtually "anything", it doesn't matter. So it gets type variable (t) in the signature.

Answer 2

Well, let's take a look at the type signature for the curried function foldr:

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

So foldr takes a binary function (i.e. a->b->b), a b value, a list of a values, and returns a b value.

Let's also look at the documentation for foldr to get a more clear definition:

foldr, applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:

Now, let's take a look at the type signature for myConcat xs = foldr (++) []

> :t myConcat
myConcat :: t -> [[a]] -> [a]

Hmm...that's not what we wanted...

The problem is that you never provided foldr a value of type [a]. So now, myConcat needs some value, of any type, to satisfy xs and a value of type [a] to complete foldr (++) [], like:

> myConcat 2 [[1,2],[3,4]] 
[1,2,3,4]
> myConcat Nothing [[1,2],[3,4]] 
[1,2,3,4]

That works, but the first argument is just a waste.

However, if we pass that xs value over to foldr (++) [], like:

myConcat xs = foldr (++) [] xs

and check its type signature

> :t myConcat
myConcat :: [[a]] -> [a]

Ah, much better. Now myConcat uses xs to complete the foldr function.

Also, myConcat = foldr (++) [] also works, and is actually an example of point-free style programming. If we check the type signature of foldr (++) [],

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

Since we already provided foldr its first two arguments through partial application, we get a function back that will takes a [[a]] value and do what we want! So we just assign it to a name, and it works just like the example above, but we didn't need to explicitly pass arguments!

> let myConcat = foldr (++) []
> :t myConcat
myConcat :: [[a]] -> [a]
> myConcat [[1,2],[3,4]]
[1,2,3,4]

Answer 3

myConcat xs = foldr (++) []

has the type t -> [[a]] -> [a] which is not the same as the type of the other two [[a]] -> [a].