# Exceptions

In OCaml, exceptions are not objects, and there are no exception hierarchies. It may look unusual now, but in fact exceptions predate the rise of object oriented languages and it's more in line with original implementations. The advantage is that they are very lightweight.

The syntax for defining exceptions is reminiscent of sum types with a single data constructor. The data constructors can be either nullary or can have a value of any type attached to them.

All exceptions are essentially members of a single extensible (*open*) sum type *exn*, with some language
magic to allow raising and catching them.

This is how you can define new exceptions:

```
exception Access_denied
exception Invalid_value of string
```

## Raising and catching exceptions

It is important to learn how to use exceptions because many functions from the standard library and third party libraries alike use them, and it's impossible to avoid them even if you prefer to write your own code in purely functional style.

For example, the division functions `/`

and `/.`

raise a `Division_by_zero`

exception when the divisor is zero.

To learn how to raise an exception ourselves, we can reimplement the `/`

function to raise our own exception.
They are raised using the `raise : exn -> 'a`

function:

```
exception Invalid_value of string
let (//) x y =
if y <> 0 then x / y
else raise (Invalid_value "Attempted division by zero")
```

Now let's learn how to catch exceptions:

```
let () =
try
let x = 4 // 0 in
Printf.printf "%d\n" x
with Invalid_value s -> print_endline s
```

Note that `try ... with`

constructs are expressions rather than statements, and can be easily used
inside `let`

-bindings, for example to provide a default value in case an exception is raised:

```
let x = try 4 / 0 with Division_by_zero -> 0 (* x = 0 *)
let () = Printf.printf "%d\n" x
```

Another implication of the fact that `try ... with`

is an expression is that all expressions in the
`try`

and `with`

clauses must have the same type. This would cause a type error:

```
let x = try 4 / 0 with Division_by_zero -> print_endline "Division by zero"
```

You can catch multiple exceptions using a syntax similar to that of `match`

expressions:

```
let () =
try
let x = 4 // 0 in
Printf.printf "%d\n" x
with
Invalid_value s -> print_endline s
| Division_by_zero -> print_endline "Division by zero"
```

So far our examples assumed that we know all exceptions our functions can possibly raise, or do not want to catch any other exceptions, which is not always the case. Since there are no exception hierarchies, we cannot catch a generic exception, but we can use the wildcard pattern to catch any possible exception. The downside of course is that if an exception comes with an attached value, we cannot destructure it and extract the value since the type of that value is not known in advance.

```
let () =
try
let x = 4 // 0 in
Printf.printf "%d\n" x
with
Invalid_value s -> print_endline s
| _ -> print_endline "Something went wrong"
```

### Built-in exceptions

These are some exceptions that are commonly raised by standard library functions and you'll likely encounter them often:

```
exception Not_found
exception Failure of string
exception Sys_error of string
exception Match_failure of string * int * int
```

The `Not_found`

and `Failure`

exceptions are normally used to signal error conditions caused by user input. They are expected to be caught.

The `Match_failure`

exception is rather more special. It is raised when pattern matching is not exhaustive and the function hits the unhandled case.
The compiler will always warn you that your pattern matching is not exhaustive, but as we discussed earlier, the checking algorithm
can sometimes incorrectly assume that it's not exhaustive when it actually is, so by default it is a warning rather than error.
But if the compiler was right, it will cause runtime errors, ending with `Match_failure`

. Encountering that exception thus indicates
a programming error and supressing it with exception handling is never the right thing to do — if you genuinely do not care about remaining
cases, you should indicate it explicitly by adding a wildcard match clause.

# Linked lists and structural recursion

## Syntax and built-in functions for lists

Linked lists are among the most commonly used data structures. The type of lists in OCaml is `'a list`

.
Presence of a type variable `'a`

tells us that it's polymorphic: you can create lists of elements of
any type, but all elements must be the of the same type. Heterogenous lists cannot be created directly,
which is good for type safety.

We will learn about syntactic sugar for list and standard functions first, and then learn how that type is actually defined.

This is how to create a non-empty list: `let xs = [1; 2; 3; 4]`

. The empty list is written `[]`

