:PROPERTIES: :ID: 84c4452d-e37f-4029-8739-e063bc22bcf4 :mtime: 20231124170129 20231110164438 20231109171655 20231109120736 20231108173854 20231108063537 20231108053343 20231108012643 20231101015829 20231031094921 :ctime: 20231031094916 :END: #+title: foundations of CS supervision 4 #+filetags: :public:project: * Questions 2010 Paper 1 Question 1 2010 Paper 1 Question 2 2016 Paper 1 Question 2 2020 Paper 1 Question 1 * 2010 Paper 1 Question 1 ** Question Foundations of Computer Science (a) Give an ML datatype declaration suitable for representing lazy lists, possibly of infinite length. [2 marks] (b) Code the ML function interleave, which takes two lazy lists and generates a lazy list containing each of their elements. [2 marks] (c) Code an ML function that applies a given function to every element of a lazy list, returning a lazy list of the results (analogously to the function map). [3 marks] (d ) Code the ML function iterates which, given a function f and some value x, generates a lazy list containing all the values of the form f n(x) (that is, f (· · · f (x) · · ·) with n applications of f ) for $n \ge 0$. [3 marks] (e) Code the ML function iterates2 which, given functions f and g and values x and y, generates a lazy list containing all the values of the form (f m(x), gn(y)) for $m, n \ge 0$. [10 marks] All ML code must be explained clearly and should be free of needless complexity. 1 ** Solution (a) A lazy list uses unit functions to delay the evaluation of the tail. #+BEGIN_SRC ocaml type 'a llist = | Nil | Cons of 'a * (unit -> 'a llist) #+END_SRC #+RESULTS: : type 'a llist = Nil | Cons of 'a * (unit -> 'a llist) (b) Interleave weaves two lazy lists togther. #+BEGIN_SRC ocaml let rec interleave = function | Nil , x -> x | x , Nil -> x | Cons (a , b) , Cons (c , d) -> Cons (a , fun _ -> Cons (c , fun _ -> interleave (b () , d ()))) #+END_SRC #+RESULTS: : <fun> (c) Map applies f to every element of a lazy list. #+BEGIN_SRC ocaml let rec map f = function | Nil -> Nil | Cons (a , b) -> Cons (f a , fun _ -> map f (b ())) #+END_SRC #+RESULTS: : <fun> (d) Iterates creates an infinite lazy list of x , f x , f (f x) , f (f (f x)) , .... #+BEGIN_SRC ocaml let rec iterates f x = Cons (x , fun _ -> iterates f (f x)) #+END_SRC #+RESULTS: : <fun> (e) Create all combinates of $f^n$ and $g^m$. This solution includes some elements multiple times in the list, but the instructions just specified that each pair had to be included at least once, so I think this flaw is fine. #+BEGIN_SRC ocaml let first f (a , b) = (f a , b) let second f (a , b) = ( a , f b) let rec iterates2 f g x y = Cons((x , y) , fun _ -> interleave ((map (first f) (iterates2 f g x y)) , (map (second g) (iterates2 f g x y))) ) #+END_SRC #+RESULTS: : <fun> A simple utility function to inspect lazy lists. #+BEGIN_SRC ocaml let rec view n = function | Nil -> [] | Cons (a , b) -> if n <= 0 then [] else (a :: (view (n - 1) (b ()))) #+END_SRC #+RESULTS: : <fun> Count up infinitly from a starting value. #+BEGIN_SRC ocaml let rec from n = Cons(n , fun _ -> from (n + 1)) #+END_SRC #+RESULTS: : <fun> Test if the map function works. #+BEGIN_SRC ocaml :exports both view 10 (map succ (from 0)) #+END_SRC #+RESULTS: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Test is interleave works. #+BEGIN_SRC ocaml :exports both view 10 (interleave ((from 0 ) ,(map succ (from 10)))) #+END_SRC #+RESULTS: | 0 | 11 | 1 | 12 | 2 | 13 | 3 | 14 | 4 | 15 | Test if iterates works. #+BEGIN_SRC ocaml :exports both view 10 (iterates succ 0) #+END_SRC #+RESULTS: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Test if iterates2 works. #+BEGIN_SRC ocaml :exports both view 10 (iterates2 succ succ 0 0) #+END_SRC #+RESULTS: | 0 | 0 | | 1 | 0 | | 0 | 1 | | 2 | 0 | | 1 | 1 | | 1 | 1 | | 0 | 2 | | 3 | 0 | | 2 | 1 | | 2 | 1 | * 2010 Paper 1 Question 2 ** Question (a) Write brief notes on the function defined below: #+BEGIN_SRC ocaml let rec foldl f e = function | [] -> e | x :: xs -> foldl f (f e x) xs #+END_SRC #+RESULTS: : <fun> Illustrate your answer by describing the computations performed by the following two functions: #+BEGIN_SRC ocaml let f = foldl (foldl (fun a b -> a * b) ) 1 #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both f [[3 ; 4] ; [5 ]] #+END_SRC #+RESULTS: : 60 #+BEGIN_SRC ocaml let g p = foldl (fun (x,y) z -> if p z then (z::x,y) else (x,z::y)) ([],[]) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both let isEven x = (x mod 2 = 0);; g isEven [ 1 ; 2 ; 3 ;4 ; 5 ; 6 ; 7 ; 8 ; 9] #+END_SRC #+RESULTS: | 8 | 6 | 4 | 2 | | | 9 | 7 | 5 | 3 | 1 | [4 marks] (b) Selection sort is a sorting algorithm that works by repeatedly identifying and setting aside the smallest (or largest) item to be sorted. Implement selection sort in ML and describe the efficiency of your solution using O-notation. [4 marks] (c) Code an ML function to generate a multiplication table in the form of a list of lists of integers. For example, given the argument 3 it should return [[1, 2, 3], [2, 4, 6], [3, 6, 9]]. [6 marks] (d ) Modify your solution to part (c) in order to generate a three-dimensional table containing values xijk computed by calling a supplied 3-argument curried function f . For example, given the argument 2 it should return [[[x111,x112], [x121,x122]], [[x211,x212], [x221,x222]]]. [6 marks] All ML code must be explained clearly and should be free of needless complexity. 1 ** Solution (a) foldl is the unique catamorphism from the initial algebra of the list datatype. The first function f takes in a list of lists of integers, and multiplies all the integers. The second function g takes a predicate p and a list, and parititions the list into those elements that satisfy p and those elements which do not. (b) I used paritition_minimum to create selection_sort. #+BEGIN_SRC ocaml exception EmptyList let min x y = if x < y then x else y let max x y = if x < y then y else x let rec partition_minimum = function | [] -> raise EmptyList | x :: xs -> List.fold_left (fun (current_min , rest) elem -> (min current_min elem , max current_min elem :: rest)) (x , []) xs let rec selection_sort xs = if xs = [] then [] else let (y , ys) = partition_minimum xs in y :: (selection_sort ys) #+END_SRC #+RESULTS: : <fun> Test if partition_minimum works correctly. #+begin_src ocaml :exports both partition_minimum [1 ; 2] #+end_src #+RESULTS: | 1 | (2) | Test if selection_sort works correctly. #+begin_src ocaml :exports both selection_sort [ 4 ; 2 ; 6 ; 1 ; 6] #+end_src #+RESULTS: | 1 | 2 | 4 | 6 | 6 | Efficiency of selection sort is $O(n^2)$. (c) I used range to create multiplication_table. #+BEGIN_SRC ocaml let rec range n = if n = 0 then [] else range (n - 1) @ [n] let rec row length step = if length = 0 then [] else step :: List.map ((+) step) (row (length - 1) step) let multiplication_table n = List.map (row n) (range n) #+END_SRC #+RESULTS: : <fun> Test if multiplication_table works correctly. #+BEGIN_SRC ocaml :exports both multiplication_table 5 #+END_SRC #+RESULTS: | 1 | 2 | 3 | 4 | 5 | | 2 | 4 | 6 | 8 | 10 | | 3 | 6 | 9 | 12 | 15 | | 4 | 8 | 12 | 16 | 20 | | 5 | 10 | 15 | 20 | 25 | (d) This function is a bit complicated, so I will not explain how it works. #+BEGIN_SRC ocaml let cube (f : int -> int -> int -> 'a) (n : int) : 'a list list list = List.map (fun row -> List.map (fun (a , b) -> List.map (fun x ->f x a b ) (range n) ) row ) (List.map (fun x -> List.map (fun y -> (x , y)) (range n)) (range n)) #+END_SRC #+RESULTS: : <fun> Test if cube works correctly. #+BEGIN_SRC ocaml :exports both cube (fun x a b -> (x , a ,b)) 2 #+END_SRC #+RESULTS: | ((1 1 1) (2 1 1)) | ((1 1 2) (2 1 2)) | | ((1 2 1) (2 2 1)) | ((1 2 2) (2 2 2)) | * 2016 Paper 1 Question 2 ** Question (a) A prime number sieve is an algorithm for finding all prime numbers up to a given limit n. The algorithm maintains a list, which initially holds the integers from 2 to n. The following step is then repeated: remove the head of this list, which will be a prime number, and remove all its multiples from the list. Write code for the algorithm above as an ML function of type int -> int list. [4 marks] (b) Consider the problem of eliminating all duplicates from a list of strings. Write code for a function of type string list -> string list such that the output contains the same elements as the input, possibly reordered, but where every element occurs exactly once. The worst-case performance must be better than quadratic in the length of the list. [6 marks] (c) Consider the task of determining whether a given word (a string) can be expressed by joining together various chunks (non-empty strings). If the chunks are abra, cad and hal, then the word abracadabra can be expressed as abra|cad|abra. Note that if the available chunks are ab, bra, cad and abra, then the first two are no good for expressing abracadabra, and yet a solution can be found using cad and abra. The chunks can be used any number of times and in any order. Write code for a function that takes a list of chunks along with a word, and returns a list of chunks that yield the word when concatenated. For the examples above, the result should be ["abra", "cad", "abra"]. Exception Fail should be raised if no solution exists. [10 marks] Note: You are given a function delPrefix for removing an initial part of a string. For example, delPrefix ("abra", "abracadabra") returns "cadabra", but delPrefix ("bra", "abracadabra") raises exception Fail. All ML code must be explained clearly and should be free of needless complexity. Well-known utility functions may be assumed to be available. ** Solution (a) sieve can be expressed concisely using a fold_right. We simply remove all multiples of a from the accumulator for each a. #+BEGIN_SRC ocaml let remove_multiples p = List.filter (fun q -> q mod p != 0) let rec range a b = if b < a then [] else a :: (range (a + 1) b) let sieve n = List.fold_right (fun a acc -> a :: (remove_multiples a acc)) n [] let prime_sieve n = sieve (range 2 n) #+END_SRC #+RESULTS: : <fun> Test if prime_sieve works correctly. #+BEGIN_SRC ocaml :exports both prime_sieve 100 #+END_SRC #+RESULTS: | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 | 97 | (b) To make remove_dups faster, we sort the list first, giving us a runtime complexity of $O(n \log n)$. #+BEGIN_SRC ocaml let rec remove_sorted = function | [] -> [] | [x] -> [x] | a :: b :: cs -> (if a = b then [] else [a]) @ remove_sorted (b :: cs) let remove_dups (s : string list) : string list = remove_sorted (List.sort compare s) #+END_SRC #+RESULTS: : <fun> Test if remove_dups works correctly. #+BEGIN_SRC ocaml :exports both remove_dups ["a" ; "b" ; "a" ; "c" ; "d" ; "b" ; "c" ; "x" ; "d"] #+END_SRC #+RESULTS: | a | b | c | d | x | (c) I coded delPrefix myself, just for testing purposes. #+BEGIN_SRC ocaml exception Fail let delPrefix prefix str = if String.starts_with prefix str then String.sub str (String.length prefix) (String.length str - String.length prefix) else raise Fail #+END_SRC #+RESULTS: : <fun> Check if delPrefix works correctly. #+BEGIN_SRC ocaml :exports both delPrefix "abra" "abracadabra" #+END_SRC #+RESULTS: : cadabra Check if delPrefix works correctly. #+BEGIN_SRC ocaml :exports both delPrefix "abra" "abra" #+END_SRC #+RESULTS: We use concat_map (which is the monadic bind for lists) in order to create from_chunks. #+BEGIN_SRC ocaml let rec from_chunks (s : string) (chunks : string list) : string list list = if s = "" then [[]] else List.concat_map (fun chunk -> try List.map (List.cons chunk) (from_chunks (delPrefix chunk s) chunks) with Fail -> []) chunks #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let rec from_chunks_backtrack (s : string) = function | [] -> if s = "" then [] else raise Fail | f :: t -> try from_chunks_backtrack (delPrefix s f) (f :: t) with Fail -> from_chunks_backtrack s t #+END_SRC #+RESULTS: : <fun> Test if from_chunks works correctly. #+BEGIN_SRC ocaml from_chunks "abracadabra" ["ab" ; "bra" ; "cad" ; "abra"] #+END_SRC #+RESULTS: | abra | cad | abra | #+BEGIN_SRC ocaml from_chunks_backtrack "abracadabra" ["ab" ; "bra" ; "cad" ; "abra"] #+END_SRC #+RESULTS: : Exception: Fail. * 2020 Paper 1 Question 1 ** Question Foundations of Computer Science (avsm2) You need to write OCaml code to help a local park ranger count the different types of trees present in a region of Cambridgeshire woodland. (a) Define an OCaml type tree that can distinguish between an oak, birch or maple tree, and also any other species with an arbitrary string name. [1 mark] (b) Define two OCaml values with the following signatures: (i) val describe : tree -> string that accepts a tree parameter and returns a human-readable string. (ii) val identify : string -> tree that accepts a lowercase string parameter and returns a tree. Explain briefly how the OCaml compiler can statically check if you have handled all the input possibilities for the input parameters to describe and identify. [4 marks] (c) Define a type stree that only distinguishes between three species oak, birch or maple and no others. Implement functions for the following signatures with similar functionality to the earlier identify function: val identify exn : string -> stree val identify opt : string -> stree option Briefly discuss the tradeoffs between your two approaches. [5 marks] (d ) You now need to implement a simple simulator before starting real surveys. Trees will occur in the following fixed infinite sequence: oak, birch, oak, maple, maple, and then repeat from the beginning. (i) Define a function val spotter : unit -> stree that will return the sequence of trees when called multiple times. [5 marks] (ii) Define a purely functional alternative spotter that calculates the next stree in sequence, using only the input arguments to the function to calculate the return value. Write down an example application of this function with the input arguments and the expected output result.(Hint: you may need to pass in the complete sequence as one of the arguments.) [5 marks] 1 ** Solution (a) Define an inductive datatype. #+BEGIN_SRC ocaml type tree = | Oak | Birch | Maple | Other of string #+END_SRC #+RESULTS: : type tree = Oak | Birch | Maple | Other of string (a.i) Use pattern matching on the tree type. #+BEGIN_SRC ocaml let describe = function | Oak -> "Oak" | Birch -> "Birch" | Maple -> "Maple" | Other s -> s #+END_SRC #+RESULTS: : <fun> (a.ii) Use pattern matching on strings #+BEGIN_SRC ocaml let identify = function | "Oak" -> Oak | "Birch" -> Birch | "Maple" -> Maple | s -> Other s #+END_SRC #+RESULTS: : <fun> It is quite interesting how the ocaml compiler can check the exhaustiveness of a pattern match, especially for infinite types such as int or string. Here is how I think the ocaml compiler works: If the datatype is a finite datatype, it is easy to check all possibilites. If the datatype is an infinite datatype, ocaml checks if there is one catchall case at the end. (c) #+BEGIN_SRC ocaml exception Tree let identify_exn = function | "Oak" -> Oak | "Birch" -> Birch | "Maple" -> Maple | s -> raise Tree #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml let identify_opt = function | "Oak" -> Some Oak | "Birch" -> Some Birch | "Maple" -> Some Maple | s -> None #+END_SRC #+RESULTS: : <fun> I would say that indentify_opt is the better function because in ocaml, exceptions are sneakily hidden away in the type signature. You cannot tell if a function is safe or unsafe merely from looking at the type signature. (d.i) spotter uses some hidden internatl state in order to track the current tree. #+BEGIN_SRC ocaml let spotter = let c = ref 0 in fun () -> begin c := succ !c ; List.nth [Oak ; Birch ; Oak ; Maple ; Maple] (!c mod 5) end #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :export both spotter () #+END_SRC #+RESULTS: : Birch fun_spotter needs an additional input, which is the current state in order to remember which state to go to next. #+BEGIN_SRC ocaml let fun_spotter = function | Birch , _ -> Oak , 1 | Oak , 0 -> Birch , 0 | Maple , 0 -> Maple , 1 | Oak , _ -> Maple , 0 | Maple , _ -> Oak , 0 #+END_SRC #+RESULTS: : <fun> Simply test if fun_spotter works correctly. #+BEGIN_SRC ocaml :exports both let rec rep n f x = if n = 0 then [] else x :: rep (n - 1) f (f x) ;; rep 10 fun_spotter (Oak , 0) #+END_SRC #+RESULTS: | Oak | 0 | | Birch | 0 | | Oak | 1 | | Maple | 0 | | Maple | 1 | | Oak | 0 | | Birch | 0 | | Oak | 1 | | Maple | 0 | | Maple | 1 | * 1997 Paper 1 Question 5. ** Question Noughts and Crosses is a game played by two players (O and X) on a board with nine positions numbered as follows: 1 2 3 4 5 6 7 8 9 The players place their marks (O and X) in unoccupied positions on the board until the game is complete. A completed game is when either (a) there is a straight line of three Xs giving a win for X, or (b) there is a straight line of three Os giving a win for O, or (c) all nine positions are occupied, in which case the game is drawn. O is the first player to move. It is required to construct an OCaml structure representing the tree of all possible games. Each node of the tree should represent a reachable board state, with the root being the empty board, and the leaf nodes corresponding to won, lost or drawn games. (a) Define the OCaml variant type tree that you would use to represent this game tree. [3 marks] (b) Define the function mktree : unit -> tree to construct the complete game tree, explaining carefully how it works. There is no need for your implementation to be efficient in either space or time. [10 marks] (c) Briefly discuss ways in which your implementation of mktree could be made more efficient. [4 marks] (d) Define a function winner is O : tree -> int which when applied to the complete tree will yield the number of distinct games in which O wins. [3 marks] 1 ** Solution (a) Here are the types that I used to model the game #+BEGIN_SRC ocaml type player = X | O type endstate = | Over of player | Draw type cell = Gone of player | Empty type boardstate = cell list type tree = Leaf of endstate | Board of boardstate * (tree list) #+END_SRC #+RESULTS: : type player = X | O : type endstate = Over of player | Draw : type cell = Gone of player | Empty : type boardstate = cell list : type tree = Leaf of endstate | Board of boardstate * tree list (b) The beginning state of the board when the game starts #+BEGIN_SRC ocaml let openingState = [ Empty ; Empty ; Empty ; Empty ; Empty ; Empty ; Empty ; Empty ; Empty ] #+END_SRC #+RESULTS: | Empty | Empty | Empty | Empty | Empty | Empty | Empty | Empty | Empty | A list of all ways a player could win with 3 in a row. #+BEGIN_SRC ocaml let rows = [ [0 ; 1 ; 2] ; [3 ; 4 ; 5] ; [6 ; 7 ; 8] ; [0 ; 3 ; 6] ; [1 ; 4 ; 7] ; [2 ; 5 ; 8] ; [0 ; 4 ; 8] ; [2 ; 4 ; 6] ; ] #+END_SRC #+RESULTS: | 0 | 1 | 2 | | 3 | 4 | 5 | | 6 | 7 | 8 | | 0 | 3 | 6 | | 1 | 4 | 7 | | 2 | 5 | 8 | | 0 | 4 | 8 | | 2 | 4 | 6 | A list of all indices of cells in the board. #+BEGIN_SRC ocaml let range = [0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8] #+END_SRC #+RESULTS: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | A simple utility function which sets the ith index of a list. #+BEGIN_SRC ocaml let set_elem l i x = List.mapi (fun j el -> (if (i = j) then x else el)) l #+END_SRC #+RESULTS: : <fun> join 2 boardstates together. #+BEGIN_SRC ocaml let joinBoards (b : boardstate) (p : player) (place : int) : boardstate option = match List.nth b place with | Gone _ -> None | Empty -> Some (set_elem b place (Gone p)) #+END_SRC #+RESULTS: : <fun> Get a list of the next boards reachable from this boardstate. #+BEGIN_SRC ocaml let nextBoards (b : boardstate) (p : player) : boardstate list = List.filter_map (joinBoards b p) range #+END_SRC #+RESULTS: : <fun> Check if a row will result in a win. #+BEGIN_SRC ocaml let isRowWin = function | [Gone X ; Gone X ; Gone X] -> Some X | [Gone O ; Gone O ; Gone O] -> Some O | _ -> None #+END_SRC #+RESULTS: : <fun> Check if the game is in a draw. #+BEGIN_SRC ocaml let isDraw (b : boardstate) : bool = List.for_all (fun cell -> match cell with | Empty -> false | Gone _ -> true) b #+END_SRC #+RESULTS: : <fun> Calculate the endstate (if the game is over) for a given boardstate. #+BEGIN_SRC ocaml let endState (b : boardstate) : endstate option = if isDraw b then Some Draw else let possibleWins : cell list list = (List.map (fun win -> List.map (fun r -> List.nth b r) win) rows) in Option.map (fun x -> Over x) (List.find_map isRowWin possibleWins) (* let winstate (b : board) = List.map (fun row -> ) rows *) #+END_SRC #+RESULTS: : <fun> Get the next player from the current player. #+BEGIN_SRC ocaml let nextPlayer : player -> player = function | X -> O | O -> X #+END_SRC #+RESULTS: : <fun> Recursively find all states #+BEGIN_SRC ocaml let rec possibleStates (b : boardstate) (p : player ) : tree list = let e = endState b in match e with | None -> let boards = nextBoards b p in List.concat_map (fun board -> possibleStates (board) (nextPlayer p)) boards | Some ends -> [Leaf ends] #+END_SRC #+RESULTS: : <fun> Generate the large tree. #+BEGIN_SRC ocaml let mktree (u : unit) : tree = Board (openingState , possibleStates openingState X ) #+END_SRC #+RESULTS: : <fun> (c) To make this more efficient, I would implement lazy generation of the tree, i.e. I would only generate the parts of the tree that we need to generate. It is very unlikely that a person needs to know the entire game tree of tic tac toe, so it would be more economical to only generate the tree upon request. (d) #+BEGIN_SRC ocaml let sum = List.fold_left (fun a b -> a + b) 0 let rec count_O_wins : tree -> int = function | Leaf (Over O) -> 1 | Leaf _ -> 0 | Board (_ , ts) -> sum (List.map count_O_wins ts) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml count_O_wins (mktree ()) #+END_SRC #+RESULTS: : Stack overflow during evaluation (looping recursion?).