### CSE 428: Exercises on ML

The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

1. (s) Define a function which computes the product of all integers between m and n (with n >= m) inclusive. Use this function to define the function Cn,k (the number of combinations of n elements taken k by k), which is defined by
Cn,k = n!/(k!*(n-k)!)
2. (s) Define a function
power : int * int -> int
so that, for m >=0
power(n,m) = nm
holds. Note: we assume that 00 is defined as 1.
3. (s) The positive integer square root of a non-negative integer is a function introot such that: if introot m = n, then n is the largest integer such that n2 is less than or equal to m. Define the function introot in ML.
4. (s) In ML, like in any other language, the if-then-else construct is non-strict, i.e. only one of the branches is evaluated, depending on the the result of the test. What would be the consequences for recursive definitions if the if-then-else were strict (meaning that first both the branches are evaluated, and then one of the results is picked, depending on the result of the test), and pattern-matching were not available?
5. (s) Define a function copy: int * 'a -> 'a list such that copy(k,x) gives the list containing k occurrences of x. Examples:
```   copy(0,5) = []
copy(1,5) = [5]
copy(3,"a") = ["a","a","a"]
copy(3,copy(1,8)) = [[8],[8],[8]]
```
6. (s) Define a function sumlists: int list * int list -> int list which takes in input two lists of integers and gives as result the list of the sums of the elements in corresponding position in the input lists. The shortest list has to be seen as extended with 0's. Examples:
```   sumlists([],[]) = []
sumlists([1,2],[3,4]) = [4,6]
sumlists([1],[3,4,2]) = [4,4,2]
sumlists([1,6],[3]) = [4,6]
```
7. (s) Define a function remove_dup: ''a list -> ''a list which takes in input a list and removes all the duplicates, Examples:
```   remove_dup [] = []
remove_dup [1,2,1] = [1,2]
remove_dup ["a","a","a"] = ["a"]
remove_dup [[1],[1,2],[1,2,3],[1,2],[4,5]] = [[1],[1,2],[1,2,3],[4,5]]
```
Is it possible to define remove_dup with a more generl type, i.e. remove_dup: 'a list -> 'a list?
8. (s) Define a function first_list: ('a * 'b) list -> 'a list which takes in input a list of pairs and gives back the list consisting of the first elements only, Examples:
```   first_list [] = []
first_list [(1,2),(1,3)] = [1,1]
first_list [(1,"a"),(2,"b"),(3,"c")] = [1,2,3]
first_list [([],"a"),([1],"b"),([1,2],"c")] = [[],[1],[1,2]]
```
9. (s) Define a function flatten: 'a list list -> 'a list which takes in input a list of lists and gives back the list consisting of all the elements, in the same order in which they appear in the argument. Examples:
```   flatten [[]] = []
flatten [[1,2],[2,3,4],[5],[],[6,7]] = [1,2,2,3,4,5,6,7]
flatten [["a"],["b","a"]] = ["a","b","a"]
```
10. (s) Consider the data structure "binary tree", defined in Assignment 7:
```   datatype 'a btree = emptybt | consbt of 'a * 'a btree * 'a btree;
```
Define a function sum_tree : int btree -> int which returns the sum of all the elements of the tree (0 if the tree is empty)
11. (s) Consider the data structure "binary tree" of previous exercise. Define a function mirror : 'a btree -> 'a btree which returns the "mirror" of the input tree. Example:
```      1                     1
/ \                   / \
2   3   - mirror ->   3   2
/ \               / \
4   5             5   4
\           /
6         6
```
12. (s) Define a function breadth_first: 'a btree -> 'a list which takes a binary tree and returns a list representing the breadth first visit of the tree (visit by level). Example:
```         1
/ \
2   3
/ \   \
4   5   6  - breadth_first -> [1,2,3,4,5,6,7,8,9]
/    /
7    8
\
9
```
13. (s) Define a data structure 'a tree, which has an arbitrary number of subtrees for every node. On this structure, define the function pre_visit. Example:
```         1
/ \
2   3
/|\  |
4 5 6 7_    - pre_visit -> [1,2,4,5,6,3,7,8,9,0,9]
/|\ \
8 9 0 9
```
14. (s) We want to organize a data base containing information about a number of people in such a way that it is easy to perform a search. To such purpose, we want to use a search three. For each person we will have a record containing the following information:
• the name of the person (represented as a string)
• the date of birth (represented in the format (DD, MM , AAAA) where DD , MM and AAAA are numbers)
• the place of birth (represented as a string)
1. Define the data type suitable to represent the search three
2. Define a function build_search_tree which, given a (unordered) list of records, transforms it into a search tree, as balanced as possible. The key field is the name, i.e. the information has to be organized in the tree with respect to the alphabetical order on names.
3. Define a function search that, given a search three and a name, returns the date and place of birth of the person with that name, if it is in the tree, and some message of unsuccessful search otherwise.

15. Define the datatype 'a stack (stack of elements of the generic type 'a) with operations
```   emptystack : 'a stack
push : 'a * 'a stack -> 'a stack
is_empty : 'a stack -> bool
pop : 'a stack -> 'a stack
top : 'a stack -> 'a
```
Some of these operations can be implemented as constructors and the others as functions. Be careful about choosing the right set of constructors!
16. Exercise 9.3 in Sethi
17. Exercises 9.5 and 9.6 in Sethi