Haskell colon within the zip function

Question

I struggle understanding this Haskell function. I know what it does superficially, but I'm unsure of how it achieves this functionality.

zip (x:xs) (y:ys) = (x,y) : zip xs ys 
zip xs ys = [ ]

What I think:

1. zip is the name of the function.
2. zip takes 2 parameters. (I believe currying is not important here).
3. The parammeters are (x:xs) and (y:ys)
4. zip returns a list of a tuple type (x,y).

Now I don't quite understand the parameters

(x:xs) (y:ys)

The colon appends something to the start of a list (returning the list), so why do we append something to the lists we want to zip? What are x and y in the function definition?

The right side seems pretty obvious: We insert(0) the tuple (x,y) to a list of tuples returned by zip.

(x,y) : zip xs ys 

Now zip xs ys = [ ] why would we always want an empty list if we just pass 2 lists?

Could you explain how the following call to zip would be evaluation:

zip [5,7,9] [1,3,5,11]

Answer 1

The (x:xs) on the left hand side of equations is a pattern. It deconstructs an argument.

The (x:xs) on the right hand side of equations is an expression. It constructs a value.

zip (x:xs) (y:ys) = 

means, zip is a function, expecting two arguments, both are expected to be non-empty lists.

                      (x,y) : zip xs ys 

this constructs an output value; its head is (x,y) and its tail is the result of calling zip xs ys:

       [ x1,   x2, x3, x4, ....
       [ y1,   y2, y3, y4, ....
      --------------------------
    [ (x1,y1) , ................

Trying to call zip (5,7,9) (1,3,5,11) won't work (will cause a compile-time type-mismatch error), because the first rgument here is a triple, and the second - 4-tuple; these are not lists. Lists are of varying sizes, but tuples have fixed sizes. The correct call is thus zip [5,7,9] [1,3,5,11]. You can see how it is reduced to a value (i.e. what result is describes), by substituting the numbers to the above scheme's x1, y1, x2, etc.

When one of the lists is exhausted, the call will be zip [] [11]. The above equation won't match this situation. Fortunately, you have another equation,

zip xs ys = 

which uses variables as patterns. This is an example of an irrefutable pattern; it always succeeds. So, whatever the two arguments are, first will be henceforth known as xs, second - ys, and the right hand side of the equation

               [ ]

will be entered, that shows that the value [] will be produced, always. The effect of it is that when the list arguments to zip are of different lengths, the extra elements of the longer list are ignored.

Answer 2

Let's work with a simpler example:

head (x:xs) = x

The thing to realize is that the list [1,2,3] is shorthand for 1:2:3:[], which is again shorthand for 1:(2:(3:[])) because (:) is right-associative. So taking

head [1,2,3]

that's the same as

head (1:(2:(3:[])))

And now we can see how the pattern resembles the input.

head (1:(2:(3:[])))
      ^  ^^^^^^^^
head (x:   xs     )

So x will be 1 and xs will be 2:(3:[]), in other words [2,3].

---

Expounding a little about pattern matching. The first equation for zip

zip (x:xs) (y:ys) = ...

matches when both lists have at least one element (because empty lists are not of the form a:b). The second equation

zip xs ys = ...

matches any arguments whatsoever, provided the first equation did not match (and that they are the right type, since Haskell is statically typed).