:PROPERTIES:
:ID: dec185e3-1f1f-4d44-86d5-7809c1f84e46
:mtime: 20231027081204 20231025053304 20231025043117 20231025020400 20231024083559 20231024072345 20231023093441 20231023073740 20231021052008
:ctime: 20231021052001
:END:
#+title: Foundations of CS Supervision 3 solutions -- Atticus Kuhn
#+filetags: :public:project:
* Assigment
For the third supervision, please attempt the following exam questions:
- 2003 Paper 1 Question 5
- 2004 Paper 1 Question 5
- 2005 Paper 1 Question 6
- 2019 Paper 1 Question 2
* Questions
** 2003 Paper 1 Question 5
*** Problem
(a) Describe how lazy lists can be implemented using ML. [2 marks]
(b) Code a function to concatenate two lazy lists, by analogy to the ‘append’
function for ordinary ML lists. Describe what happens if your function is
applied to a pair of infinite lists. [3 marks]
(c) Code a function to combine two lazy lists, interleaving the elements of each.
[3 marks]
(d ) Code the lazy list whose elements are all ordinary lists of zeroes and ones,
namely [], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], . . . . [6 marks]
(e) A palindrome is a list that equals its own reverse. Code the
lazy list whose elements are all palindromes of 0s and 1s, namely
[], [0], [1], [0, 0], [0, 0, 0], [0, 1, 0], [1, 1], [1, 0, 1], [1, 1, 1], [0, 0, 0, 0], . . . . You may
take the reversal function rev as given. [6 marks]
*** Solution
(a)
Here is my definition of a lazy list.
#+BEGIN_SRC ocaml
type 'a llist =
| Nil
| Cons of (unit -> 'a * 'a llist)
#+END_SRC
#+RESULTS:
: type 'a llist = Nil | Cons of (unit -> 'a * 'a llist)
I acknowledge that you could also define lazy lists as:
#+BEGIN_SRC ocaml
type 'a llist2 =
| Nil2
| Cons2 of 'a * (unit -> 'a llist2)
#+END_SRC
#+RESULTS:
: type 'a llist2 = Nil2 | Cons2 of 'a * (unit -> 'a llist2)
but I think these 2 definitions are roughly equivalent.
Here is a utility function for inspecting the first $n$ elements
of a lazy list.
#+BEGIN_SRC ocaml
let rec view n = if n = 0 then Fun.const [] else function
| Nil -> []
| Cons x -> let (a , b) = x () in a :: (view (n - 1) b)
#+END_SRC
#+RESULTS:
: <fun>
(b)
Here is my concat function:
#+BEGIN_SRC ocaml
let rec concat (a : 'a llist) (b : 'a llist) : 'a llist
= match a with
| Nil -> b
| Cons x -> let (first , rest) = x () in Cons (fun _ -> (first , concat rest b))
#+END_SRC
#+RESULTS:
: <fun>
Here is an alternative version which is even lazier than the first version:
#+BEGIN_SRC ocaml
let pairmap f g (a , b) = (f a , g b)
let rec concat (a : 'a llist) (b : 'a llist) : 'a llist
= match a with
| Nil -> b
| Cons x -> Cons (fun _ -> pairmap Fun.id (Fun.flip concat b) (x ()))
#+END_SRC
#+RESULTS:
: <fun>
(c)
Here is my interleave function for lazy lists.
#+BEGIN_SRC ocaml
let rec interleave (a : 'a llist) (b : 'a llist) : 'a llist =
match a , b with
| Nil , Nil -> Nil
| Nil , Cons x -> Cons x
| Cons x, Nil -> Cons x
| Cons x , Cons y -> let (a , b) = x () in
let (c , d) = y () in
Cons (fun _ -> (a , Cons (fun _ -> (c , interleave b d))))
#+END_SRC
#+RESULTS:
: <fun>
Let us test that interleave works correctly:
#+BEGIN_SRC ocaml :exports both
view 10 (interleave bin_list bin_list)
#+END_SRC
#+RESULTS:
| 0 | |
| 0 | |
| 1 | |
| 1 | |
| 0 | 0 |
| 0 | 0 |
| 0 | 1 |
| 0 | 1 |
(d)
Here is my code for the list of binary numbers.
The way it works is that I iteratively produce
the next binary number.
#+BEGIN_SRC ocaml
let rec iterate (initial : 'a ) (next : 'a -> 'a ) : 'a llist
= Cons (fun _ -> (initial, iterate (next initial) next ))
let rec next_bin_aux = function
| [] -> [0]
| 0 :: xs -> 1 :: xs
| 1 :: xs -> 0 :: (next_bin_aux xs)
let next_bin xs = List.rev (next_bin_aux (List.rev xs))
let bin_list : int list llist = iterate [] next_bin
#+END_SRC
#+RESULTS:
: Cons <fun>
#+BEGIN_SRC ocaml :exports both
view 16 bin_list
#+END_SRC
#+RESULTS:
| 0 | | | |
| 1 | | | |
| 0 | 0 | | |
| 0 | 1 | | |
| 1 | 0 | | |
| 1 | 1 | | |
| 0 | 0 | 0 | |
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 0 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 | |
| 1 | 1 | 1 | |
| 0 | 0 | 0 | 0 |
(e)
I use the binary numbers to construct binary palindromes.
If $X$ is a binary number, then there are 3 ways to turn $X$ into
a palindrome:
1) X @ X'
2) X @ [0] @ X'
3) X @ [1] @ X'
#+BEGIN_SRC ocaml
let rec pal_aux (l : int list llist ) : int list llist =
match l with
| Nil -> Cons (fun _ -> ([0], Cons (fun _ -> ([1], Nil))) )
| Cons x -> Cons (fun _ -> let (a , b) = x() in
let a' = List.rev a in (a @ a',
Cons (fun _ -> (a @ [0] @ a' ,
Cons (fun _ -> (a @ [1] @ a' , pal_aux b)) ))))
let palindromes = pal_aux bin_list
#+END_SRC
#+RESULTS:
: Cons <fun>
Let us test that palindromes works correctly.
#+BEGIN_SRC ocaml :exports both
view 16 palindromes
#+END_SRC
#+RESULTS:
| 0 | | | | |
| 1 | | | | |
| 0 | 0 | | | |
| 0 | 0 | 0 | | |
| 0 | 1 | 0 | | |
| 1 | 1 | | | |
| 1 | 0 | 1 | | |
| 1 | 1 | 1 | | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | |
#+BEGIN_SRC ocaml :exports both
view 8 bin_list
#+END_SRC
#+RESULTS:
| 0 | | |
| 1 | | |
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 | |
| 0 | 0 | 0 |
** 2004 Paper 1 Question 5
*** Problem
https://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2004p1q5.pdf
The following ML datatype can be viewed as defining a lazy or infinite sort of tree
where each node in the tree holds an integer:
#+BEGIN_SRC ocaml
type tr =
N of int * (unit -> tr) * (unit -> tr);
#+END_SRC
#+RESULTS:
: type tr = N of int * (unit -> tr) * (unit -> tr)
(a) Write a function called ndeep such that if n is an integer and z is a tree (i.e. of
type tr) the call ndeep n z will return an ordinary list of all the $2^n$ integers
at depth exactly n in the tree. Note that if n = 0 it will return a list of length
1, being just the top integer in the tree. Comment on its efficiency. [8 marks]
(b) You are given a tr, and told that it contains arbitrarily large values at least
somewhere in it. You want to find a value from it that is bigger than 100
(but if there are many big values it does not matter which one is returned).
Because the tree is infinite you cannot use simple depth-first search: you decide
to use iterative deepening. Thus you first check all integers at depth 1, then
at depth 2, depth 3, . . . and return when you first find a value that is greater
than 100.
Use exception handling to return the large value when you find it. Present
and explain code that searches the lazy tree. [12 marks]
*** Solution
(a)
ndeep returns those nodes which are n deep:
#+BEGIN_SRC ocaml
let rec ndeep (n : int) (z : tr) : int list =
match z with
| N (a , left, right) -> if n = 0 then [a] else (ndeep (n - 1) (left ())) @ (ndeep (n - 1) (right ()))
#+END_SRC
#+RESULTS:
: <fun>
(b)
iterative deep tries to search at depth $n=0$. If iterative deep fails at
depth $n = k$, it tries again at depth $n = k+ 1$
#+BEGIN_SRC ocaml
let search n tr = List.find ((>) 100) (ndeep n tr)
let rec iterative_deep_aux n tr = try search n tr with Not_found -> iterative_deep_aux (n + 1) tr
let iterative_deep = iterative_deep_aux 0
#+END_SRC
#+RESULTS:
: <fun>
** 2005 Paper 1 Question 6
*** Problem
https://www.cl.cam.ac.uk/teaching/exams/pastpapers/y2005p1q6.pdf
Consider a datatype of binary trees where both leaves and branches carry labels:
#+BEGIN_SRC ocaml
type 'a tree = Twig of 'a
| Br of 'a * 'a tree * 'a tree;
#+END_SRC
#+RESULTS:
: type 'a tree = Twig of 'a | Br of 'a * 'a tree * 'a tree
A path in a binary tree is a series of labels proceeding from the root to a leaf, as
shown in the diagram:1
2
4
4
7 9 3
Consider the problem of finding a path in a binary tree such that the integer sum
of the labels satisfies a given property. (In the example above, the highlighted path
sums to a prime number.)
(a) Write an ML function find path such that find path p t returns some path
in t whose sum satisfies the boolean-valued function p. If no such path exists,
the function should raise an exception. [5 marks]
(b) Write an ML function all paths such that all paths p t returns the list of
all paths in t whose sums satisfy the boolean-valued function p. [6 marks]
(c) Write an ML function all pathq that is analogous to all paths but returns
a lazy list of paths. For full credit, your function should find paths upon
demand rather than all at once. [Hint: try adding solutions to an accumulating
argument.] [9 marks]
1
*** Solution
(a)
Here is a sample tree
#+BEGIN_SRC ocaml
let test_tree = Br(1, Br(4, Twig 7 , Twig 9) , Br(2, Twig 4 , Twig 3))
let isEven n = n mod 2 = 0
#+END_SRC
#+RESULTS:
: <fun>
find path uses exceptions in order to back-track. find path does a greedy DFS, greedily taking
the left path. If find path failts, it back-tracks to the last choice point.
#+BEGIN_SRC ocaml
exception NotFound
let rec find_path (p : int -> bool) = function
| Twig a -> if p a then [a] else raise NotFound
| Br (a , left, right) -> let q n = p (n + a)
in a :: (try
find_path q left
with NotFound -> find_path q right)
#+END_SRC
#+RESULTS:
: <fun>
Test findpath to check if it works.
#+BEGIN_SRC ocaml :exports both
find_path isEven test_tree
#+END_SRC
#+RESULTS:
| 1 | 4 | 7 |
all paths uses the non-determinism monad (which is isomorphic to the list monad) to non-deterministically
search all paths of the tree.
#+BEGIN_SRC ocaml
let rec all_paths p = function
| Twig a -> if p a then [[a]] else []
| Br (a , left , right) -> let q n = p (n + a) in
List.map (List.cons a) ((all_paths q left) @ (all_paths q right))
#+END_SRC
#+RESULTS:
: <fun>
Test that all paths is correct
#+BEGIN_SRC ocaml :exports both
all_paths isEven test_tree
#+END_SRC
#+RESULTS:
| 1 | 4 | 7 |
| 1 | 4 | 9 |
| 1 | 2 | 3 |
(c)
#+BEGIN_SRC ocaml
let rec all_paths_lazy p = function
#+END_SRC
** 2019 Paper 1 Question 2
*** Problem
(a) We are interested in performing operations on nested lists of integers in ML. A
nested list is a list that can contain further nested lists, or integers. For example:
[[3, 4], 5, [6, [7], 8], []]
We will use the datatype:
#+BEGIN_SRC ocaml
type nested_list = Atom of int
| Nest of nested_list list
#+END_SRC
#+RESULTS:
: type nested_list = Atom of int | Nest of nested_list list
Write the code that creates a value of the type nested list above. [1 mark]
(b) Write the function flatten that flattens a nested list to return a list of integers.
[3 marks]
(c) Write the function nested map f n that applies a function f to every Atom in n. [4 marks]
(d ) What is the type of f in Part (c)? [1 mark]
(e) Write a function pack as xs n that takes a list of integers and a nested list;
the function should return a new nested list with the same structure as n,
with integers that correspond to the integers in list xs. Note: It is acceptable
for the function to fail when the number of elements differ. Example:
#+BEGIN_SRC ocaml
> pack_as [1, 2, 3] (Nest [Atom 9, Nest [Atom 8, Atom 7]]);
val it = Nest [Atom 1, Nest [Atom 2, Atom 3]]: nested_list
#+END_SRC
#+RESULTS:
: Line 1, characters 0-1:
: 1 | > pack_as [1, 2, 3] (Nest [Atom 9, Nest [Atom 8, Atom 7]]);
: ^
: Error: Syntax error
[6 marks]
(f ) What does the data type nested zlist correspond to? [2 marks]
#+BEGIN_SRC ocaml
type nested_zlist = ZAtom of int
| ZNest of (unit -> nested_zlist list);
#+END_SRC
#+RESULTS:
: type nested_zlist = ZAtom of int | ZNest of (unit -> nested_zlist list)
(g) Write the function that converts a nested zlist to a nested list. [3 marks]
1
*** Solution
(a)
Here is a sample value of a nested list.
#+BEGIN_SRC ocaml
let test_list = Nest [Nest [Atom 3 ; Atom 4]; Atom 5; Nest [Atom 6; Nest [Atom 7]; Atom 8]; Nest []]
#+END_SRC
#+RESULTS:
: Nest
: [Nest [Atom 3, Atom 4], Atom 5, Nest [Atom 6, Nest [Atom 7], Atom 8],
: Nest []]
(b)
flatten recursively flattens each level of the nested list.
#+BEGIN_SRC ocaml
let rec flatten = function
| Atom x -> [x]
| Nest n -> List.concat_map flatten n
#+END_SRC
#+RESULTS:
: <fun>
Test if flatten works correctly.
#+BEGIN_SRC ocaml :exports both
flatten test_list
#+END_SRC
#+RESULTS:
| 3 | 4 | 5 | 6 | 7 | 8 |
(c)
Nested map needs to use List.map to map over all the children
in the case of nesting.
#+BEGIN_SRC ocaml
let rec nested_map f = function
| Atom x -> Atom (f x)
| Nest n -> Nest (List.map (nested_map f) n)
#+END_SRC
#+RESULTS:
: Line 2, characters 6-10:
: 2 | | Atom x -> Atom (f x)
: ^^^^
: Error: Unbound constructor Atom
Test if nested map works correctly:
#+BEGIN_SRC ocaml :exports both
nested_map ((+) 1) test_list
#+END_SRC
#+RESULTS:
: Nest
: [Nest [Atom 4, Atom 5], Atom 6, Nest [Atom 7, Nest [Atom 8], Atom 9],
: Nest []]
(d)
Here is the type signature of $f$.
#+BEGIN_SRC
int -> int
#+END_SRC
The function pack aux returns a pair of the result, and any unconsumed input that
can be passed along to the next stage.
By chaining together pack aux with fold left, we can pack a nested list.
#+BEGIN_SRC ocaml
exception WrongShape
let second f ( a , b ) = ( a , f b)
let append xs x = xs @ [x]
let nest x = Nest x
let rec pack_seq (unconsumed , result) y = second (append result) (pack_aux (unconsumed , y))
let rec pack_aux = function
| [] , Atom _ -> raise WrongShape
| x :: xs , Atom _ -> (xs , Atom x)
| xs , Nest [] -> (xs , Nest [])
(* | [] , Nest (_ :: _) -> raise WrongShape *)
| xs , Nest ys -> second nest (List.fold_left pack_seq (xs , []) ys)
let pack xs n = snd (pack_aux (xs , n))
#+END_SRC
#+RESULTS:
: Line 5, characters 67-75:
: 5 | let rec pack_seq (unconsumed , result) y = second (append result) (pack_aux (unconsumed , y))
: ^^^^^^^^
: Error: Unbound value pack_aux
: Hint: Did you mean pack_seq?
Test if pack works correctly.
#+BEGIN_SRC ocaml :exports both
pack [1 ; 2 ; 3] (Nest [Atom 9 ; Nest [Atom 8 ; Atom 7]])
#+END_SRC
#+RESULTS:
: Nest [Atom 1, Nest [Atom 2, Atom 3]]
#+BEGIN_SRC ocaml :exports both
pack [1 ; 2 ; 3 ; 4] (Nest [Nest [Atom 8 ; Nest [Atom 8 ; Atom 7]] ; Atom 7])
#+END_SRC
#+RESULTS:
: Nest [Nest [Atom 1, Nest [Atom 2, Atom 3]], Atom 4]
(f)
Zlist corresponds to a lazy nested list
(g)
Force forces the evaluation of all the thunks
#+BEGIN_SRC ocaml
let rec force = function
| ZAtom x -> Atom x
| ZNest l -> Nest (List.map force (l()))
#+END_SRC
#+RESULTS:
: <fun>