CODEWITHSUNDEEP
functionfunctional-programmingocaml
hieutran42
hieutran42

Reputation: 75

Trying to understand this block of code in OCaml

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.

Upvotes: 4

Views: 239

Answers (5)

pad
pad

Reputation: 41290

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.

Upvotes: 10

paxdiablo
paxdiablo

Reputation: 881423

As per this article, which actually has that exact example you're discussing:

As we have seen, a list can be either empty (the list is of the form []), or composed of a first element (its head) and a sublist (its tail). The list is then of the form h::t.

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

So, it's the _::tail which reduces the list, and 1 + (size tail) which calculates the size. The bit before the | is, of course, the terminating condition for the recursion.

It may be more understandable (in my opinion) if viewed as:

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

(this is actually very similar to the format used in the linked page, I've just changed it slightly to line up the -> symbols).

Upvotes: 4

Keith Irwin
Keith Irwin

Reputation: 5668

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

Second, any pattern you're matching in Ocaml, if you want, you can replace a variable with an underscore to say "match something here, but I'm not going to actually use it, so I'm not giving it a name". So, in this program instead of writing head::tail -> 1 + (size tail), they write _::tail -> 1 + (size tail) since they aren't actually using the first element, just ensuring that it exists.

Upvotes: 4

Pierre
Pierre

Reputation: 155

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.

Upvotes: 4

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66793

It uses a pattern match to extract the tail of the list (naming it tail), then calls itself with the tail. Maybe the missing piece for you is the pattern matching.

Upvotes: 1

Related Questions