Exercise 1 Write a function
gcd : int → int → int
that returns the greatest common divisor (GCD) of two given non-negative integers. Use the Euclidean algorithm based on the following principle (for two integers n an m such that n ≥ m):
2
Exercise 2 Write a function
merge : int list → int list → int list
that takes two integer lists sorted in descending order and returns a new sorted integer list that includes every element in the two given lists. For example,
merge [3;2;1] [5;4] = [5;4;3;2;1]
merge [5;3] [5;2] = [5;5;3;2] merge [4;2] [] = [4;2] merge [] [2;1] = [2;1]
2
Exercise 3 Write a function
range : int → int → int list
range lower upper generates a sorted list of integers in the range [lower … upper]. If lower is greater than upper, the function returns the empty list. For example,
| range13 | = | [1;2;3] |
| range (−2) 2 | = | [−2;−1;0;1;2] |
| range22 | = | [2] |
| range2 (−2) | = | [] |
2
type formula = TRUE | FALSE
| NOT of formula
| ANDALSO of formula * formula
| ORELSE of formula * formula
| IMPLY of formula * formula
| LESS of expr * expr and expr = NUM of int
| PLUS of expr * expr
| MINUS of expr * expr
Exercise 4 Considering the above definition of propositional formula, write a function eval : formula → bool
that computes the truth value of a given formula. For example, eval (IMPLY (IMPLY (TRUE, FALSE), TRUE))
evaluates to true, and
eval (LESS (NUM 5, PLUS (NUM 1, NUM 2)))
evaluates to false. 2
Exercise 5 Binary trees can be inductively defined as follows:
type btree = Empty | Node of int * btree * btree
For example, the following t1 and t2 are binary trees.
let t1 = Node (1, Empty, Empty) let t2 = Node (1, Node (2, Empty, Empty), Node (3, Empty, Empty)) let t3 = Node (1, Node (2, Node (3, Empty, Empty), Empty), Empty)
Write a function height : btree → int
that computes the height of a given binary tree. The height of a given binary tree is inductively defined as follows:
heightEmpty = 0
(heightl) + 1 (heightl > heightr)
height (Node n,l r
(heightr) + 1 (otherwise)
For example,
| heightEmpty | = | 0 |
| heightt1 | = | 1 |
| heightt2 | = | 2 |
| heightt3
2 Exercise 6 Write a function |
= | 3 |
balanced : btree → bool.
that determines if a given binary tree is balanced. A tree is balanced if the tree is empty or the following conditions are met.
- The left and right subtrees’ heights differ by at most one, and
- The left subtree is balanced, and
- The right subtree is balanced.
For example,
| balancedEmpty | = | true |
| balancedt1 | = | true |
| balancedt2 | = | true |
| balancedt3 | = | false |
where t1, t2, and t3 are defined in Exercise 5. 2
Exercise 7 The fold function for lists
fold : (‘a → ‘b → ‘a) → ‘a → ‘blist → ‘a
recombines the results of recursively processing its constituent parts, building up a return value through use of a given combining operation. For example,
foldfa [b1;…;bn] = f (…(f (fab1) b2)…) bn.
Extend the following function that takes three lists. Write a function
fold3 : (‘a → ‘b → ‘c → ‘d → ‘a) → ‘a → ‘blist → ‘clist → ‘dlist → ‘a
of which meaning is defined as follow:
fold3fa [b1;…;bn] [c1;…;cn] [d1;…;dn]
= f (…(f (fab1c1d1) b2c2d2)…) bncndn.
You may assume that all the given lists are of the same length. 2
Exercise 8 Write a function
(iter
The function returns the identity function (fun x → x) when n = 0. For example,
(iter n (fun x -> x + 2)) 0
returns 2 × n. 2
Exercise 9 Write a function
sigma : int * int * (int -> int) -> int.
such that sigma(a,b,f) returns Σ
Exercise 10 Write a function cartesian: ’a list -> ’b list -> (’a * ’b) list
that returns a list of from two lists. That is, for lists A and B, the Cartesian product A × B is the list of all ordered pairs (a,b) where a ∈ A and b ∈ B. For example, if A = [“a00;“b00;“c00] and B = [1;2;3], A × B is defined to be
2
