Haskell Beginner: Currying/List Associativity

Question

From Learn You a Haskell:

Think about this list: [5]. That’s just syntactic sugar for 5:[]. On the left side of the :, there’s a value; on the right side, there’s a list. In this case, it’s an empty list. Now how about the list [4,5]? Well, that desugars to 4:(5:[]). Looking at the first :, we see that it also has an element on its left side and a list, (5:[]), on its right side. The same goes for a list like 3:(4:(5:6:[])), which could be written either like that or like 3:4:5:6:[] (because : is right-associative) or [3,4,5,6].

For the bolded part, I was expecting the growing list to culminate in 3:(4:(5:(6:[]))). This has something to do with my lack of understanding of currying, associativity, or both. Can someone tell me the flaw in my thinking?

Answer 1

Multiplication is associative. This means that (x * y) * z is the same as x * (y * z). However, : is not associative.

However, the terms "left-associative" and "right-associative" are different, and unrelated to the term "associative".

• If * is left-associative, then x * y * z is the same thing as (x * y) * z. The parentheses are redundant.

• If * is right-associative, then x * y * z is the same thing as x * (y * z). The parentheses are redundant.

Currying has nothing to do with this.

Since : is right-associative, [3,4,5,6] can be written as:

3:(4:(5:(6:[])))
3:4:(5:(6:[]))
3:(4:5:(6:[]))
3:4:5:(6:[])
3:(4:(5:6:[]))
3:4:(5:6:[])
3:(4:5:6:[])
3:4:5:6:[]

Answer 2

It's just a typo. There should be a parenthesis in the example (but it is the same behaviour without one, because of the associativity).

Answer 3

1. You say "I was expecting the growing list to culminate in 3:(4:(5:(6:[])))".

   Indeed you are right. If you want to eliminate all syntactic sugar from [3,4,5,6], you will get 3:(4:(5:(6:[])))

2. You are puzzled by the fact that as you state in the comment in your question "the book says 3:(4:(5:6:[]))".

   Again, you are right to be. In the interest of keeping presentation uniform, it shouldn't; this was probably a typo.

As far as Haskell syntax and semantics go though, there is nothing wrong with writing 3:(4:(5:6:[])) instead of 3:(4:(5:(6:[]))). What this boils down to is the question of whether 5:6:[] is the same as 5:(6:[]) or not. By the definition of right-associativity it is. Because : is right associative x:y:z = x:(y:z).

Just to add a geeky note here: by taking advantage of :'s right-associativity (i.e. not using parentheses), one can write 3:(4:(5:(6:[]))) quite concisely: 3:4:5:6:[]. This is only a single character longer than its syntactically sugared [3,4,5,6].

See also: http://en.wikipedia.org/wiki/Operator_associativity for more info on associativity.