Recursive functions and pattern matching in ocaml

Question

The following code snippet comes from the official OCaml website:

# let rec compress = function
| a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
| smaller -> smaller;;
val compress : 'a list -> 'a list = <fun>

The above function 'compresses' a list with consecutive, duplicative elements, e.g. :

# compress ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;

- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]

I'm having a devil of a time understanding the logic of the above code. I'm used to coding imperatively, so this recursive, functional approach, combined with OCamls laconic - but obscure - syntax is causing me to struggle.

For example, where is the base case? Is it smaller -> smaller? I know smaller is a variable, or an identifier, but what is it returning (is returning even the right term in OCaml for what's happening here)?

I know that lists in OCaml are singly linked, so I'm also wondering if a new list is being generated, or if elements of the existed list are being cut? Since OCaml is functional, I'm inclined to think that lists are not mutable - is that correct? If you want to change a list, you essentially need to generate a new list with the elements you're seeking to add (or with the elements you're seeking to excise absent). Is this a correct understanding?

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2018-09-22T17:54:41

Yes, the base case is this:

| smaller -> smaller

The first pattern of the match expression matches any list of length 2 or greater. (It would be good to make sure you see why this is the case.)

Since OCaml matches patterns in order, the base case matches lists of lengths 0 and 1. That's why the programmer chose the name smaller. They were thinking "this is some smaller list".

The parts of a match statement look like this in general:

| pattern -> result

Any names in the pattern are bound to parts of the value matched against the pattern (as you say). So smaller is bound to the whole list. So in sum, the second part of the match says that if the list is of length 0 or 1, the result should just be the list itself.

Lists in OCaml are immutable, so it's not possible for the result of the function to be a modified version of the list. The result is a new list, unless the list is already a short list (of length 0 or 1).

So, what you say about the immutability of OCaml lists is exactly correct.

Recursive functions and pattern matching in ocaml

1 Answers