Week 5 programming: lists¶

Subsite home page:
	http://bit.ly/focs-aux

A: Head and tail, first and second¶

You can get the head and the tail of a list with functions hd and tl.

In OCaml/utop, you first have to type

open List;;

to get access to these functions.

You can get the first and the second part of a pair with the functions fst and snd. This only works for 2-tuples (e.g. (3, "abc")), not smaller tuples (like (), (2, 3, 4), ...) .

Can you find the head and the tail of the terms from last week, if they exist?
Can you find the first and the second component of any pairs in those terms?

Check your answers with ocaml/utop.

B: Cons exercises¶

Which of these terms is valid? If it is valid, what is its value, and what is its type?

Check your answers with ocaml/utop.

3 :: []
3 :: 4 :: []
3 :: [4]
[3] :: []
[3] :: 4
[] :: []
[] :: [[]]
[[]] :: []
[[]] :: [[]]
[] :: [], []
[] :: []; []
[[] :: []; []]

(Note: this is very different!)

C: List exercises¶

Do the exercises from https://ocaml.org/learn/tutorials/99problems.html; solutions are provided.

Additional hints given on Canvas:

Some of the question use the OCaml option type. This type is used to return a special value (None) when a function cannot be computed, instead of throwing an exception. For example, the standard hd function is:
let hd = function
  | [] -> failwith "hd"
  | x :: _ -> x
and has type
val hd : 'a list -> 'a = <fun>
If you want to avoid throwing a failure the alternative is this:
let hd = function
  | [] -> None
  | x :: _ -> Some x
and has type
val hd : 'a list -> 'a option = <fun>
For the purpose of this assignment you can ignore the option type and use failwith instead of None.

For a longer discussion of option types read this article: https://blogs.janestreet.com/making-something-out-of-nothing-or-why-none-is-better-than-nan-and-null/

See also:	the assignment on Canvas

We did some exercises without option. I have here filled in our solutions.

Make a function last that finds the last element of a list. We want that:
```
last [3; 5] = 5
last [3] = 3
last [] = an error
```
(Now you can click on the button below; there is an answer.)
(answer goes here)
We are making a function on lists, so probably we’ll need recursion. (Use let rec.)

We can make a first attempt by just writing down these cases. Last of a two-element list should return the second element, and so forth. In the “otherwise” case (_), we wish to give an error.
let rec last l = match l with | [x; y] -> y | [x] -> x | [] -> failwith "last" | _ -> failwith "dunno"
We can make the last case more specific, because the list will not be empty:
let rec last l = match l with | [x; y] -> y | [x] -> x | [] -> failwith "last" | x::xs -> failwith "dunno"
We can not list all the possible list length, because a list can be arbitrarily long. So we need to use recursion. Usually, structural recursion is enough.

What’s the relation between last [2; 3; 4] and last of its tail, last [3; 4]?

They are equal. So we write:
let rec last l = match l with | [x; y] -> y | [x] -> x | [] -> failwith "last" | x::xs -> last (tl l)
We simplify this in two ways. Firstly, in the last case, we already have tl l in a variable, namely xs.
let rec last l = match l with | [x; y] -> y | [x] -> x | [] -> failwith "last" | x::xs -> last xs
We also don’t need to do the special case for two elements.
let rec last l = match l with | [x; y] -> y | [x] -> x | [] -> failwith "last" | x::xs -> last xs

Make a function pen that finds the penultimate element of a list.

Write down some example inputs and outputs like above, then write the solution.

(answer goes here)

We want

pen [] = error
pen [2; 3; 4] = 3
pen [2] = error
pen [2; 3] = 2

Solution:

let rec pen l = match l with
  | [] -> failwith "pen empty"
  | [a] -> failwith "pen of one element"
  | [a; b] -> a
  | x::xs -> pen xs ;;

Make a function pens that finds the last two elements of a list and puts them in a pair.