.
Semicolon as a list element separator may look odd, but it has advantages,
since it makes it very easy to make a list of tuples: `let ys = ["foo", 1; "bar", 2]`

.
If the separator for list and tuple element was the same, it would require a lot
more parentheses.

The standard library defines a number of list functions in the `List`

module.
The simplest to use is the `List.length : 'a list -> int`

function that calculates list length:

```
let l = List.length ["foo"; "bar"; "baz"] (* l = 3 *)
```

Another simple function is `List.rev : 'a list -> 'a list`

that reverses a list.

Many of the `List`

module functions are higher order functions that use other functions as conditions
for searching, filtering, or transformation.

For example, there is a `List.exists : 'a list -> ('a -> bool) -> bool`

function that checks if
an element matching some condition exists in a list:

```
let x = List.exists (fun x -> x = 0) [0; 1; 2] (* x = true *)
```

Using partial application of the `(=)`

function we could make it shorter:

```
let x = List.exists ((=) 0) [0; 1; 2]
```

Many functions from that module also raise exceptions. Some third party libraries add functions
that return value of the option type instead, but in the standard library it's not the case.
Both approaches have their advantages and disadvantages. An exception-raising function can return
values of the same type as elements of the list, but forces you to handle exceptions.
A function of `'a list -> ('a -> bool) -> 'a option`

type would be exception-safe, but it would force
you to unwrap the option type value and handle the case of `None`

.
If you want to stick wit the
standard library, you'll need to handle exceptions.

For example, the `List.find : 'a list -> ('a -> bool) -> 'a`

function raises `Not_found`

exception
if it fails to find a matching element. This is how we could convert it to a function that returns
option type instead and then use its result in pattern matching:

```
let find_opt xs f =
try Some (List.find xs f)
with Not_found -> None
let () =
let x = find_opt ((=) 0) [1; 2; 3] in
match x with
None -> print_endline "This list does not include zero"
| Some _ -> print_endline "This list includes zero"
```

The `map : ('a -> 'b) -> 'a list -> 'b list)`

function that you are likely already familiar with from
other languages is also there. It takes a function and a list and applies the function to every element
of the list:

```
let squares = List.map (fun x -> x * x) [1; 2; 3]
```

The `List.filter : ('a -> bool) -> 'a list -> 'a list`

function should also look familar since it's implemented by many languages:

```
let evens = List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4] (* evens = [2; 4] *)
```

Another commonly used function is `List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a`

. In some other languages
it's known as `reduce`

. It takes a function, a list, and an initial values, and applies the function to every list
element and the accumulator. This is how we can write a function that calculates the average value of all elements
in a list:

```
let average xs =
let sum = List.fold_left (fun x y -> x +. y) 0.0 xs in
sum /. (float (List.length xs))
let x = average [1.0; 2.0; 3.0]
```

Note that `fold_left`

is not limited to function whose both arguments are same type. The function it takes must have type
`'a -> 'b -> 'a`

, which is more general than `'a -> 'a -> 'a`

. It also means the first argument of that function will be
the accumulator, while the second will be list element, since the accumulator value has type `'a`

, while the list is `'b list`

.

For functions like addition or multiplication it is not important, but for cases when it is important, the standard library
includes `List.fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b`

function that has order of argument types reversed.

Lists in OCaml are true linked lists, which means access to their elements is strictly sequential. To retrieve an element at
a known position, you may use `List.nth : 'a list -> int -> 'a`

function, but remember that it's *O(n)*.
Note that it will raise a `Failure`

exception
if list is too short. Elements are numbered from zero. This is an example of a program that will fail:

```
let () = Printf.printf "%d\n" @@ List.nth [1; 2; 3] 3
```

We could make it safer by handling the exception:

```
let () =
try List.nth [1; 2; 3] 3 |> Printf.printf "%d\n"
with Failure _ -> print_endline "List is too short"
```

Finally, if you are not planning to do anything with results of applying a function to list elements,
you can use the `List.iter : ('a -> unit) -> 'a list -> unit`

function. This is how you can print
all elements of a list with it for example:

```
let () =
List.iter print_endline ["foo"; "bar"; "baz"]
```

