So far we have used the option type (see Section The polymorphic option type in the lecture notes of Week 09) to make functions total (see Section Total functions – a reminder in the lecture notes of Week 03). For example, consider functions that return the head (first element) or the tail (rest) of a non-empty list. Ideally they have the following type:
hd : 'a list -> 'a
tl : 'a list -> 'a list
However, these functions are partial (see Section Partial functions – a reminder in the lecture notes of Week 03) because they are undefined over the empty list. Since we cannot distinguish between the type of the empty list and the type of a non-empty list in their domain, we implement them using an option type in their codomain to manifest the existence or non-existence of the result:
hd : 'a list -> 'a option
tl : 'a list -> 'a list option
And then we can account for the case of the empty list, as detailed next.
Let hd' denote the function that, given a list, returns its head, if this head exists. Since an empty list has no head, applying hd' to the empty list should yield None:
let positive_test_hd' candidate =
(* positive_test_hd' : ('a list -> 'a option) -> bool *)
let b1 = (candidate [1] = Some 1)
and b2 = (candidate [2; 1] = Some 2)
and b3 = (candidate [3; 2; 1] = Some 3)
(* etc. *)
in b1 && b2 && b3;;
let negative_test_hd' candidate =
(* negative_test_hd' : ('a list -> 'a option) -> bool *)
(candidate [] = None);;
The following OCaml function tests whether its input is the empty list (in which case it returns the None constructor) or a non-empty list (in which case it returns the Some constructor):
let hd' vs =
(* hd' : 'a list -> 'a option *)
match vs with
| [] ->
None
| v :: _ ->
Some v;;
This OCaml function passes the unit tests:
# positive_test_hd' hd';;
- : bool = true
# negative_test_hd' hd';;
- : bool = true
#
Let tl' denote the function that, given a list, returns its tail, if this tail exists. Since an empty list has no tail, applying tl' to the empty list should yield None:
let positive_test_tl' candidate =
(* positive_test_tl' : ('a list -> 'a list option) -> bool *)
let b1 = (candidate [1] = Some [])
and b2 = (candidate [2; 1] = Some [1])
and b3 = (candidate [3; 2; 1] = Some [2; 1])
(* etc. *)
in b1 && b2 && b3;;
let negative_test_tl' candidate =
(* negative_test_tl' : ('a list -> 'a list option) -> bool *)
(candidate [] = None);;
The following OCaml function tests whether its input is the empty list (in which case it returns the None constructor) or a non-empty list (in which case it returns the Some constructor):
let tl' vs =
(* tl' : 'a list -> 'a list option *)
match vs with
| [] ->
None
| _ :: vs' ->
Some vs';;
This OCaml function passes the unit tests:
# positive_test_tl' tl';;
- : bool = true
# negative_test_tl' tl';;
- : bool = true
#
OCaml’s predefined functions, List.hd and List.tl, however, do not have an option type in their codomain. Instead, they are partial and just return the expected result when applied to a non-empty list:
# List.hd;;
- : 'a list -> 'a = <fun>
# List.hd [1; 2; 3];;
- : int = 1
# List.tl;;
- : 'a list -> 'a list = <fun>
# List.tl [1; 2; 3];;
- : int list = [2; 3]
#
In other words, when used in conjunction with Some, these two functions pass the positive tests above:
# positive_test_hd' (fun vs -> Some (List.hd vs));;
- : bool = true
# positive_test_tl' (fun vs -> Some (List.tl vs));;
- : bool = true
#
As for the exceptional case of the empty list, OCaml handles it by aborting the computation and returning a result at the toplevel that signals the name of the function whose application failed:
The result of applying [the function denoted by] List.hd to the empty list yields an exceptional result signaling that applying [the function named] hd failed:
# List.hd [];;
Exception: Failure "hd".
#
When the application of the head function fails, its context is abandoned, be it an ordinary context or a context where another error would be raised:
# 1 + List.hd [];;
Exception: Failure "hd".
# List.hd [] / 0;;
Exception: Failure "hd".
#
The result of applying List.tl to the empty list yields an exceptional result signaling that applying tl failed:
# List.tl [];;
Exception: Failure "tl".
#
When the application of the tail function fails, its context is abandoned, be it an ordinary context or a context where another error would be raised:
# List.length (List.tl []);;
Exception: Failure "tl".
# List.length (List.tl []) / 0;;
Exception: Failure "tl".
#
These exceptional situations are handled with an “exception” (hence the error message in the interactions above). This exception is named Failure.
The error case of attempting to divide a number by 0 is also handled with with an exception:
# 1/0;;
Exception: Division_by_zero.
# 10 + 1/0;;
Exception: Division_by_zero.
#
The exception associated with dividing by 0 is named Division_by_zero.
In the String library, the function get, given a string and an index, yields the character in the string at that index:
# String.get "abcde" 0;;
- : char = 'a'
# String.get "abcde" 1;;
- : char = 'b'
# String.get "abcde" 4;;
- : char = 'e'
#
Attempting to access a string with an invalid index is handled with an exception named Invalid_argument:
# String.length "abcde";;
- : int = 5
# String.get "abcde" 10;;
Exception: Invalid_argument "index out of bounds".
# String.get "abcde" 5;;
Exception: Invalid_argument "index out of bounds".
# String.get "abcde" (-1);;
Exception: Invalid_argument "index out of bounds".
#
OCaml provides us with a way to raise an exception, using the keyword raise:
<expression> ::= ...
| raise <expression>
The argument of raise must evaluate to the result of applying an exception constructor. Let us illustrate this exception raising with the three exception constructors discovered so far:
# raise Division_by_zero;;
Exception: Division_by_zero.
# raise (Failure "is not an option");;
Exception: Failure "is not an option".
# raise (Invalid_argument "One million fans can't be wrong.");;
Exception: Invalid_argument "One million fans can't be wrong.".
#
Harald: Failure "is not an option" is a pun, right?Alfrothul: ‘fraid so.
We are now in position to define our own head function using an exception instead of an option type. Let hd denote the function that, given a list, returns its head, if this head exists. Since an empty list has no head, applying hd to the empty list should raise the same exception as List.hd:
let positive_test_hd candidate =
(* positive_test_hd : ('a list -> 'a) -> bool *)
let b1 = (candidate [1] = 1)
and b2 = (candidate [2; 1] = 2)
and b3 = (candidate [3; 2; 1] = 3)
(* etc. *)
in b1 && b2 && b3;;
let hd vs =
(* hd : 'a list -> 'a *)
match vs with
| [] ->
raise (Failure "hd")
| v :: _ ->
v;;
This function passes its unit test and raises an exception when applied to the empty list:
# positive_test_hd hd;;
- : bool = true
# hd [];;
Exception: Failure "hd".
#
Likewise, let tl denote the function that, given a list, returns its tail, if this tail exists. Since an empty list has no tail, applying tl to the empty list should raise the same exception as List.tl:
let positive_test_tl candidate =
(* positive_test_tl : ('a list -> 'a list) -> bool *)
let b1 = (candidate [1] = [])
and b2 = (candidate [2; 1] = [1])
and b3 = (candidate [3; 2; 1] = [2; 1])
(* etc. *)
in b1 && b2 && b3;;
let tl vs =
(* tl : 'a list -> 'a list *)
match vs with
| [] ->
raise (Failure "tl")
| _ :: vs' ->
vs';;
This function passes its unit test and raises an exception when applied to the empty list:
# positive_test_tl tl;;
- : bool = true
# tl [];;
Exception: Failure "tl".
#
We are now in position to cater for invalid arguments, e.g., to implement the factorial function, which is only defined over non-negative integers with a more meaningful error behaviour than failing to satisfy an assertion. So prior to calling the local auxiliary function, let us test whether the argument of the OCaml function is negative or not:
let robust_fac n_init =
if n_init < 0
then raise (Invalid_argument ("robust_fac (" ^ string_of_int n_init ^ ")"))
else let rec fac n =
if n = 0
then 1
else n * (fac (pred n))
in fac n_init;;
To wit:
# robust_fac (1 + 4);;
- : int = 120
# robust_fac (1 - 4);;
Exception: Invalid_argument "robust_fac (-3)".
#
Sigbjørn: What happened before when we applied fac to a negative number?Loki (surprised): You mean you didn’t try?Halcyon: Right. I meant to ask – what does “looping recursion” mean?Sigbjørn (looking up after typing very fast): And “stack overflow”?Harald: Semiotics, anyone?
Created [24 Mar 2020]