Midterm review

Stuff to know for the midterm. First, the details:

The midterm exam will take place in Leacock 26, between 14:35 and 15:25 on Wednesday, February 29. The exam is closed book, with a one-page crib sheet (back and front) allowed. The exam will consist of one proof and several programs to write.

Subjects that will be on the exam (non-exhaustive):

• References
• Proof by induction
• Rewriting standard library functions, possibly using tail recursion
• Using specific standard library functions (e.g. fold) to write others

Subjects that will not be on the exam:

• Lazy computation (including streams)
• Exceptions
• Continuations
• Regular expressions

1Datatypes¶

• Basic datatypes: int, real, string, boolean
• Tuples: int * real, etc
• Functions
• Custom datatypes
  • Cards
  • Trees
• Lists
  • Recursively defined datatype - basically set comprehension¹

2Rewriting standard library functions¶

• The regular way
• Using tail recursion (an accumulator)
• length:

- fun length [] = 0 | length (_::t) = 1 + length t;
val length = fn : 'a list -> int
- length [1,2,3];
val it = 3 : int
- length [];
val it = 0 : in

• rev (tail recursion):

- fun rev list = let fun rev' ([], acc) = acc | rev' (h::t, acc) = rev' (t, h::acc) in rev' (list, []) end;
val rev = fn : 'a list -> 'a list
- rev [1,2,3,4];
val it = [4,3,2,1] : int list

3Higher order functions¶

3.1Using standard library functions¶

• Like map, fold, etc
• Note that you can do op + which will produce the function fn x, y => x + y (so same thing)
  • Doesn't need parenthesising ... for example, to pass it to fold, foldl op + 0 some_list will result in the sum of some_list
• Reversing a string: fun srev (s:string):string = implode (rev (explode s));

3.2Currying¶

- fun curry f = fn (x, y) => f x y;
val curry = fn : ('a -> 'b -> 'c) -> 'a * 'b -> 'c
- fun uncurry f = fn x => fn y => f (x, y);
val uncurry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
- fun lol a b = a ^ b;
val lol = fn : string -> string -> string
- lol ("lol" "lol");
stdIn:5.6-5.17 Error: operator is not a function [tycon mismatch]
  operator: string
  in expression:
    "lol" "lol"
- lol "lol" "lol";
val it = "lollol" : string
- (curry lol) ("lol", "lol");
val it = "lollol" : string
- (uncurry (curry lol)) "lol" "lol";
val it = "lollol" : string

3.3Partial evaluation¶

• order of evaluation? associativity?
• left-associative so ` fun

- fun c k a = k;
val c = fn : 'a -> 'b -> 'a
- val c = fn k => (fn a => k);
val c = fn : 'a -> 'b -> 'a

- fun blah list f = length (f list);
val blah = fn : 'a -> ('a -> 'b list) -> int
- fun blah list f = length f list;
stdIn:9.19-9.32 Error: operator is not a function [tycon mismatch]
  operator: int
  in expression:
    (length f) list
- (* The above gets evaluated as ((length f) list) *)

4Proof by induction¶

• Structural induction
• tail recursion, using a generalised lemma to prove the full thing

5References¶

To create a reference:

val r = ref 0
val s = ref 0

Now, r and s are both references to 0, but they're not pointing to the same cell in memory. To read:

5.1Updating references¶

r := 4

5.2Reading references¶

val r_value = !r

5.3Closures and pseudo-objects¶

• To have a function take no parameters: fun blah () = ...

• To chain function calls together (only the last value evaluated is returned):

  fun blah () = (do_something 5; do_something_else)

• Records: val a = {lol="lol", blah="blah"}

• To get "lol", do #lol a

5.4Notes¶

• there is no pointer arithmetic in SML
• you can have a self-referential reference

6To do and miscellaneous notes¶

• examples from the assignments
• currying
• common errors
  • andalso and orelse (short-circuit evaluation)
  • parentheses in constructed patterns when pattern-matching, e.g. (h::t) not h::t and (Node(k, v)) not Node(k, v)
  • reals and functions are NOT equality types
  • type checker evaluates both branches of an if/else statement even if the condition is true, so if the branches are of different types --> errors
• creating new types: type keyword

- type lol = (int * int);
type lol = int * int
- val blah = (5, 5);
val blah = (5,5) : int * int
- val blah : lol = (5, 5);
val blah = (5,5) : lol
- type person = {name : string, age : int};
type person = {age:int, name:string}
- val me = {age=12, name="what is this"};
val me = {age=12,name="what is this"} : {age:int, name:string}
- val me : person = {age=12, name="what is this"};
val me = {age=12,name="what is this"} : person

• () is the empty tuple; type: unit. Note that there are no tuples with only one element.
• characters: #"a" etc
• converting to real: real(5) etc (fn : int -> real)
• _ in pattern matching or variable names is a wildcard binding; is thrown away
• decomposing tuples/records/structures is preferred over sharp notation (#1 or #age etc)
• Bind failure: execution time, heterogeneous types only; e.g. val 0 = 1 + 1
• for some reason you can redefine not (e.g. defining a function called not) but you can't with and or andalso etc
• mutual recursion - for example:

- fun even x = case x of 0 => true | n => odd (n-1) and odd x = case x of 0 => false | n => even (n-1);
val even = fn : int -> bool
val odd = fn : int -> bool

• as keyword:

- fun lol (x as (a, b, c, d, e, f, g)) = x;
val lol = fn  : 'a * 'b * 'c * 'd * 'e * 'f * 'g -> 'a * 'b * 'c * 'd * 'e * 'f * 'g

• type information is necessary when using overloaded arithmetic operators; sml/nj will assume int by default in most cases, so passing in reals requires (x:real) or whatever
• :: is right-associative; 1::2::3::[] gives [1, 2, 3] as one might expect
• self-note for tail recursion: the one that's not the accumulator (i.e. the variable with the base case) should be the one that's pared down