Latest update April 19, 2015.

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

**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:

`Leaf`- Takes an integer, and returns a leaf containing this integer.`buildTree`- Takes two subtrees and an integer, and returns a tree with the integer as root and the subtrees as its children.`isLeaf`- tests if the argument is a leaf.`head`- returns the integer stored in the root (which may be a leaf).`left`- For a non-leaf, returns the left subtree.`right`- For a non-leaf, returns the right subtree.

`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:

`add`- Takes a (sorted) tree and an integer, and returns a tree with the integer sorted into to the argument tree.`addList`- Instead of a single integer, this function takes a list of integers and inserts them in the tree.

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.

bjorn.lisper#mdh.se