## Defining the list type

Many data structures, including linked lists, can be defined _inductively.

An *inductive definition* consists of two parts: a *base case* that defines the least possible element,
and an *inductive step* that defines how to make larger structures from it.

In terms of sum types, it can be said that an inductive type definition includes a nullary data constructor for the empty data structure and data constructors for non-empty data structures.

The list type is defined as follows:

- An empty list (
`[]`

) is a list (the base case). - A pair of a value
`x`

and a list`xs`

(`x :: xs`

) is also a list (the inductive step). - Nothing else is a list.

In OCaml we cannot create our own infix data constructors, but in imaginary syntax it could be written like this:

```
type 'a list = [] | 'a :: 'a list
```

So the `'a list`

type is simply a sum type with two data constructors, one for the empty list, and another for non-empty lists
made from a value (head) and another list (tail). The square brackets syntax is simply a syntactic sugar, and we could create
any list using the empty list value `[]`

and the `::`

constructor alone. The following definitions are equivalent:

```
let xs = []
let ys = [1]
let ys' = 1 :: []
let ys'' = 1 :: xs
let zs = [2; 1]
let zs' = 2 :: (1 :: [])
let ws = [3; 2; 1]
let ws' = 3 :: zs
```

The true syntax that is using data constructors is important because it can be used in pattern matching to define any possible list pattern. Here are some list patterns:

`[]`

— an empty list`_ :: _`

— any non-empty list`_ :: []`

— a list with exactly one element`_ :: _ :: _`

— a list with at least two elements

The square brackets syntax has limited use in pattern matching. It can be used for matching on lists of known length, but it cannot express any non-empty list for example.

- [_] — a list of one element
- [
*;*] — a list of two elements

If you want to destructure lists into its parts, you can always substitute the wildcard in those patterns with a variable name.

If special syntax for the `::`

infix constructor and empty list value `[]`

didn't exist in OCaml, we could make an equivalent
definition:

```
type 'a list = Nil | Cons of 'a * 'a list
```

The names *nil* for the empty list and *cons* for a pair of a value and another list come from the Lisp programming
language that was the first language to use this approach. When reading source code aloud, it's common to refer
to the `[]`

value as *nil* and the `::`

constructor as *cons*.

## Structural induction, structural recursion, and functions on lists

Structural induction and its twin, structural recursion, is a very common technique in functional programming. They can be used for both algorithm design and algorithm correctness proving.

For functions, we can rephrase the inductive definition as follows:

- A base case that defines how to calculate function value for the least possible element (empty data structure).
- An inductive step that defines how to calculate function value for the next element if we already know it for the previous element.

This is a generalization of mathematical induction on natural numbers. We have already seen an inductive definition when we discussed the factorial function:

- Base case:
*0! = 1* - Inductive step: (n + 1)! = n! * (n + 1)

The generalization of mathematical induction for data structures is known as *structural induction*.

Every inductive definition of a function can be naturally converted to a recursive algorithm, assuming we know how to destructure
a value into its parts. For the factorial function, we had to substitute destructuring a natural number *n* into
*m + 1* with substracting one from it.

Data structures defined as sum types can be directly destructured using pattern matching, which makes them easy to use with recursive functions.

Recursion derived from inductive definitions
is known as *structural recursion*. A structurally recursive function only applies itself to smaller parts of the original data.
Since every inductive definition includes a base case for the empty data structure, structural recursion is guaranteed to terminate.

The other kind — generative recursion that may generate new (possibly larger) data from the original arguments and apply itself to it, does not have this property and can be much harder to reason about.

Now we are ready to write our first function that works with lists. Let's write a function that calculates
list length. There are only two possible cases. The base case is the empty list, its length is zero.
Now to the inductive step: if we know that list `xs`

has length *n*, then we know that list `x :: xs`

has
length *n + 1*.

Or, formally:
1. *length [] = 0* (base case)
2. *length (x :: xs) = 1 + (length xs)* (inductive step)

This inductive definition can be easily converted to pattern matching:

```
let rec length xs =
match xs with
[] -> 0
| _ :: xs' -> 1 + (length xs')
```

