(* Solution set for Homework 1 *) (*************** Programming style ************************) let abc (x:bool) (y:bool) (z:bool) : bool = x && ( y || z ) let t (b:bool) (x:float) : float = let v = if b then sin x +. 1.0 else cos x in v *. v let danQuayle (((a,b),c):(float*float)*float) (((d,e),f):(float*float)*float) : float*float*float = ( b*.f -. c*.e, c*.d -. a*.f, a*.e -. b*.d) (* finds the largest element in a list, given a default value. *) let rec max (l: int list) (curr:int) : int = match l with [] -> curr | (hd :: tl) -> if hd > curr then max tl hd else max tl curr (* Reverses the order of elements in a list *) let reverse (l:int list) : int list = let rec reverse_aux (l: int list) (acc: int list) : int list = match l with [] -> acc | (hd :: tl) -> reverse_aux tl (hd :: acc) in reverse_aux l [] (************ Programming Language Syntax *****************) (* let x = 3 is not syntactically correct because there is * no body to the let expression. *) (* let add (x:int) (y:int) = x + y in add 2 is not * correct because the function is not annotated with its * return type. This is different than O'Caml where the * return type is optional. *) (* 3 + 4 * 5 is syntactically correct *) (* let count (x:int) :int = if x = 0 then 0 else count 1 + (x - 1) in count 3 * is not syntactically correct for one reason: * - I ommitted equality (=) from the list of binary operators. * There is another problem with this function, it is * recursive, so there should be a rec after let, however, * according to just the rules of the grammar, it is ok to omit the rec. *) (********* More programming language syntax ***************) (* The ML expression: let x = 3 in let y z = x in if true then (y 4) + (y 5) else y 6 *) (* Would be written as the following in Scheme: * * (let (x 3) * (let (y (lambda (z) x)) * (if #t * (+ (y 4) (y 5)) * (y 6)))) *) (* Assuming that variables are distinguishable from the keywords * (if, lambda, let, letrec) and the operators, then the grammar * is not ambiguous. * An arbitrary expression could be a variable, a boolean value, * a number or somthing in parentheses. We can tell all of these * cases apart easily. If it is something in parentheses, we can also * tell what sort of expression it is by looking at the first token. * Either the first word is one of the keywords (if, lambda, let, letrec) * or it is a binary or prefix operator or it isn't any of the above, * in which case it must be an application expression. *) (************* ML Programming from EOPL ******************) (* duple n x returns a list containing n copies of x * for example: * duple 2 3 return [3;3] * duple 4 ("ho","ho") returns * [ ("ho","ho"); ("ho","ho"); ("ho","ho"); ("ho","ho")] *) let rec duple (n: int) (x:'a) : ('a * 'a) list = if n = 0 then [] else (x,x) :: (duple (n-1) x) let d1 = duple 2 2 let d2 = duple 0 1 (* val d1 : (int * int) list = [(2, 2); (2, 2)] val d2 : (int * int) list = [] *) (* invert lst, returns a list with each pair reversed. * for example: * invert [("a",1);("a",2)] returns [(1,"a"),(2,"a")] *) let rec invert (lst : ('a * 'b) list) : ('b * 'a) list = match lst with [] -> [] | ((x,y) :: tl) -> (y,x) :: invert tl let i1 = invert [("a",1);("a",2)] (* val i1 : (int * string) list = [(1, "a"); (2, "a")] *) (* filter pred lst returns the list of those elements in * list that satisfy pred. * for example: * filter odd [0;1;2;3;4] return [1;3] *) let rec filter (pred: 'a -> bool) (lst: 'a list) : 'a list = match lst with [] -> [] | (hd :: tl) -> if (pred hd) then hd :: (filter pred tl) else (filter pred tl) let odd (x:int) = x mod 2 = 1 let f1 = filter odd [0;1;2;3;4] (* val f1 : int list = [1; 3] *) (* find pred lst returns the first element of the list that satisfies the predicate. Because no element may do so, the answer is returned in an option. *) let rec find (pred:'a -> bool) (lst:'a list) = match lst with [] -> None | (hd :: tl) -> if pred hd then Some hd else find pred tl let f2 = find odd [0;1;2] let f3 = find odd [] (* val f2 : int option = Some 1 val f3 : int option = None *) (* every pred lst returns false if any element of lst * fails to satisfy pred. *) let rec every (pred: 'a -> bool) (lst: 'a list) : bool = match lst with [] -> true | (hd::tl) -> pred hd && every pred tl let e1 = every odd [1;2;3] let e2 = every odd [1;3;5] (* list_set lst n x returns a list like lst, except that * the nth element (using zero-based indexing) is x. * for example: * list_set [1;2;3;4] 2 8 returns [1;2;8;4] * list_set [1;2;3] 5 10 returns [1;2;3] * You can assume n will be >= 0. *) (* val e1 : bool = false val e2 : bool = true *) let rec list_set (lst:'a list) (n:int) (x:'a) = match lst with [] -> [] | (hd::tl) -> if n=0 then x :: tl else hd :: list_set tl (n - 1) x let l1 = list_set [1;2;3;4] 2 8 let l2 = list_set [1;2;3] 5 10 (* val l1 : int list = [1; 2; 8; 4] val l2 : int list = [1; 2; 3] *) (* merge lon1 lon2, where lon1 and lon2 are lists of numbers sorted in * ascending order, returns a sorted list of all the numbers in lon1 and * lon2. For example: * merge [1;4] [1;2;8] returns [1;1;2;4;8] *) let rec merge (lon1:int list) (lon2:int list) : int list = match lon1,lon2 with [],_ -> lon2 | _,[] -> lon1 | (hd1::tl1),(hd2::tl2) -> if hd1 < hd2 then hd1 :: merge tl1 lon2 else hd2 :: merge lon1 tl2 let m1 = merge [35; 62; 81; 90; 91] [3; 83; 85; 90] let m2 = merge [1;4] [1;2;8] (* val m1 : int list = [3; 35; 62; 81; 83; 85; 90; 90; 91] val m2 : int list = [1; 1; 2; 4; 8] *) (* bst is the representation of a binary search tree. In a node of this tree, the numbers contained in the left subtree are smaller than the int at the node, and the numbers in the right subtree are greater. *) type bst = N of int * bst * bst | L type dir = Left | Right (* path n bst returns a list of Lefts and Rights, showing how to find the node containing n. If n is found at the root, return []. You may assume that the number exists in the tree. Use the "failwith" function for the case that cannot happen. for example: path 17 (N (14, N(7, L, N(12, L, L)) N(26, N(20, N(17, L,L), L) N(31,L,L)))) returns Some [Right; Left; Left] *) let rec path (n:int) (bst:bst) : dir list = match bst with L -> failwith "Impossible" | N (i, left, right) -> if i = n then [] else if i < n then Right :: (path n right) else Left :: (path n left) let p1 = path 17 (N (14, N(7, L, N(12, L, L)), N(26, N(20, N(17, L,L), L), N(31,L,L)))) (* val p1 : dir list = [Right; Left; Left] *)