(* OCaml compatibility *) module List = let flatten l = List.fold (fun ac e -> ac@e) [] l module String = let sub (str: string) s e = str.Substring(s,e) let print_line (s: string) = System.Console.WriteLine s let print_string (s: string) = System.Console.Write s let string_of_int i = sprintf "%i" i let string_of_bool (b: bool) = sprintf "%b" b (* /OCaml compatibility *) (* CSE P505, Autumn 2016, Homework 1 *) (************************ Problem 1 ***********************) type inttree = Empty | Node of int * inttree * inttree (* use this function in fromList *) let rec insert t i = match t with Empty -> Node(i,Empty,Empty) | Node(j,l,r) -> if i=j then t elif i < j then Node(j,insert l i,r) else Node(j,l,insert r i) (* no need for this function; it is just an example *) let rec contains t i = match t with Empty -> false | Node(j,l,r) -> i=j || (i < j && contains l i) || contains r i (* put fromList, sum1, prod1, avg1, map and negateAll here *) let rec fold f a t = match t with Empty -> a | Node(j,l,r) -> fold f (fold f (f a j) l) r (* put your English answer to 1e here *) (* put sum2, prod2, and avg2 here *) (* a little testing for problem 1 -- commented out since the functions do not exist yet (You can/should write similar tests for other problems, but we won't grade your tests.) *) (* let tr = fromList [0;1;2;3;4;5;6;7;8;9;9;9;1] (* repeats get removed *) let print_ans f t = print_string (string_of_int (f t)); print_string "\n" let _ = print_ans sum1 tr let _ = print_ans prod1 tr let _ = print_ans avg1 tr let _ = print_ans sum2 tr let _ = print_ans prod2 tr let _ = print_ans avg2 tr *) (************************ Problem 2 ***********************) let compose f g x = f (g x) let flatten_map f = compose List.flatten (List.map f) let firsts ss = List.map (fun s -> String.sub s 0 1) ss (* (* these tests should pass when done with Problem 2; each is true *) let test1 = stutter ["hi"; "bye"] = ["hi"; "hi"; "bye"; "bye"] let test2 = firsts2 ["foo"; ""; ""; "bar"] = ["f"; ""; ""; "b"] let test3 = remove_empties ["foo"; ""; ""; "bar"] = ["foo"; "bar"] *) (************************ Problem 3 ***********************) (* put your answer to problem 3 here *) (************************ Problem 4 ***********************) type pattern = Wildcard | Variable of string | UnitP | ConstP of int | TupleP of pattern list | ConstructorP of string * pattern type valu = Const of int | Unit | Tuple of valu list | Constructor of string * valu let rec g v f2 p = let r = g v f2 in match p with Wildcard -> v | Variable x -> f2 x | TupleP ps -> List.fold (fun i p -> (r p) + i) 0 ps | ConstructorP(_,p) -> r p | _ -> 0 (* put your answer to problem 4 here *) (********************* Challenge Problem 5 *****************) type 'a iterator = Nomore | More of 'a * (unit -> 'a iterator) let rec iter t = let rec f t k = match t with Empty -> k () | Node(j,l,r) -> More(j, fun () -> f l (fun () -> f r k)) in f t (fun () -> Nomore) (* put your English description here *) (* put sum3, prod3, and avg3 here *) (********************* Challenge Problem 6 *****************) type typ = Anything | UnitT | IntT | TupleT of typ list | Datatype of string (* put typecheck_patterns (and whatever helper functions) here *)