It's very easy to see that our `length`

function is structurally recursive: every time the recursive step is handled,
`length`

is applied to the tail of the original list, which is guaranteed to be smaller than the original list.

It's also easy to see that this implementation is not tail recursive, since the outermost `1 + (length xs')`

expression cannot be evaluated
until all inner expressions are evaluated. To make it tail recursive, we could use a variant of structural recusrion sometimes called
*structural recursion with accumulator*:

```
let rec length xs =
let aux ys acc =
match ys with
[] -> 0
| _ :: ys' -> length (acc + 1) ys'
in aux xs 0
```

As it is with tail recursive functions, it's harder to reason about it, and harder to see if it's structurally recursive or not.
It generates new data as it goes. But notice that while new data is generated in the `acc`

variable, it is never used in pattern
matching, so the decision what to do next only depends on the value of the `ys`

argument, and `ys`

is only destructured and
never modified in a way that would add anything that wasn't present in the original `xs`

list. The function that remains
structurally recursive.

The map function can also be easily reimplemented with pattern matching. There are also just two cases.
The base case is the empty list, and since it has no elements there is nothing to apply a function to, so we return it unchanged.
The inductive step is also simple: to calculate `map (x :: xs)`

we apply `f`

to the head and cons it with `map xs`

.

```
let rec map f xs =
match xs with
[] -> []
| y :: ys -> (f y) :: (map f ys)
```

Some functions may require definitions with more than two cases. For example, if we want to write a function for checking is a list is sorted, we need special handling for lists with only one element in addition to the empty list.

If we limit the discussion to lists sorted in ascending order, our definition will look like this:

- An empty list is sorted.
- A list of one element is sorted.
- A list of two or more elements
`(x :: y :: ys)`

is sorted iff*x < y*and list`y :: ys`

is sorted.

```
let rec is_sorted xs =
match xs with
[] -> true
| [_] -> true
| x :: y :: ys ->
if x < y then (is_sorted (y :: ys))
else false
```

If we forget the case of a single element list, the OCaml compiler will warn us that pattern matching is not exhaustive.

## A note on lists and tail recursion

The length function was very easy to make tail recursive because it doesn't build a new list in its accumulator.
If we need to build another list, we need to take special care of element order. Since lists can only be built
by prepending a new head to existing tail, accumulating processed list element with `::`

will reverse the list.

Consider this naive attempt to make map tail recursive:

```
let rec map f xs acc =
match xs with
[] -> acc
| y :: ys -> map f ys ((f y) :: acc)
let xs = map (fun x -> x * x) [1; 2; 3] []
```

The `xs`

list is now `[9; 4; 1]`

. A correct implementation must reverse the accumulator before returning it:

```
let map f xs =
let rec map_aux f xs acc =
match xs with
[] -> acc
| y :: ys -> map_aux f ys ((f y) :: acc)
in List.rev @@ map_aux f xs []
```

## Immutability, and structural sharing

For primitive values we've worked with before this chapter, immutability doesn't mean much. When closures are not involved, shadowing a variable is not much different from variable assignment since the original value will eventually get garbage collected and lost forever.

Data structures like linked lists is where the benefits of immutability really come into play. Suppose you have multiple functions in your program that are working with the same linked list.

At the machine level, a linked list is a pair of a head value and a pointer to the tail. In a language like C, where you can take any of the pairs that comprise a list and change the head value or the tail pointer, you would be forced to make a complete copy of the entire list if any other functions are also working with it, else you may lose the original list forever.

If values are immutable, the data can be safely shared between multiple functions. When you create a new list by prepending a new head to existing tail, the tail still points to the original tail.

## Exercises

Using functions from the `List`

module, write a function calculates the sum of squares of all elements in a list.

Rewrite the `is_sorted`

function so that is can use any function for comparing elements rather than just `<`

.

Write a function that reverses a list.

Reimplement the `fold_left`

function in both usual and tail recursive ways.

Write a function that removes all even-numbered elements from a list, e.g. `["foo"; "bar"; "baz"; "quux"; "xyzzy"]`

should become `["foo"; "baz", "xyzzy"]`

.

## Comments !