Do not understand this code

I am new to F# and found some code that I would like to use. This code takes a list and returns the second half of the list. I am hoping someone can go over line by line of what it does. I want to change it开发者_开发百科 so it returns the first half of the list. Here is the code after it is my questions.

let cut l = 
   let rec cut = function
       | xs, ([] | [_]) -> xs  
       | [], _ -> []
       | x::xs, y::y'::ys -> cut (xs, ys)
   cut (l, l)

What does = function do?

I am pretty sure that | xs, ([] | [_]) -> xs is if there is xs add it to the list

I do not understand what this does | [], _ -> []

| x::xs, y::y'::ys -> cut (xs, ys): I understand the first half, it creates two sublists, what confuses me is why cut is sending the tail xs, and ys. Doesn't cut only take one parameter?

---

The function returns the second half of the given list.

The interesting part of the code is only the nested (recursive) function, because the only purpose of the outer function is to call the nested function and pass it the specified list two times. The nested cut function has two arguments (as a tuple), so it's type is:

cut : 'a list * 'a list -> 'a list

When calling itself recursively, this is the function that is called (which explains why it is called with two arguments). Here is the commented code:

// The 'function' syntax means that the arguments of the function are matched against 
// several clauses. When the arguments (lists) match the clause, the clause is selected
// and its body will be executed. 
let rec cut = function
  // When the second list is empty or contains a single element,
  // the function return all elements of the first list
  | xs, ([] | [_]) -> xs  
  // When the first list is empty, return empty list
  | [], _ -> []
  // When first list is non-empty and second contains at least two elements,
  // the function takes one element from the first list and two elements from 
  // the second list (x, y, y'), ignores them and calls itself with the 
  // remaining lists as arguments.
  | x::xs, y::y'::ys -> cut (xs, ys)

cut ([ 1 .. 10 ], [ 1 .. 10 ])

The idea of the function is that it iterates over two copies of the same list. At every recursive step, it skips two elements from the second one and one element from the first one. By the time it reaches the end of the second list, the first one contains the second half of the list (because the function was skipping its elements 2-times slower).

To get the first half of the list you'll need to add additional parameter to your inner recursive cut function. You can use it for accumulating the elements from the first list. Again, you'll need to skip over elements of one of the list two-times faster. Instead of skipping first elements of the other list, you'll need to take them and add them to your accumulator.

I will not give you a full solution, but to give you some idea, here is pseudo-code:

  | x::xs, _::_::ys -> 
      // Call 'cut' recursively to process 'xs' and 'ys'
      // and add the element 'x' to the accumulator.

Another way to write the function would be to use match instead of function and write the two arguments as standard multiple arguments (instead of using a tuple). When ignoring elements in the last clause, it is also possible to use _ because their names are not needed:

let rec cut l1 l2 = 
  match l1, l2 with
  | xs, ([] | [_]) -> xs  
  | [], _ -> []
  | _::xs, _::_::ys -> cut xs ys

cut [ 1 .. 10 ] [ 1 .. 10 ]

---

The easiest way to change it to return the first half of the list is: pass the reversed list into the inner function and reverse the result.

let cut l = 
  let rec cut = function
    | xs, ([] | [_]) -> xs  
    | [], _ -> []
    | x::xs, y::y'::ys -> cut (xs, ys)
  let k = List.rev l
  cut (k, k) |> List.rev

Without List.rev

let cut l = 
  let rec cut f = function
    | x::_, [_] -> f [x]
    | _, [] -> f []
    | [], _ -> []
    | x::xs, _::_::ys -> cut (fun acc -> f (x::acc)) (xs, ys)
  cut id (l, l)

---

Easiest way to see what the cut function is doing is by realizing that the line below

| x::xs, y::y'::ys -> cut (xs, ys)

is emptying the 2nd list twice as fast as the 1st list. This is because it's pulling 2 elements off the head of the ys list and one element off the head of the xs list and throwing them away. If it does this continuously then ys will terminate first and when it does xs will contain the lower half of the original list.