Recursive function of a list

Question

I'm a little confused with that recursive function on haskell, can somebody explain me better ?

cut [] = ([],[])
cut (x:[]) = ([x],[]) 
cut (x:y:l) = let (xs,ys) = cut l
             in (x:xs,y:ys)

P.S. : The "let...in" part is confusing me a lot !

Answer 1

Haskell let has the following syntax: let <bindings> in <expression>

So you create some bindings and use that in the expression.

Example:

λ> let a = 3 in a + 3
6

The type of cut function is cut :: [a] -> ([a], [a]).

So, the function cut returns a tuple of type ([a],[a]) and that is exactly what is pattern matched in let expression of your cut function. The variable xs is pattern matched with the first element of the tuple i.e [a] and the next variable ys is pattern matched with the second element of the tuple which is another list.

Answer 2

cut [] = ([],[])
cut (x:[]) = ([x],[]) 

These are the edge conditions, and

cut (x:y:l) = let (xs,ys) = cut l
              in  (x:xs,y:ys)

is the recursive part. In it,

1. pattern matching (x:y:l) will break that the argument list of cut to three part, first element of it will be bound to x, second element to y, and the rest to l

2. let (xs, ys) = cut l says applying cut to l, the result should be a pair, and binding the first part of it to xs, the second part to ys

3. the value of cut (x:y:l) will be (x:xs,y:ys) in this case.

Answer 3

I'll go through an example step-by-step, and hopefully it will make things clearer. First let me establish the following line numbers:

1.  cut [] = ([],[])
2.  cut (x:[]) = ([x],[]) 
3.  cut (x:y:l) = let (xs,ys) = cut l
                  in (x:xs,y:ys)

Using the following call as an example:

cut [0,1,2]

This matches the clause of line the 3. because the list has at least 2 elements. Therefore x = 0, y = 1 and l = [2]. So it evaluates to the following:

let (xs,ys) = cut [2]
              in (0:xs, 1:ys)

cut [2] matches the clause of line 2. with x being bound to 2.

let (xs,ys) = ([2], [])
             in (0:xs, 1:ys)

We conclude then that xs = [2] and ys = []:

(0:[2], 1:[])

Which is the same as:

([0,2], [1])

So what this function is doing is splitting a list in two, by putting the even indexes in the first list and the odd ones in the second list.