OCaml List Lecture (9/13/18)

list.ml

(* Exercise: Write the class definition (no methods) for a linked list in
   Java. *)

(* Bad Approach:

   class List<T> {
     T data;
     List<T> next;
   }
 
   List<Integer> singleton = new LinkedList<>(1, null);
   List<Integer> larger = new LinkedList<>(0, singleton);
*)

(* This uses null. A null is a lie. The type for List<T> says that the
   next field has to be of type list. But null obviously isn't a list!
   You can't get it's length, etc. *)

(* Better Approach:

   interface List<T> { ... }
   class Empty<T> implements List<T> { ... }
   class NonEmpty<T> implements List<T> {
     T first;
     List<T> rest;
     ...
   }
 
   List<Integer> singleton = new NonEmpty<>(1, new Empty<>());
   List<Integer> larger = new NonEmpty<>(0, singleton);
*)

(* Here you can never run into any NullPointerException issues
   because there aren't any nulls! We explicitly represent the
   empty list and enforce that it actually is a real List<T>.
   Not a fake List<T> like null was. *)

(* We use this to motivate the definition of a list. *)

(* What is a list? *)
(* A [List of T] is either
   - Nil
   - Cons of (T, [List of T]). *)

(* Two important things to notice about this definition
   - it's recursive (so lists can have arbitrary size)
   - they're homogeneous (as opposed to Ruby). *)

(* In OCaml, a list is either
   - []
   - x :: xt. *)

(* Here's how we construct lists. Same as in Java, but with
   a much nicer syntax. The :: is called the "cons" operator.
   "Cons" for construct. It builds up the pairs. *)

[]
(0 :: [])
(0 :: (1 :: []))
(0 :: (1 :: (2 :: [])))

(* This is cumbersome to write. *)
(* There is syntactic sugar for this in OCaml. *)

[]
[0]
[0; 1]
[0; 1; 2]

(* These can also be evaluated as you'd expect. *)

[1 - 1; 1 + 1]

(* They are NOT comma separated. *)
(* OCaml will let you write something like [0, 1, 2]. *)
(* However, it's not what you think it is! *)

(* What is the type of the following? *)

[1; "world"]     (* error *)
0 :: [1; 2; 3]   (* int list *)
[[1]; [2; 3]]    (* int list list *)
[1; 2] :: 3      (* error *)
[1; 2] :: [3; 4] (* error *)
[]               (* 'a list (polymorphic type, like generic type in Java)
                    says that this has type 'a list for any type 'a *)

(* You should think of (::) as a function. *)
(* In fact, what's the type of the following function? *)

let cons x y = x :: y

(* Notice the polymorphic variables. We see that x is 'a (meaning an
   arbitrary type) and y is 'a list. The 'a are arbitrary, but they're
   the SAME arbitrary type. *)

(* Remember, OCaml is a functional language. Therefore, mutation
   is discouraged. Lists are not mutable. *)

let xs = [1; 2; 3]
0 :: xs
xs (* unchanged *)

(* We can create lists, but that's useless if we cannot manipulate them. *)
(* We need to dissect them, pull them apart, do surgery. *)
(* Pattern matching is a powerful way to do this. *)

match xs with
| x :: xt -> x

(* After "match" comes the thing we want to match against. To the left
   of the arrow are patterns. To the right is the result if the pattern
   was a success. This is a switch statement on steroids. *)

(* What's with that warning? *)
(* OCaml is smart and knows that this could yield problems. *)

let xs = []
match xs with
| x :: xt -> x

(* You should always have exhaustive patterns. *)

match xs with
| [] -> 0
| x :: xt -> x

(* We can do more cool things. What if we want to add the first
   three elements and give back zero for smaller lists? *)

match ys with
| y0 :: y1 :: y2 :: yt -> y0 + y1 + y2
| y0 :: y1 :: yt -> 0
| y0 :: yt -> 0
| [] -> 0

(* There's a better way to write this. *)
(* Use a wildcard (this relies on the fact pattern matching is ORDERED). *)

match ys with
| y0 :: y1 :: y2 :: yt -> y0 + y1 + y2
| _ -> 0

(* What about this? *)

match xs with
| [] -> true
| _ -> 0

(* The types of thing you're matching and all the patterns must be
   the same. The right-hand side types must all be the same too. *)

(* See the slides for more pattern matching voodoo. *)

(* Returns if the list is empty. Notice this is polymorphic. *)
let is_empty xs =
  match xs with
  | x :: xt -> false
  | [] -> true

is_empty []
is_empty [1; 2; 3]

(* Returns the head of the list. *)
let hd xs =
  match xs with
  | x :: xt -> x

(* This is polymorphic too! *)

(* Returns the head of the list. *)
let hd' (x :: xt) = x

(* Returns the sum of elements in xs. *)
let rec sum xs =
  match xs with
  | x :: xt -> x + (sum xt)
  | [] -> 0

(* This isn't polymorphic. *)
(* The use of + on the elements of the list enforces
   that this be an int list. *)

(* Returns the length of the list. *)
let rec length xs =
  match xs with
  | _ :: xt -> 1 + (length xt)
  | [] -> 0

length []
length [1; 2; 3]

(* Returns element at index k. *)
let rec index xs k =
  match xs with
  | x :: xt -> if k = 0 then x else index xt (k - 1)
  | [] -> -1 (* unfortunately forces xs to be int list... *)

(* We'll see a way to fix this soon enough. It's called
   option types. *)

(* Returns the last element of the list. *)
let rec last xs =
  match xs with
  | [x] -> x
  | _ :: xt -> last xt

last []
last [1]
last [1; 2; 3]

(* Appends the two lists together. *)
let rec append xs ys =
  match xs with
  | x :: xt -> x :: (append xt ys)
  | [] -> ys

append [] []
append [] [2; 3]
append [2; 3] []
append [0; 1] [2; 3]

(* What happens if you do... *)

append ["hello"; "world"] [0; 1]

(* Reverses the list. *)
let rec rev xs =
  match xs with
  | x :: xt -> append (rev xt) [x]
  | [] -> []

rev []
rev [1; 2; 3]

(* This is O(n ^ 2). *)
(* There's an O(n) function that you can write. Can you think of it? *)
(* Hint: You'll need a rev helper function with one extra parameter. *)