辅导CS:4420、OCaml留学生辅导、讲解c/c++，Java编程设计、辅导Python语言

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 Programming Functional Style with Lists

1. 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.

2. 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).

3. 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

For example, zip [4; 2; 5; 9] ["a"; "b"; "c"; "d"] is

[(4, "a"); (2, "b"); (5, "c"); (9, "d")].

1

4. Write a parametric function drop: ’a -> ’a list -> ’a list which takes as input a value

x of type 0a and an 0a 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].

5. Write a parametric function replaceAll: ’a -> ’a -> ’a list -> ’a list which, given

values x and y of type 0a and an 0a 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].

6. 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.

For example, insert 3 [1; 3; 7; 8] is [1; 3; 7; 8] and insert 5 [1; 3; 7; 8] is [1;

3; 5; 7; 8].

7. 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.

For example, sort [1; 3; 8; 7; 1; 5; 3] is [1; 3; 5; 7; 8].

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’.

2 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

0 as pictured

below, where x and y denote node values and t1, t2 and t3 denote subtrees.

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.