11. Give the types of each of the following Ocaml functions: (a) let alwaysfour x = 4 val alwaysfour : 'a -> int (b) let add x y = x + y val add : int -> int -> int (c) let concat x y = x ^ y val concat : string -> string -> string (d) let addmult x y = (x + y, x * y) val addmult : int -> int -> int * int (e) let rec f x = if x=[] then [] else hd x @ f (tl x) val f : 'a list list -> 'a list (f) let rec copy x = if x=[] then [] else hd x :: copy (tl x) val copy : 'a list -> 'a list (g) let b (x,y) = x+y val b : int * int -> int (h) let c (x,y) = x val c : 'a * 'b -> 'a (i) let d x = match x with (a,b) -> a val d : 'a * 'b -> 'a (j) let e x = hd x + 1 val e : int list -> int (k) let f x y = match x with [] -> 0 | a::b -> a+y val f : int list -> int -> int (l) let g (a,b) (c,d) = (a+d, b^c) (Recall that ^ is the string concatenation operation.) val g : int * string -> string * int -> int * string (m) let rec h x = match x with [] -> 0 | (a,b)::r -> a + (h r) val h : (int * 'a) list -> int22. Define the following OCaml functions: (a) contains : 'a -> 'a list -> bool such that contains x lst returns true if and only if lst has x as one of its elements. Do not use any pre-existing functions. E.g. contains 4 [3;4;5] = true let rec contains x lst = match lst with [] -> false | y::ys -> x = y || contains x ys (b) evens: ‘a list -> ‘a list returns the 2nd, 4th, etc. elements of its argument. E.g. evens [13;5;9;0;7;8] = [5; 0; 8] let rec evens lis = match lis with [] -> [] | [a] -> [] | (a::b::lis') -> b :: evens lis' (c) Implement the Ocaml function partition: int list -> (int list) list, which divides a list into “runs” of the same integer, e.g. partition [9;9;5;6;6;6;3] = [[9;9]; [5]; [6;6;6]; [3]] (You may define auxiliary functions, but it is not actually necessary.) let rec partition lis = if lis = [] then [] else match partition (tl lis) with [] -> [[hd lis]] | x :: xs -> if hd lis = hd x then (hd lis :: x) :: xs else [hd lis] :: (x :: xs) (d) genlist m n = [m; m+1; ... ; n] (or [] if m>n) let rec genlist m n = if m>n then [] else m :: (genlist (m+1) n)3(f) compress: int list -> (int * int) list replaces runs of the same integer with a pair giving the count and the number. E.g. compress [1;1;5;6;6;6;3] = [(2,1); (1,5); (3,6); (1,3)] let rec compress lis = if lis = [] then [] else match compress (tl lis) with [] -> [(1, hd lis)] | (n,x)::lis' -> if x = hd lis then (n+1,x):: lis' else (1, hd lis)::(n,x)::lis' (g) apply: string -> int list -> int applies the operator described by the string argument to the elements in the int list. The string argument can be either “times” or “plus”. apply “times” [2;3;4] = 24 Assume the int list argument is non-empty. let rec apply s lis = match lis with [n] -> n | n::lis' -> let n' = apply s lis' in if s="times" then n*n' else n+n'43. Suppose we are given the following type definition: type btree = Leaf of int | Node of int * btree * btree Define the following functions in Ocaml: (i) preorder: btree -> int list gives the preorder listing of the labels of the tree. E.g. let t = node(1, node(2, leaf(4), leaf(5)), node(3, leaf(6), leaf(7))) preorder t => [1; 2; 4; 5; 3; 6; 7] let rec preorder bt = match bt with Leaf n -> [n] | Node(n,lt,rt) -> n :: (preorder lt @ preorder rt) (ii) followpath: btree -> boolean list -> int list gives the list of integers in the tree on the path described by the boolean list, where “true” means follow the left child and “false” means follow the right child. You may assume that the path described by the boolean list actually exists in the tree. E.g. followpath t [true; false] => [1; 2; 5] let rec followpath bt blis = match bt with Leaf n -> [n] | Node(n,lt,rt) -> if blis = [] then [n] else if hd blis then n::(followpath lt (tl blis)) else n::(followpath rt (tl blis)) (iii) height: btree -> int gives the height of a tree, defined as the length of the longest path from the root to a leaf node. height t;;5 => 2 let max (x,y) = if x>y then x else y let rec height bt = match bt with Leaf n -> 0 | Node(n,lt,rt) -> 1 + max(height lt, height rt) (iv) balanced: btree -> boolean returns true if for every internal node, the heights of its children differ by no more than 1. balanced t => true let t1 = node(1, leaf(2), node(3, leaf(6), leaf(7))) => true let t2 = node(1, leaf(2), node(3, leaf(6), node(8, leaf(7), leaf(9))) => false let rec balanced bt = match bt with Leaf n -> true | Node(n,lt,rt) -> let h1 = height lt and h2 = height rt in let p = if h1<h2 then h2-h1 else h1-h2 in (p=0 || p=1) && balanced lt && balanced rt 4. Given this Java class definition: class List { public int h; public List t; public int hd () { return h; } public List tl () { return t; } public List (int h, List t) {this.h = h; this.t = t; } } The empty list is represented by null. Define the Java function to concatenate two lists: public static append (L1, L2) {6 if (L1 == null) return L2; return new List(L1.h, append(L1.t, L2)); } 5. Given the grammar: E -> E + T | T T -> T * P | P P -> id | ( E ) and an Ocaml type for trees: type tree = Node of string * tree list we can represent concrete syntax trees. For example, the syntax tree would correspond to the term Node(“E”, [Node(“E”, [Node(“T”, [Node(“P”, [Node(“id”, [])])])]); Node(„+“, []); Node(“T”, [Node(“P”, [Node(“id”, [])])])])7 Here is a type for abstract syntax : type exp = Id of string | Plus of Exp*Exp | Times of Exp*Exp Write a function abstract: tree -> exp to transform a concrete syntax tree to an AST. let rec abstract t = match t with Node(s, children) -> (match children with [] -> Id s | [ch] -> abstract ch | [Node(“(“,[]); ch; Node(“)”,[])] -> abstract …
View Full Document
Unlocking...