Trying to understand this block of code in OCaml

Question

I am trying to understand what this block of code is doing:

let rec size x =
    match x with
      [] -> 0
    | _::tail -> 1 + (size tail) ;;

I know that this expression computes the size of a list, but I don't understand where in the code it reduces the list one by one. For example, I think it needs to go from [1;2;3] to [2;3] to [3], but where or how does it do it? I don't get it.

Thanks.

Answer 1

A list in OCaml is built recursively using empty list ([]) and cons (::) constructor. So [1; 2; 3] is a syntactic sugar of 1::2::3::[].

The size is computed by reducing x in each step using the pattern _::tail (_ denotes that we ignore the head of the list) and calling the same function size on tail. The function eventually terminates when the list is empty and the pattern of [] succeeds.

Here is a short illustration of how size [1; 2; 3] is computed:

   size 1::2::3::[]
~> 1 + size 2::3::[] // match the case of _::tail
~> 1 + 1 + size 3::[] // match the case of _::tail
~> 1 + 1 + 1 + size [] // match the case of _::tail
~> 1 + 1 + 1 + 0 // match the case of []
~> 3

As a side note, you can see from the figure that a lot of information needs to be stored in the stack to compute size. That means your function could result in a stack overflow error if the input list is long, but it is another story.

Answer 2

Actually this piece of code use the power of pattern matching to compute the size of the list.

the match means you will try to make x enter in one of the following pattern.

The first one [] means that your list is empty, so its size is 0. And the second one _::tail means you have one element (*) , followed by the rest of the list, so basically the size is 1 + size(rest of the list)

(*) The underscore means you don't care about the value of this element.