Latest update Dec 3, 2023

Assignment 2

This assignment has several purposes. The first and second assignments give you some more training defining recursive functions over lists. The second assignment also gives you a first, simple exercise in defining higher-order functions. The third assignment provides training in defining data types for trees using recursive data type declarations. It also gives an exercise how to use modules to create an abstract data type, where a concrete data type is wrapped and access to it is given through a set of functions that provide an interface. In this way the concrete data type is hidden, and can be easily replaced with another data type that implements the same interface.

We recommend that you use the lab skeletons under DVA229Lab2/ in labs.zip as a template for your solutions below: List.fs for assignment 1) and 2), Tree.fs for assignment 3.1) - 3.2), and BST.fs for assignment 3.3) - 3.5). This will make it easier to use the FsCheck test functions.

Note: in assignment 1) and 2) below you are not allowed to use any builtin list functions, with one exception: you may use List.append (or @) when implementing union. The assignments are otherwise to be solved using recursion over lists.

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 a function that takes two lists of integers as arguments, and returns the union of the lists considered as sets. You will probably want to use the previously defined member function.

Example:

   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 function 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]

Is there a way to avoid defining the functions eq, lt, and gt, and instead use the operators =, <, and > directly in the calls to foo2? (Hint: F# has a way to turn infix operators into functions.)

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']

Test mem, union, foo1, foo2 using FsCheck with the corresponding test functions Lab2.List.mem, etc from DVA229Lab2/Test.fs in labs.zip!

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 empty, 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, and empty trees. They should have proper error-handling if given a leaf or empty tree 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 the functions in your newly created module for binary trees to implement the sorted 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 define three more functions:

Test sortList using FsCheck with the corresponding test function Lab2.BST.sortlist from DVA229Lab2/Test.fs in labs.zip! Make sure that your code passes all tests before handing in your solution.

Now you have two modules: one for general binary trees. and one for sorted binary trees. Each of them forms an abstract data type. The idea with abstract data types is to hide the underlying implementation: thus, an abstract data type always comes with an interface that provides the "right" way of accessing the data type. If the user code sticks to the interface, then that code does not have to be changed even if underlying implementation of the abstract data type is modified. This makes it much easier to update the software. Typically the interface consists of a set of functions accessing the underlying representation: for the tree data types, the interfaces consist of the functions listed in 3.2 (binary trees, sorted trees) and 3.4 (sorted trees).

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 some trees to use as test inputs. You could for instance add the following definition: let tree = insertList [2; 1; 6; 7] (leaf 5). You can then call the different functions from the interactive environment with tree as argument, for instance insert 8 tree.

(A more systematic approach would be to let FsCheck generate trees for testing some interesting properties, but this is not required for this assignment.)

3.5 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 = insertList ['e';'b';'a';'f';'g'] emptyTree.


Björn Lisper
bjorn.lisper (at) mdu.se