Practice questions
Practice questions for COMP 302.
1Writing SML code¶
1.1Lists and ListPairs¶
1.1.1Rewriting standard library functions¶
1.1.1.1Append¶
Write a function app that takes in a tuple of two lists (list * list) and returns one list that has the elements in both lists, in order. You can't use any of the built-in list functions (except List.rev) or the @ operator, obviously. :: is allowed.
fun app ([], other) = other | app (h::t, other) = h::(app (t, other))
Now, write a tail-recursive function app_tl that takes in a tuple of three lists (list * list * list), with the last list being the accumulator, and appends the first two lists together.
fun app_tl ([], other, acc) = (case other of [] => List.rev acc | h::t => app_tl ([], t, h::acc)) | app_tl (h::t, other, acc) = app_tl (t, other, h::acc)
Now, write a function app_cont that uses continuations.
fun app_cont ([], other, cont) = cont other | app_cont (h::t, other, cont) = app_cont (t, other, fn x => cont (h::x)))
1.1.1.2Reverse¶
Write a function rev that takes in a list and returns that list, reversed.
fun rev [] = [] | rev (h::t) = (rev t) @ [h]
Write a function rev_tl that does the same as the above but is tail-recursive. It should take in a tuple of type list * list.
fun rev_tl ([], acc) = acc | rev_tl (h::t, acc) = rev_tl(t, h::acc)
Use structural induction to prove that rev l and rev_tl (l, []) are equivalent. See the induction section for more.
1.1.1.3Map¶
Write a function called map etc
fun map f [] = [] | map f (h::t) = (f h)::(map f t)
Tail-recursive version:
fun map_tl f [] acc = List.rev acc (* reversing is necessary *) | map_tl f (h::t) acc = map_tl f t (f h::acc) (* the above is probably harder to do structural induction on, so here's another *) fun map_tl f [] acc = acc | map_tl f (h::t) acc = map_tl f t (acc @ [f h])
Continuations version:
fun map_cont f [] cont = cont [] | map_cont f (h::t) cont = map_cont f t (fn x => cont ((f h)::x))
Prove that map_tl f l [] and map f l are equivalent using structural induction. See the induction section for more.
1.1.1.4Filter¶
filter
fun filter f [] = [] | filter f (h::t) => if f h then h::t else t
1.1.1.5All¶
all
fun all f [] = true | all f (h::t) = f h andalso all t
1.1.1.6Exists¶
exists
fun exists f [] = false | exists f (h::t) = f h orelse all t
1.1.1.7Tabulate¶
tabulate : (int * (int -> 'a)) -> 'a list
fun tabulate 0 f = [f 0] | tabulate n f = (tabulate (n-1) f) @ [f n]
Tail-recursive version:
fun tabulate 0 f acc = acc | tabulate n f acc = tabulate (n-1) f ((f (n-1))::acc)
Continuations version
fun tabulate 0 f cont = cont [] | tabulate n f cont = tabulate (n-1) f (fn x => cont (x @ [f (n-1)])) (* or *) fun tabulate 0 f cont = List.rev (cont []) | tabulate n f cont = tabulate (n-1) f (fn x => cont ((f (n-1))::x))
1.1.1.8Zip¶
Rewrite ListPair.zip. Depends on length of first list in tuple.
fun zip ([], _) = [] | zip (_, []) = [] | zip (h1::t1, h2::t2) = (h1, h2)::(zip (t1, t2))
1.1.1.9Unzip¶
Rewrite ListPair.unzip
fun unzip [] = ([], []) | unzip ((a, b)::t) = let val (t1, t2) = unzip t in (a::t1, b::t2) end
1.1.2Other list functions¶
1.1.2.1Sum¶
sum
fun sum [] = 0 | sum (h::t) = h + sum t
Now, the tail-recursive version
fun sum_tl ([], acc) = acc | sum_tl (h::t, acc) = sum_tl(t, h + acc)
Now use structural induction to prove that sum l = sum_tl (l, 0). See the induction section for more.
Now write a version, sum_fold using the foldl or foldr function. (Either works).
fun sum_fold l = List.foldl op + 0 l
1.1.2.2Range¶
range n, will return [0, 1, ... n-1]. It will return a list of size n.
Write one without tabulate and one with tabulate (range_tab - the built-in List function).
Also a tail-recursive version (second)
fun range 0 = [] | range 1 = [0] | range n = (range (n-1)) @ [n-1] fun range_tl (0, acc) = acc | range_tl (n, acc) = range_tl (n-1, (n-1)::acc) fun range_tab n = List.tabulate (n, fn x => x)
Now use structural induction to prove that range n = range_tl (n, []). See the induction section for more.
1.1.2.3Sets¶
Given the datatype, implement the following functions:
count(counts the occurrences of an element in an int list)contains(checks if an int is present in a set)make_set(takes in an int list, returns a "set" - i.e. dropping all duplicate elements)unionintersection
type set = int list fun count e (l: int list) = List.foldl (fn (x, i) => if x = e then i + 1 else i) 0 l fun contains e (s:set) = List.exists (fn x => x = e) s fun make_set l = let fun make_set' [] s = s | make_set' (h::t) s = if contains h s then make_set' t s else make_set' t (h::s) in List.rev (make_set' l []) end fun union s1 s2 = s1 @ (List.filter (fn e => not (contains e s1)) s2) fun intersection (s1:set) (s2:set) = List.filter (fn e => contains e s2) s1
1.1.2.4Lists of references¶
Write ref_read which takes in a list of references, returns the contents as a list
fun ref_read l = map ! l
Write ref_apply which takes in a function, and a list of references. Should map the function on to each ref content etc
fun ref_apply f l = map f (ref_read l)
ref_write, supply a list of refs and a list of values. Should return the list of values
fun ref_write refs values = ListPair.map (fn (r, v) => (r := v; v)) (refs, values)
Give it a function and a list of refs, will update each ref cell to have the value after having the function applied to it
fun ref_update f refs = ref_write refs (ref_apply f refs)
1.2Complex numbers¶
We define a custom type for complex numbers:
type complex = int * int
where the first element in the tuple is the real part, and the second element is the imaginary part.
1.2.1Complex conjugates¶
Write a function conjugate that takes in as input a complex number and returns its complex conjugate. For example, if given $4+2i$ (represented as (4, 2)) then it should return $4-2i$ (or (4, ~2)). Its type should be fn : complex -> complex.
fun conjugate ((a, b):complex) = (a, ~b):complex
1.2.2Complex arithmetic¶
Write an add function that takes two complex numbers as input and returns a complex number as output (type: fn : complex * complex -> complex):
fun add ((a, b):complex, (c, d):complex) = (a+c, b+d):complex
Write a multiply function (same type as add). Note that multiplication for complex numbers is defined as follows:
$$(a+bi)(c+di) = (ac-bd) + (bc+ad)i$$
fun multiply ((a, b):complex, (c, d):complex) = (a*c - b * d, b * c + a * d):complex
1.3Matrices and vectors¶
1.3.1Matrix transposition¶
The transpose operation on matrices transforms a matrix such that the rows of the input matrix become the columns of the output matrix. For example:
[[1,2,3],[4,5,6],[7,8,9]]
should become
[[1,4,7],[2,5,8],[3,6,9]]
and
[[1,2,3,4]]
should become
[[1],[2],[3],[4]]
Here, we represent matrices as lists of int lists, with each int list corresponding to a row of the matrix. A valid matrix is one in which the length of each row is greater than 0 and all the rows have the same length. For example, [] would be an invalid matrix, as would [[]], or [[1], [2,3]], while [[1],[2]] would be a valid matrix.
a) Write a function called isValid (int list list -> bool) that takes as input an m x n matrix and returns true if the matrix is valid according to the above specifications and false if it is not. Make use of recursion and/or higher-order list functions (all, map, etc).
b) Write a function called transpose (int list list -> int list list) that takes as input a m x n matrix and returns the transpose of the matrix, if and only if the matrix is valid. If the matrix is not valid, raise an InvalidMatrix exception. You should make use of your isValid function as well as both recursion and higher-order list functions (all, map, etc).
exception InvalidMatrix fun isValid (l: int list list) = (* Write your code here for part a) *) fun transpose (l: int list list) = (* Write your code here for part b) *)
1.3.2Cross-product¶
Given two 3-dimensional vectors, return their cross product. If they're not both 3-d vectors, raise InvalidInput
exception InvalidInput fun cross_product (u, v) = let val [u1, u2, u3] = u val [v1, v2, v3] = v in [u2 * v3 - u3 * v2, u3 * v1 - v3 * u1, u1 * v2 - u2 * v1] end handle Bind => raise InvalidInput
1.3.3Magnitude¶
Use Math.sqrt (real -> real) for this. Takes reals as inputs. Can use no other built-in functions.
fun magnitude v = Math.sqrt(List.foldr (fn (x, y) => x*x + y) 0.0 v)
1.3.4Normalise¶
Given a vector, normalise it so that it is a unit vector.
fun normalise v = let val v_magnitude = magnitude v in map (fn x => x / v_magnitude) v
1.4Binary trees¶
1.4.1Defining the datatype¶
Define a datatype tree for a binary tree that can hold any type of element (as long as it's comparable - so equality type?) as a value. Either it's Empty or it's a Node with a left subtree and a right subtree and a value.
datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree
1.4.2Writing functions¶
Write a size function. Note that the size of an empty tree is 0. Only those that have values are counted etc. Add up the left and right subtrees
fun size Empty = 0 | size Node(_, L, R) = 1 + size L + size R
Write a mirror function which flips the left and right subtrees for EVERY subtree.
fun mirror Empty = Empty | mirror (Node(v, L, R)) = Node(v, mirror R, mirror L)
Prove that for all trees t, size t = size (mirror t). See the induction section for more details.
Write a retrieve function, given 'a * tree. Should return the Node containing that value. If it's not there, raise an exception, NotFound.
exception NotFound fun retrieve (_, Empty) = raise NotFound | retrieve (v, t as Node (v', L, R)) = if v = v' then t else if v < v' then retrieve (v, L) else retrieve (v, R)
Write an insert function
(* if it's already there, we don't need to do anything * except return the tree; if it's not, we have to add it *) fun insert (v, t) = retrieve (v, t) handle NotFound => (case t of Empty => Node(v, Empty, Empty) | Node(v', L, R) => if v < v' then Node(v', insert (v, L), R) else Node(v', L, insert (v, R)) )
Write a function that finds all the elements that satisfy a given predicate. (Based on a solved exercise during the last two lectures.) Do it three ways:
- Standard recursion
- Exceptions
- Continuations
(* The standard recursion way *) fun findAll f Empty = [] | findAll f (Node(v, L, R)) = let val tail = (findAll f L) @ (findAll f R) in if f v then v::tail else tail end (* Using exceptions - have to use int list because exceptions are not * polymorphic for some reason. This method also seems to preserve order *) exception FoundAll of int list fun findAllEx' f Empty = raise FoundAll [] | findAllEx' f (Node(v, L, R)) = let val this_one = List.filter f [v] in (findAllEx' f L) handle FoundAll left_list => ((findAllEx' f R) handle FoundAll right_list => raise FoundAll (left_list @ this_one @ right_list)) end fun findAllEx f t = findAllEx' f t handle FoundAll l => l (* Using continuations *) fun findAllCont' f Empty cont = cont [] | findAllCont' f (Node(v, L, R)) cont = let val this_one = List.filter f [v] in findAllCont' f L (fn L1 => (findAllCont' f R (fn R1 => cont (L1 @ this_one @ R1)))) end fun findAllCont f t = findAllCont f t (fn x => x)
1.5Geometry¶
1.5.1Point of intersection¶
Write a function that returns the x- and y-coordinates of the intersection point of two lines in the form ax+b (each represented as a tuple, with the slope being the first element, and the y-intercept being the second - all ints). Should return a tuple of reals (use Real.fromInt to convert from int to real). If they don't intersect, raise the ParallelLines error.
exception ParallelLines fun intersect ((a1, b1), (a2, b2)) = if a1 = a2 then raise ParallelLines else let val x = (Real.fromInt (b2-b1)) / (Real.fromInt (a1-a2)) in (x, (Real.fromInt a1) * x + (Real.fromInt b1)) end
1.6Strings¶
1.6.1On-the-fly string function generation¶
For the following section, you may make use of any String functions - for example, String.implode (type: fn : char list -> string), String.map (type: (char -> char) -> string -> string) and String.translate (type: (char -> string) -> string -> string) may be useful. You can also use any functions in the List signature.
Write a function called repeat of type fn : char -> int -> string that takes as input a character and returns a function that will, when called with an integer n, will return a string of length n consisting of only that character. For example, if I called repeat with the argument #"c", then called the resulting function with the argument 10, the result would be "cccccccccc".
fun repeat c = fn n => String.implode (List.tabulate (n, (fn x => c))) (* or ... *) fun repeat c n = String.implode (List.tabulate (n, (fn x => c)))
Now, use the function repeat to write a function double_chars that takes as input a string and returns a string with every character doubled. So lol would become llooll.
fun double_chars s = List.foldr (fn (c, str) => (repeat c 2) ^ str) "" (String.explode s) (* or ... (and this is probably nicer) *) fun double_chars s = String.translate (fn c => (repeat c) 2) s
Modify the above to return a function that will multiply the number of chars by n - multiply_chars
fun multiply_chars s = fn n => (List.foldr (fn (c, str) => (repeat c n) ^ str) "" (String.explode s)) (* or ... *) fun multiply_chars s n = String.translate (fn c => (repeat c) n) s
1.6.2Caesar cipher¶
Write a caesar_encode function that takes as input a string and an int where the int is the number of places to shift right by.
Make use of the function String.translate (type: fn : (char -> string) -> string -> string). There is a function called chr (type: int -> char) and a function called ord (type: char -> int) in the standard library - both should be helpful.
Also write a function caesar_decode that calls caesar_encode. Calling caesar_decode (caesar_encode "lol" n) n should return "lol" (replace n by any integer).
fun caesar_encode s n = String.translate (fn c => str (chr ((ord c) + n))) s (* or ... (much nicer) *) fun caesar_encode s n = String.map (fn c => chr ((ord c) + n)) s fun caesar_decode s n = caesar_encode s (~n)
1.6.3Counting characters¶
Write a function count_spaces that counts the number of whitespace characters in a string.
fun count_spaces s = List.foldl (fn (c, count) => if c = #" " then count + 1 else count) 0 (explode s)
Now, write a function count_char that returns a function that counts the occurrences of character c in the string. For example, count_char #"c" should return a function that, when passed a string, will return the number of c's in the string.
fun count_spaces x s = List.foldl (fn (c, count) => if c = x then count + 1 else count) 0 (explode s)
1.7Project Euler problems in SML¶
Just for fun etc
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
(Problem 5)
exception FoundAnswer of int fun divisibleBy n x = x mod n = 0 (* returns true if x is divisible by n *) fun divisibleByAllUpTo 1 x = true | divisibleByAllUpTo n x = divisibleBy n x andalso divisibleByAllUpTo (n-1) x fun solve x = if divisibleByAllUpTo 20 x then raise FoundAnswer x else solve (x + 1) solve 1 handle FoundAnswer n => print (Int.toString n)
Answer: 232792560, took about 10 seconds on my machine.
What is the first term in the Fibonacci sequence to contain 1000 digits?
(Problem 25)
exception FoundAnswer of int fun getNumDigits x = if x div 10 < 1 then 1 else 1 + (getNumDigits (x div 10)) (* probably really inefficient but whatever *) fun solve this_fib prev_fib = let val new_fib = this_fib + prev_fib in if getNumDigits new_fib > 99 then raise FoundAnswer new_fib else solve (this_fib + prev_fib) this_fib end solve 1 1 handle FoundAnswer answer => print (Int.toString answer)
... which would theoretically work, but running it produces an overflow error. I suppose there has to be a smarter way of doing this. (It does work for digits up to 9 though!)
2Proof by induction¶
2.1Tail-recursive induction¶
2.1.1Reverse induction¶
Recall the reverse functions:
fun rev [] = [] | rev (h::t) = (rev t) @ [h] fun rev_tl ([], acc) = acc | rev_tl (h::t, acc) = rev_tl(t, h::acc)
Prove that rev l = rev_tl (l, []).
First, we need to prove the following lemma: (rev l) @ acc = rev_tl (l, acc) for all lists l and acc. We do our induction on l. Base case:
(rev []) @ acc = [] @ acc (* by program *)
= acc (* by the properties of the append operator and its behaviour with empty lists *)
rev_tl ([], acc) = acc (* by program *)
So the base case checks out. Let us assume that (rev t) @ acc = rev_tl (t, acc) (the induction hypothesis). Our induction step is to prove that (rev (h::t)) @ acc = rev_tl (h::t, acc) also holds:
= (rev t) @ ([h] @ acc) (* by the associativity of the @ operator *)
= (rev t) @ (h::acc) (* by the equivalence of x::t and [x] @ t *)
rev_tl (h::t, acc) = rev_tl (t, h::acc) (* by program *)
By the induction hypothesis using h::acc for acc, we see that these are equal, and so the lemma is true.
Now, we return to the main theorem. Using the lemma, we can let the accumulator be [], in which case we have (rev l) @ [] = rev l = rev_tl (l, []) QED.
2.1.2Sum induction¶
Recall the function definitions:
fun sum [] = 0 | sum (h::t) = h + sum t fun sum_tl ([], acc) = acc | sum_tl (h::t, acc) = sum_tl(t, h + acc)
We need to show that sum l = sum_tl (l, 0).
Lemma: show that sum l + acc = sum_tl (l, acc) for all lists l and all accumulators acc. Our induction is on l.
Base case: sum [] = 0 by the function definition, and so 0 + acc = acc by the properties of addition. Also, sum_tl ([], acc) = acc by the function definition, so the functions produce the same result in the base case.
IH: Assume that sum t + acc = sum_tl (t, acc). Then we must show that sum (h::t) + acc = sum_tl (h::t, acc). From the function definition forsum, we knowsum (h::t) = h + sum tand sosum (h::t) + acc = (h + sum t) + acc(by substitution). However, we can rewrite this assum t + h + acc = sum t + (h + acc)` by the commutativity and associativity of addition.
Now, from the function definition for sum_tl, we know sum_tl (h::t, acc) = sum_tl (t, h + acc). If we substitute acc in the IH by h + acc, we see that the two are equal. Consequently, we prove the lemma.
To prove the main theorem, let acc = 0 and we have that sum l + 0 = sum l = sum_tl (l, 0) and we're done.
2.1.3Range induction¶
Recall the range functions:
fun range 0 = [] | range 1 = [0] | range n = (range (n-1)) @ [n-1] fun range_tl (0, acc) = acc | range_tl (n, acc) = range_tl (n-1, (n-1)::acc)
We need to prove that range n = range_tl (n, []).
To do this, we first need to prove a lemma: (range n) @ acc = range_tl (n, acc) for all integers n and accumulators acc. Our induction is on n.
Base case: n = 0:
(range 0) @ acc = ([]) @ acc (* by program *)
= acc (* when you append an empty list to another in SML, the resulting list is equivalent to the other list*)
range_tl (0, acc) = acc (* by program *)
The base case checks out. Let's move on to the induction hypothesis. Assume that (range (n-1)) @ acc = range_tl (n-1, acc). The induction step is to check that this holds for n as well.
(range n) @ acc = ((range (n-1)) @ [n-1]) @ acc (* by program *)
= (range (n-1)) @ ([n-1] @ acc) (* by associativity of @ *)
range_tl (n, acc) = range_tl (n-1, (n-1)::acc) (* by program *)
= range_tl (n-1, [n-1] @ acc) (* by the equivalence of [x] @ acc and x::acc in SML *)
By the induction hypothesis using [n-1] @ acc for acc, we know that these are equal, and so the lemma is proved.
To prove the main theorem, we simply use [] for acc: range n @ [] = range n = range_tl (n, []) which shows that they are equivalent.
2.1.4Map induction¶
Recall the map functions:
fun map f [] = [] | map f (h::t) = (f h)::(map f t) fun map_tl f [] acc = acc | map_tl f (h::t) acc = map_tl f t (acc @ [f h])
Prove that map f l = map_tl f l [].
We first prove the lemma acc @ (map f l) = map_tl f l acc for all lists l and acc by doing the induction on l. Base case:
acc @ (map f []) = acc @ [] (* by program *)
= acc (* by the properties of @ when appending something with an empty list *)
map_tl f [] acc = acc (* by program *)
The base case checks out. For our induction hypothesis, we use acc @ (map f t) = map_tl f t acc. Now we have the induction step, h::t:
= acc @ ([f h] @ (map f t)) (* by the equivalence of x::y and [x] @ y *)
= (acc @ [f h]) @ (map f t) (* by the associativity of the @ operator *)
map_tl f (h::t) acc = map_tl f t (acc @ [f h])
By the induction hypothesis, using acc @ [f h] for acc, we know that these are equal, and so the lemma is true.
To prove the main theorem, let acc = []: [] @ (map f l) = map f l = map_tl f l []
2.2Binary tree induction¶
Recall the mirror and size functions for a binary tree:
fun size Empty = 0 | size Node(_, L, R) = 1 + size L + size R fun mirror Empty = Empty | mirror (Node(v, L, R)) = Node(v, mirror R, mirror L)
Prove that size t = size (mirror t). We can do this using structural induction on t. Base case, when t = Empty:
size Empty = 0 (* by program *)
size (mirror Empty) = size (Empty) (* by program *)
= 0 (* by first line *)
The base case checks out. Our induction hypothesis is that size L = size (mirror L) and size R = size (mirror R) (i.e. the theorem holds for the subtrees). We need to prove that size (Node(v, L, R)) = size (mirror (Node(v, L, R))) - the induction step:
size (Node(v, L, R)) = 1 + size L + size R (* by program *)
size (mirror (Node(v, L, R))) = size (Node(v, mirror R, mirror L)) (* by program *)
= 1 + size (mirror R) + size (mirror L) (* by program - see first line *)
= 1 + size (mirror L) + size (mirror R) (* by commutativity of addition *)
= 1 + size L + size R (* by IH, substituting for "size (mirror L)" and "size (mirror R)" *)
It follows by structural induction that size t = size (mirror t) for any tree t. QED
3Environment diagrams¶
Draw an environment diagram for the following piece of code:
let val a = "lol" val b = "mudkip" val (a, b) = (b, a) val c = a val d = (fn (a, b, c) => a ^ a ^ c) in d (a, b, c) end
What will the final result be?
Here's a crappy environment diagram for it:
---------
|a|"lol"| <-
--------- |
|
------------
|b|"mudkip"| <-
------------ |
|
---------
|a,b|b,a| <-
--------- |
|
-----
|c|a| <- -------------
----- | |a,b,c|a,b,c|
| -------------
----- |
|d| | <-------------|
-----
|
v
-----------------
|a,b,c|a ^ a ^ c|
-----------------
"mudkip" ^ "mudkip" ^ "mudkip"
The final result is "mudkipmudkipmudkip". No lols, not even one.
(I wasn't really sure how to draw the tuple case, so I just guessed.)
3.1Environment diagrams with references¶
See the lecture notes.
4Theoretical aspects¶
4.1Free and bound variables¶
4.2Type inference¶
4.3Subtyping¶
5Miscellaneous¶
foldr or foldl? If the left should be evaluated first, then foldl; else, foldr