CS:4420 Artificial Intelligence Spring 2019
Homework 1
Due: Tuesday, Feb 5 by 11:59pm
This is a programming assignment in OCaml to be done individually. Download the accompanying OCaml source file hw1.ml and enter your solutions in it where indicated. When you are done, submit it through the Assignments section of ICON as a plain text file with the same name. Make sure you write your name in that file where indicated.
Each of your answers must be free of static errors. You may receive no credit for problems whose code contains syntax or type errors.
Pay close attention to the specification of each problem and the restrictions imposed on its solution.
Solutions ignoring the restrictions may receive only partial credit or no credit at all.
In the following problems do not use any mutable predefined types such as references, mutable records, arrays, and so on. Define your functions recursively as needed and take advantage of the match operator.
You do not need, and should not use, any OCaml library functions over lists except for built-in operators [], ::, and @. However, you can use your own auxiliary functions if you prefer.
Do not worry about the efficiency of your solution. Strive instead for cleanness and simplicity.
Unnecessarily complicated code may not receive full credit.
1
1.
2.
3.
Programming Functional Style with Lists
Write a function sum: int list -> int which takes as input a list l of integers and returns the sum of all the elements in l.
For example, sum [10; 3; 5] is 18, while sum [] is 0.
Write a function pairsum: (int * int) list -> (int * int) which takes as input a list l of integer pairs and returns the sum of all the pairs in l, where the sum of two pairs (x1, y1) and (x2,y2) is (x1 +x2,y1 +y2).
For example, pairsum [(10,1); (3, 0); (5,-2)] is (18,-1), while pairsum [] is (0,0).
Write a parametric function zip: ’a list -> ’b list -> ’a * ’b list which takes two lists of the same length and produces a list of pairs of corresponding elements in the two input lists.
1
2
4.
5.
6.
7.
8.
For example, zip [4; 2; 5; 9] [“a”; “b”; “c”; “d”] is [(4, “a”); (2, “b”); (5, “c”); (9, “d”)].1
Write a parametric function drop: ’a -> ’a list -> ’a list which takes as input a value x of type ′a and an ′a list l, and “drops” all the occurrences of x from l, that is, returns a list containing, in the same order, all and only the elements of l that differ from x.
For example,
drop 2 [2; 1; 3; 3; 2; 1] is [1; 3; 3; 1],
drop 5 [2; 1; 3; 3; 2; 1] is [2; 1; 3; 3; 2; 1].
Write a parametric function replaceAll: ’a -> ’a -> ’a list -> ’a list which, given values x and y of type ′a and an ′a list l, returns a list identical to l except that every occurrence of x in l is replaced by y in the new list.
For example, replaceAll 2 22 [2; 1; 3; 2; 1] is [22; 1; 3; 22; 1].
Write a function insert:int -> int list -> int list which takes an integer n and an integer list l sorted in strictly increasing order returns l if n is already in l; otherwise, it “inserts” n in l while maintaining the order, that is, it returns a list that contains n and all the elements of l and is sorted in strictly increasing order.
Forexample,insert 3 [1; 3; 7; 8]is[1; 3; 7; 8]andinsert 5 [1; 3; 7; 8]is[1; 3; 5; 7; 8].
Using the function insert above, write a function sort:int list -> int list which takes a list l and returns a list consisting of all the integer values in l in strictly increasing order. Forexample,sort [1; 3; 8; 7; 1; 5; 3]is[1; 3; 5; 7; 8].
Write a function middle: ’a list -> ’a which takes a list with an odd number of elements and returns its middle element.
For example, middle [4] is 4 and middle [’A’; ’B’; ’C’; ’D’, ’E’] is ’C’.
Programming Functional Style with Trees
Consider a variant of the binary tree datatype seen in class, parametrized by the type of element stored in a node:
type ’a btree = Empty | Node of ’a * (’a btree) * (’a btree)
1. Write a parametric function size: ’a btree -> int which, given a binary tree t, returns
the number of (non-empty) nodes in it.
2. Write a parametric function depth: ’a btree -> int which takes as input a binary tree t, and returns the depth of t, that is, the length of the longest path in t from the root to a (non-empty) leaf node.
For example, depth Empty is 0, depth (Node 6, Empty, Empty) is 1, and
1Here and later use failwith to raise an exception when the input does satisfy the assumptions.
2
depth (Node (“a”, Node (“b”, Empty, Empty),
Node (“c”, Empty,
Node (“d”, Empty, Empty)))) is 3, the length of the path “a”, “c”, “d”.
3. Write a parametric function prune: ’a -> ’a btree -> ’a btree which, given a value x of type ’a and a tree t, returns a tree identical to t except that every node with value x, if any, has empty right and left subtrees. For example,
prune 3 (Node (3, Node (1, Empty, Empty),
Node (4, Empty,
Node (7, Empty, Empty)))) is Node (3, Empty, Empty), while
prune 4 (Node (3, Node (1, Empty, Empty),
Node (4, Empty,
Node (7, Empty, Empty))))
is
Node (3, Node (1, Empty, Empty),
Node (4, Empty, Empty))
4. Write a parametric function rotateLeft: ’a btree -> ’a btree which takes a non-empty tree t with a non-empty right subtree and rotates t right, that is, produces a tree t′ as pictured below, where x and y denote node values and t1, t2 and t3 denote subtrees.
t −→ t′ yx
xy
t1 t3
t2 t3 t1 t2
If the input tree t does not have the shape above, it is returned unchanged.
5. [Optional, extra credit] Design a ’a tree datatype for trees where a (non-empty) node carries a value of type ’a and can have an arbitrary number of subtrees (zero or more). Then implement a function size: ’a tree -> int which, given a tree t, returns the number of (non-empty) nodes in it.
3