(* COMP 302 Winter 2013 HOMEWORK 2
   Instructors: Francisco Ferreira, Andrew Cave
   Due 1st February 2013, at the BEGINNING OF CLASS (2:35pm)
 *)

(* Question 1 code for reference *)
infix 3 \/

fun m \/ n = Int.max (m,n)

datatype mobile = Object of int | Wire of mobile * mobile

fun mobile_max (Object n) = n
  | mobile_max (Wire (l,r)) = (mobile_max l) \/ (mobile_max r)

fun mobile_max_acc (Object n) m = n \/ m
  | mobile_max_acc (Wire (l,r)) m = mobile_max_acc l (mobile_max_acc r m)

exception NotImplemented

(* Please write your answers to this question on paper and submit them *)
(* in class or submit them in a PDF file with handin *)


(* Question 2: Associative lists *)

(* Question 2.1 *)
fun zipWith f xs ys = raise NotImplemented

(* Question 2.2 *)
fun ziprev xs ys = raise NotImplemented

(* Question 2.3 *)
fun lookup k xs = raise NotImplemented

(* Question 2.4 *)
type dict = string -> int option

val empty : dict = fn key => NONE

fun insert kv d = raise NotImplemented

fun lookup2 k d = d k

(* Examples: 

- val d = insert ("foo",2) (insert ("bar",3) empty);
val d = fn : string -> int option
- lookup2 "foo" d;
val it = SOME 2 : int option
- lookup2 "bar" d;
val it = SOME 3 : int option
- lookup2 "baz" d;
val it = NONE : int option

*)

(* Question 3 preamble *)

(* Suspended computation : we can suspend computation
   by wrapping it in a closure. *)
datatype 'a susp = Susp of (unit -> 'a)

(* delay: *)
fun delay (f ) = Susp(f)

(* force: *)
fun force (Susp(f)) = f ()

(* ---------------------------------------------------- *)
(* Define an infinite stream *)
datatype 'a stream' = Cons of 'a  * 'a stream
withtype 'a stream = ('a stream') susp

(* ---------------------------------------------------- *)
(* Inspect a stream up to n elements 
   take : int -> 'a stream' susp -> 'a list
   take': int -> 'a stream' -> 'a list
*)
fun take 0 s = []
  | take n (s) = take' n (force s)
and take' 0 s = []
  | take' n (Cons(x,xs)) = x::(take (n-1) xs)

(* Question 3.1 *)
fun hailstones n = raise NotImplemented

(* Examples:

- take 20 (hailstones 13);
val it = [13,40,20,10,5,16,8,4,2,1,4,2,...] : int list

- take 20 (hailstones 8);
val it = [8,4,2,1,4,2,1,4,2,1,4,2,...] : int list

*)

(* Question 3.2 *)

fun unfold f x = Susp(fn () => Cons(x, unfold f (f x)))

fun deriv f x = let val h = 0.0000001 in (f (x + h) - f x) / h end

fun newton f guess = raise NotImplemented

(* Example:

- take 10 (newton (fn x => x*x - 2.0) 7.0)
val it =
  [7.0,3.64285718209,2.09593841013,1.52508247335,1.41824348423,1.41421928801,
   1.41421356238,1.41421356237,1.41421356237,1.41421356237] : real list

*)