Haskell Matching pattern for lists

Question

I'm very new to Haskell, and I decided to learn it some days ago, thanks to the haskell wikibook.

I'm reading at this moment the matching pattern for lists, but I can't understand the syntax for list.

Here's an example (from the wikibook) :

doubleList :: [Integer] -> [Integer]
doubleList [] = []
doubleList (n:ns) = (2 * n) : doubleList ns

I don't understand the part (n:ns). How should I read it ?

Answer 1

You can read it like this: (head:tail), so if you have [1, 2, 3] and you match it with (x:xs), then x will be bound to the first element in the list, 1, and xs will be bound to the rest of the list, in this case [2, 3].

Answer 2

(:) is an operator with type a->[a]->[a]. This means that it takes an item, and a list of those items, and returns another list of the same items. The output list is formed by prepending the input item to the input list.

Here is how you can use it

1:[2,3]

will return

[1,2,3]

---

Because the (:) appears on the left hand side of the definition, in your case, you are pattern matching, and the operator is being used to deconstruct the value, rather than build it.

For example, if we have

func (first:rest) = ....

and call it like this

func [1,2,3]

the following values would be assigned

first=1 --notice, this is type a
rest=[2,3] --notice, this is type [a]

Answer 3

Another tip that might help you understand is by looking at the definition of the list data type:

data [] a = [] | a : ([] a)

Note that Haskell makes special syntax rules just for the list type, normally [] is not a valid constructor. This definition is equivalent to

data List a = Empty | Cons a (List a)

Where

[] = Empty
(:) = Cons

You would pattern match on this as

doubleList :: List Int -> List Int
doubleList Empty = Empty
doubleList (Cons n ns) = Cons (2 * n) (doubleList ns)

If written using infix form:

doubleList (n `Cons` ns) = (2 * n) `Cons` doubleList ns

So now hopefully you can see the parallels between the two definitions. Haskell also provides the special syntax rule that

[1, 2, 3, 4] = 1:2:3:4:[]

Since the former is much easier to write and read. In fact, whenever you have a list literal like [1, 2, 3, 4] in your code, the compiler first converts it to 1:2:3:4:[] before converting your code into an executable.