Description

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