- (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)!)
-
(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.
- (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.
-
(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?
- (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]]
-
(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]
-
(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?
-
(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]]
-
(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"]
-
(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)
-
(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
-
(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
-
(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
-
(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)
-
Define the data type suitable to represent the search
three
-
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.
-
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.
-
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!
-
Exercise 9.3 in Sethi
-
Exercises 9.5 and 9.6 in Sethi