Trying to understand this block of code in OCaml

Question

I am trying to understand what this block of code does:

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

I know that this expression calculates the size of the list, but I don’t understand where in the code it compiles the list one by one. For example, I think that it should go from [1; 2; 3] to [2; 3] to [3], but where and how does he do it? I do not understand.

Thanks.

Answer 1

A list in OCaml is created recursively using the empty constructor ( [] ) and cons ( :: . Thus, [1; 2; 3] [1; 2; 3] [1; 2; 3] is the syntactic sugar 1::2::3::[] .

The size is calculated by decreasing x at each step using the _::tail pattern ( _ means that we ignore the head of the list) and call the same size function on tail . The function ends when the list is empty and the template [] completes successfully.

Here is a brief example of how size [1; 2; 3] size [1; 2; 3] size [1; 2; 3] :

  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 on the stack to calculate size . This means that your function may result in an error if the input list is long, but this is another story.

Answer 2

According to this article , there really is that exact example that you are discussing:

As we saw, the list can be either empty (the list has the form [] ), or consists of the first element (its head) and a sublist (its tail). Then the list has the form h::t .

The above statement simply gives you 0 if the list matches an empty list or uses pattern matching to extract the head (first element) and tail (all other elements), and then uses recursion to get the length of the tail.

So this is _::tail , which reduces the list, and 1 + (size tail) , which calculates the size. Bit before | is, of course, the condition for completing the recursion.

This may be more understandable (in my opinion) when viewed as:

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

(actually it is very similar to the format used on the linked page, I changed it a bit to align the characters -> ).

Answer 3

In fact, this piece of code uses the power of pattern matching to calculate the size of a list.

match means you try to make x enter one of the following patterns.

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

(*) Underline means that you do not care about the meaning of this element.

Answer 4

Each time you match the list, you can match the head::tail form template, where head will get the value of the first element and tail will get the remainder. This template will match any non-empty list, because the tail may be empty, but the head must exist.

Secondly, any template that you map in Ocaml, if you want, you can replace the variable with an underscore to say "something is here, but I'm not going to actually use it, so I don't give that name." Thus, in this program, instead of writing head::tail -> 1 + (size tail) they write _::tail -> 1 + (size tail) , since they actually do not use the first element, just ensuring that it exists.

Answer 5

It uses pattern matching to extract the tail of the list (calling it tail ), and then calls itself the tail. Perhaps the missing part for you is pattern matching.