Case analysis

Preamble

• Solving a problem means breaking it down into sub-problems.
• The simplest form of breakdown is case analysis: we list a set of cases that form a partition of the domain of the function.
• Each case is the restriction of the problem to a sub-domain. The cases must cover the whole domain, and be mutually exclusive.

The conditional

The conditional construct in Caml

The conditional corresponds to the computation “if condition then expression₁ else expression₂”, written:

if condition then expression1 else expression2

with:

• condition, a boolean expression;
• expression1 and expression2, two expressions of the same type, which is also the type of the conditional.

if 1 < 2 then "oui" else "non" ;;
let abs x = if x < 0 then -x else x ;;
abs (-5) ;;

Nesting and properties

if true then 1 else "un" ;;

Conditionals can be nested. For example, the logical equivalence of two booleans:

let equiv a b =
  if a then (if b then true else false)
  else (if b then false else true) ;;
equiv false false ;;

Which simplifies to let equiv a b = if a then b else not b.

Exceptions

An exception in a perfect world

Every function must return a value, whatever its argument. What do we do when a value that is not defined is requested?

1 / 0 ;;

This result is called an exception: here Division_by_zero, a failure of sorts. In general, an exception stops the program. In Caml, an exception is a value: so it can be caught, which we will see later.

Raising an exception

Two basic functions raise an exception, failwith and invalid_arg:

failwith "boum" ;;
invalid_arg "f" ;;
failwith ;;

Both functions take an argument of type string, the message. Their result has type 'a, a polymorphic type: it agrees with any other type, so an exception can be raised in any branch.

let inverse x =
  if x = 0 then failwith "inverse : division par zéro"
  else 1.0 /. float_of_int x ;;
inverse 4 ;;
inverse 0 ;;

The then branch has type 'a, the else branch type float: the conditional has type float.

Pattern matching

Pattern matching

• We can also use pattern matching (« filtrage » in French) to tell cases apart.
• Pattern matching matches patterns against values.
• It looks like some constructs of other languages (such as C's switch), but it is much more powerful: it tests not only the value being matched, but also its structure.

Explicit pattern matching

Example: we want to write the function defined by

A pattern matching example

So we must set up the correspondences

which is done in Caml by:

let f x = match x with
  | 0 -> 18
  | 1 -> 24
  | y -> y * y ;;
f 0 ;;
f 5 ;;

The pattern y is a name: it matches any value, and gives it this name in the associated expression.

General form of pattern matching

match expression with
| motif1 -> expression1
| motif2 -> expression2
  ...
| motifn -> expressionn

The first bar | is optional.

Order matters, and so does exhaustiveness

Let us swap the cases of the previous example:

let g x = match x with
  | y -> y * y
  | 0 -> 18
  | 1 -> 24 ;;
g 0 ;;

The pattern y matches every value: the next two cases are never used. Caml reports this, for each of them, with a warning: the function is accepted, but it does not do what we wanted.

let h x = match x with
  | 0 -> 18
  | 1 -> 24 ;;
h 2 ;;

Caml checked the pattern matching and found a forgotten case; it even gives an example of one. You must never let these warnings go by.

Matching several values

Several parameters of a function can be matched by nesting pattern matchings. For example, logical and:

let and_ a b =
  match a with
  | true -> (match b with
             | true -> true
             | false -> false)
  | false -> false ;;

Without them, the last case | false -> false is read as a case of match b, not of match a:

let and_ a b =
  match a with
  | true -> match b with
            | true -> true
            | false -> false
  | false -> false ;;

The wildcard pattern

There is a pattern that matches any value without giving it a name: the wildcard pattern, written _. It can be seen as an “otherwise”, when all the other values have been described.

let and_ a b =
  match a with
  | true -> (match b with
             | true -> true
             | _ -> false)
  | _ -> false ;;

Yes, provided we no longer need to name the value in that case, or we use the parameter x:

let f x = match x with
  | 0 -> 18
  | 1 -> 24
  | _ -> x * x ;;

“Or” patterns

If several values give the same result, they can be grouped together:

let f x = match x with
  | 1 | 2 | 3 -> 1
  | 4 | 5 | 6 -> 2
  | _ -> 5 ;;
f 5 ;;

These patterns with several cases, separated by |, are called “or” patterns. They match the union of the cases matched by their components.

Guarded patterns

Yes, with a guard: a pattern can be followed by a condition, introduced by when.

let sign x = match x with
  | 0 -> 0
  | y when y > 0 -> 1
  | _ -> -1 ;;
sign (-3) ;;

Pattern matching and anonymous functions

Anonymous functions

There is another syntax for defining functions. For example:

translates simply into Caml as an anonymous function, function x -> x + 1, which we give a name:

let successeur = function x -> x + 1 ;;

Anonymous functions with several arguments

(This point will be covered in more detail later.)

For a function with several arguments, each parameter must be introduced by a function parameter -> construct.

let moyenne = function a -> function b -> (a + b) / 2 ;;
moyenne 3 7 ;;

So the function moyenne is:

• the function that maps a (function a ->)…
• … to the function that maps b, for a fixed a, to $\frac{a+b}{2}$ (function b -> (a + b) / 2).

A notation made clear at last

(This point will be covered in more detail later.)

The function moyenne has type int -> int -> int, exactly like average in the previous chapter: the two ways of writing define the same function.

-> is right-associative: this type reads int -> (int -> int). It is the type of the function that maps an integer to a function that maps an integer to an integer. That is why average 10 was a function.

“Anonymous” pattern matching

Pattern matching uses -> (maps to), with the same meaning as in anonymous functions. So the two can be combined: function followed directly by pattern matching cases.

The function sign is the function that:

• maps 0 to 0;
• maps a strictly positive integer to 1;
• maps any other integer (a negative integer!) to -1.

That is, in Caml:

let sign = function
  | 0 -> 0
  | y when y > 0 -> 1
  | _ -> -1 ;;

With function, the parameter has no name: so the wildcard pattern _ can only be used if the associated expression does not depend on the value of the parameter. To use that value, we use a named pattern, like y above.

let est_zero = function
  | 0 -> true
  | _ -> false ;;
est_zero 3 ;;

Pattern matching and Cartesian product

A pair is written between parentheses, its components separated by a comma. Its components are extracted with fst and snd, or by destructuring it with a pattern:

(1, "un") ;;
let p = (3, 4) ;;
fst p ;;
snd p ;;
let (a, b) = p in a * b ;;
let norme2 (x, y) = x * x + y * y ;;
norme2 p ;;

Triples, quadruples, n-tuples, and pairs of pairs are built in the same way:

(1, 'a', "b", 2.0) ;;
((1, 2), (3, 4)) ;;

fst and snd only apply to pairs; for n-tuples, we destructure.

Matching several values

The Cartesian product makes it possible to match several values at the same time, by matching the pair they form. Let us write logical implication, which is only false if a is true and b false.

With the four explicit cases:

let implies a b = match (a, b) with
  | (true, true) -> true
  | (true, false) -> false
  | (false, true) -> true
  | (false, false) -> true ;;

Three cases give true. We first handle the only false case, and the wildcard pattern takes care of the others:

let implies a b = match (a, b) with
  | (true, false) -> false
  | _ -> true ;;
implies true false ;;
implies false true ;;

So the wildcard pattern _ can stand for anything, of any type, even a structured one!

With an anonymous function, the function takes a pair as its argument: its type changes.

let implies = function
  | (true, false) -> false
  | _ -> true ;;
implies (false, false) ;;

Finally, the parentheses around pairs are optional in patterns:

let implies a b = match a, b with
  | true, false -> false
  | _ -> true ;;