Latest update April 19, 2015.

To prevent spambots from collecting mail addresses, all mail addresses on this page have the "@" replaced by "#".

Assignment 2

1) This first part is about using lists to represent sets.

1.1 First write a function called mem which, given an integer and a list of integers, returns true if the integer occurs at least once in the list and false otherwise.

Example:

   mem 2 [2;4;2;1] => true
   mem 5 [2;4;2;1] => false

(You cannot use the name "member" since it is a reserved word in F#.)

1.2 Then define two functions that each takes two lists of integers as arguments, and returns the union and the intersection respectively of the lists considered as sets. You will probably want to use the previously defined member function.

Example:

   intersection [1;4;6] [1;3;4;2;3] => [1;4]
   union [1;4;6] [1;3;4;2;3] => [1;2;3;4;6]

Note: the argument lists can be general lists. Thus, they are not necessarily sorted, and might contain duplicate elements. The resulting list must not contain any duplicate elements. However, it need not be sorted.

2) Define a function foo1 that takes an integer and a list of integers as arguments. The function shall search through the argument list, and every time the first argument occurs in the list it shall place that element in another list, which will be the return value from the function.

Example:

   foo1 1 [2;1;2;1;4;1] => [1;1;1]
   foo1 4 [2;1;2;1;4;1] => [4]

You shall now make a more advanced version of this function, called foo2. This function will be a higher-order function since it will take a function of type int - > int - > bool as first argument. This function will be used to test the integer argument against all elements of the list. Each element of the list that yields true when the operator is applied shall be placed in the return list.

Example:

   let eq x y = x = y
   let lt x y = x < y
   let gt x y = x > y

   foo2 eq 2 [1;2;4;2;5] => [2;2]
   foo2 lt 2 [1;2;4;2;5] => [4;5]
   foo2 gt 2 [1;2;4;2;5] => [1]

How can you express the three function calls to foo2 without first defining the functions eq, lt, and gt?

Note that foo1 and foo2, if you define them in a straightforward way (without explicit typings and such), most likely will become polymorphic: that is, they will not be limited to arguments of the types int and int list. Instead you should be able to use them with all types, as long as the argument types of the test function match the type of the elements in the list.

Example:

   foo1 'b' ['a';'b';'c';'d';'b'] => ['b';'b']
   foo2 lt 'b' ['a';'b';'c';'d';'b'] => ['c';'d']

3) We now turn to the definition and use of binary trees. Chapter 6 in the course book Functional Programming Using F# gives a good overview of finite trees: it might be a good idea to read this chapter before attacking this part of the assignment.

3.1 Declare a data type for binary trees with integers as data elements. This kind of tree is either a leaf containing an integer, or has a root that contains an integer and two subtrees.

3.2 Then create a module for binary trees that includes the data type declaration and the following functions:

left, and right are not defined for leaves. They should have proper error-handling if given a leaf as argument.

Binary trees can be used for many purposes, and you will now use this module in two different ways.

3.3 Create a module for Sorted binary trees, which uses your newly created module for binary trees. Sorted binary trees have the additional property, for non-leaves, that every element in the left sub-tree is smaller than the root, and every element in the right sub-tree is larger than or equal to the root. The data type declaration itself does not guarantee that the trees have this sortedness property. However, this property can be upheld if the trees are created and manipulated using only functions that preserve the property.

3.4 Now add to your sorted-tree module two functions that add elements to a sorted binary tree while preserving the sortedness:

Note that you should not declare a new data type for sorted binary trees!

Now you have two modules: one for general binary trees. and one for sorted binary trees. Each of them forms an abstract data type.

Sorted binary trees can be used to represent sets, like lists can. They have an advantage over lists in that if the tree is balanced, then the average time to test if an element is a member of the set is lower than for a list. It is possible to define operations on sorted binary trees such that the trees are always balanced: however, this is out of scope for the assignment.

To test your solution you do not need to make an interactive program where the user can dynamically add integers to the tree. It is sufficient to statically build a tree. You could for instance add the following definition: let tree = addList (Leaf 5) [2; 1; 6; 7]. You can then call the different functions from the interactive environment with tree as argument, for instance add tree 8.

3.6 Finally define a generic (polymorphic) version of the abstract data type for trees: that is, it shall be possible to store values of any kind in a tree as long as the values (1) belong to the same type, and for sorted trees; (2) can be compared with the operators =, <, etc. It is actually quite easy to do; you only need to modify the tree type declaration in the binary tree module. Do this, and then test the result by declaring let char_tree = addList emptyTree ['e';'b';'a';'f';'g'].

4) You will now use the binary tree module for a totally different purpose. Your next task is to create a simple calculator, using your generic binary tree to represent arithmetic expressions. Create a new module for the calculator. We will revisit this calculator in L4, keep that in mind.

You do not need to make an interactive program where the user can dynamically construct and evaluate expressions: the below is sufficient.

4.1 Declare a data type for arithmetic (floating-point) operators and operands. The data type declaration given for arithmetic expressions in lecture F6 should not be copied. Instead, consider how your data type for operators and operands can be used with the generic trees in the tree module to represent arithmetic expressions.

Your calculator should support the four basic arithmetic operators: addition, subtraction, multiplication and division. The operands will be floating-point numbers only.

4.2 Implement the function Op that takes an operator and two subtrees as input and returns an expression tree. Consider how operands should be handled, that is, how can we construct a subtree (a leaf?) that represents an operand? Note: it is not necessarily a requirement that Op should handle such a construction.

4.3 Implement the function Eval that takes an expression tree as input, evaluates it and returns the computed floating-point value.

4.4 Extend your calculator with the ability to compute the greatest common divisor (GCD) of two positive integers. Implement the function GCD using recursion.

Hint: Euclid's algorithm is an efficient, recursive algorithm to compute the CGD of two numbers that has been known for more than 2000 years. Already the old Greeks knew recursion...

It's sufficient to construct static expressions that demonstrate program functionality for tasks 4.2, 4.3, and 4.4. However, do keep an eye out for special cases, i.e., divison by zero.


Björn Lisper
bjorn.lisper#mdh.se