[Solved] ENE4014-Homework 1

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
heightt32Exercise 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 = [a⁰⁰;b⁰⁰;c⁰⁰] and B = [1;2;3], A B is defined to be

2