Final review

The final examination will take place on Tuesday, April 24, at 9am, in the arts building (next to Leacock). The room number depends on your last name - see the schedule for details.

The exam will consist of 10 long- or short-answer questions and will last three hours. All the course material except dependent types and OOP in Java is examinable. For a list of the main topics, see the table of contents below¹.

This page was created to provide a brief overview of all the examinable material covered this year. For other, complementary resources that may be of help in preparing for the final, see the following pages:

• Student-written lecture notes
• Student-written practice questions - under construction
• A student-written crib sheet - under construction
• The official course website, which contains links to Professor Pientka's own notes

1Datatypes¶

2Recursive functions¶

3Pattern matching¶

You can pattern match on tuples, constructors, lists, records - anything, really:

datatype tree = Leaf | Node of int * tree * tree

val [a, b, c] = [1,2,3] (* list *)
val h::t = [1,2,3] (* list, using :: *)
val (a, b) = (1, 2) (* tuple *)
val (a, b) = ((1, 2), (1, 2)) (* tuple of tuples - a and b are both now (1, 2) *)
val Node(a, b, c) = Node(1, Leaf, Leaf) (* constructors *)
val {first, last} = {first="Ash", last="Ketchum"} (* records, I don't remember covering this though *)

Cannot pattern-match on: non-constructor functions (e.g. !, str)

4Higher-order functions¶

4.1Standard library functions¶

We're expected to know the functionality and types of the following standard library functions:

• List.concat (@) - fn : 'a list list -> 'a list
  Example: List.concat [[1,2],[3,4],[5]], which is equivalent to [1,2] @ [3,4] @ [5], returns [1,2,3,4,5]
• List.map (map) - fn : ('a -> 'b) -> 'a list -> 'b list
  Example: List.map (fn x => ~x) [1,2,3,4,5,~10] returns [~1,~2,~3,~4,~5,10]
• List.filter - fn : ('a -> bool) -> 'a list -> 'a list
  Example: List.filter (fn x => x mod 2 = 0) [1,2,3,4,5] returns [2, 4]
• List.foldl - fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b list
  Starts from the left; the initial value is passed after the function, and is used as the second element in the tuple of the function's input
• List.foldr - fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b list
  Starts from the right
• List.exists - fn : ('a -> bool) -> 'a list -> bool
• List.all - fn : ('a -> bool) -> 'a list -> bool

4.2Continuations¶

4.3Staging and partial evaluation¶

Recall the List.filter example. If we didn't pass in the list at the same time as we passed in the function, we would be staging it, resulting in a function of type fn : int list -> int list:

val remove_odds = List.filter (fn x => x mod 2 = 0)

We could do a similar thing with the List.all function:

val is_even = List.all (fn x => x mod 2 = 0)

This would result in a function of type fn : int list -> bool.

5Lazy programming¶

6Exceptions¶

7Closures as objects¶

8References¶

9Proof by induction¶

10Environment diagrams¶

11Theoretical aspects¶

12Miscellaneous¶

12.1Function application¶

Function application is left-associative. (map (fn x => x)) [1,2,3] is the same thing as map (fn x => x) [1,2,3] but NOT the same thing as map ((fn x => x) [1,2,3]) (the latter would generate a tycon mismatch error). Another example: if f were the successor function, then f 1 * 2 would not be the same as f (1 * 2) - the former would result in 4, the latter in 3.

12.2Function types¶

Types, on the other hand, are right-associative. So int list -> int -> bool is the same as int list -> (int -> bool), meaning that the function takes in an int list and returns a function that takes in an int and returns a bool. It is not, however, the same as (int list -> int) -> bool, which is a function that takes in a function from int list to int and returns a bool.

Example of the former:

(* Pass it a list and a number, and it will return a boolean indicating whether or not that number is greater than all the other elements in the list *)
fun is_greater_than_max l n = List.all (fn i => i < n) l

is_greater_than_max [1,23,4,5] 5 (* returns false *)
is_greater_than_max [1,23,4,5] 25 (* returns true *)

Example of the latter:

(* Pass it a function from int list to int, and it will tell you whether or not passing it a list containing one 0 returns 0 *)
fun test_on_0_list f = (f [0]) = 0

test_on_0_list (fn x => 1) (* returns false *)
test_on_0_list (fn x => 0) (* returns true *)
test_on_0_list (List.foldl op + 0) (* return true *)
test_on_0_list (List.foldl op + 1) (* return false *)