(* Yesterday in class we did some OCaml review.  These notes very
   quickly go through the things we reviewed from 330.  (We covered
   some other stuff too!)

   If you want a more thorough tutorial on OCaml, see:
   http://ocaml.org/learn/tutorials/

   - DVH, 1.28.15 *)

(***********************************************************************)
(***********************************************************************)
(* REVIEW *)

(* Stuff you know from 330:
   - tuples
   - lists
   - recursion
   - pattern matching
   - higher-order functions
   - currying
   - data types
   - modules
   - module types
   - updatable references 
*)

(***********************************************************************)
(* Tuples: are fixed size, heterogenous collections of data. *)

(* a "2-tuple", aka pair, of an int and string. *)
(1, "string");;

(* a "3-tuple" of a boolean, float, and char. *)
(false, 4.3, 'a');;

(***********************************************************************)
(* Lists: arbitrarily sized homogenous collections of data *)

(* the empty list, contains no elements. *)
(* Q: what is the type of the empty list? *)
[];;

(* a list of integers *)
[1; 2; 3];;

(* a list of integer-string pairs *)
[(1, "string"); (2, "foo"); (3, "fred")];;

(***********************************************************************)
(* Recursion: the ability to solve a problem by assuming the ability
   to solve smaller instances of the problem. *)

let rec fact (n : int) : int =
  if (n = 0) then
    1
  else
    n * (fact (n-1))
;;

fact 5;;  (* 120 *)

(***********************************************************************)
(* Pattern matching: combination of variable binding and conditional
   evaluation for concisely describing case analysis on data. *)

let rec fact' (n : int) : int =
  match n with
    | 0 -> 1
    | n -> n * (fact' (n-1))
;;

(* Another way to write the same thing *)
let rec fact'' : (int -> int) = function
  | 0 -> 1
  | n -> (n * (fact'' (n-1)))
;;

(* Sum a list of integers (using pattern matching) *) 
let rec sum (ns : int list) : int =
  match ns with
    | [] -> 0
    | hd::tl -> hd + (sum tl)
;;

  
(***********************************************************************)
(* Higher-order functions: the ability for functions to consume and
   produce other functions *)

(* make_adder n produces a function that adds n. *)
let make_adder (n : int) : (int -> int) =
  fun m -> n + m
;;

(* Q: Can you come up with a more general type for this function? *)
let rec map (f : (int -> int)) (ns : int list) : int list =
  match ns with
    | [] -> []
    | n::ns -> (f n)::(map f ns)
;;

(* Add 5 to each element of this list. *)
map (make_adder 5) [1; 2; 3; 4];;

(* Currying: the representation of a multiple argument function as a
   single argument function that produces a function consuming the
   rest of the inputs. *)

let add x y = x + y;;

(* Note only one argument supplied to add. *)
map (add 5) [1; 2; 3; 4];;

(***********************************************************************)
(* Data types: the ability to define new kinds of data *)

(* Defines a new type called "pt" that is constructed by calling Point
with two integers. *)
type pt = Point of int * int

let a = Point (3, 4)

let manhattan_dist : pt -> int = function
  | Point (x, y) -> abs x + abs y
;;

manhattan_dist a;;

(* Data types can have multiple constructors and can be recursive *)
type binary_tree = 
  | Leaf 
  | Node of int * binary_tree * binary_tree
;;

let rec bt_sum (bt : binary_tree) : int =
  match bt with
    | Leaf -> 0
    | Node (n, left, right) ->
	n + bt_sum left + bt_sum right
;;

(***********************************************************************)
(* Modules: units of code *)

module Cartesian = struct
  type ct = Cart of int * int
  let m_dist : ct -> int = function
    | Cart (x, y) -> abs x + abs y
end
;;

Cartesian.m_dist (Cartesian.Cart (1, 2));;  

open Cartesian;;

m_dist (Cart (1, 2));;


(***********************************************************************)
(* Module types: interfaces for units of code *)

(* This defines the "interface" for Cartesian modules *)
module type Cartesian_type = sig
  type ct
  val m_dist : ct -> int
end
;;

(* This module implements the above interface *)
module Cartesian' : Cartesian_type = struct
  type ct = Cart of int * int
  let m_dist : ct -> int = function
    | Cart (x, y) -> abs x + abs y
end
;;

(***********************************************************************)
(* Updatable references: a mutable box *)

(* a function that remembers how many times it's been called *)

let f : unit -> int = 
  let i = ref 0 in 
    function () -> 
      (i := !i+1; !i)
;;

f ();;
f ();;
f ();;

(* Note that this destroys the mathematical principles you where
   taught in grade school: f () = f ().  Use with caution! *)