ENE4014- Homework 1 Solved

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