(* 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 *)