Introduction to Functional Programming – Exercises Week 6: "Recursive Datatypes and Datastructures"TDA555 / DIT440, LP1, HT2013
Home | Schedule | Labs | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2012
Here are some exercises designed to help you practice programming with data structures and higher-order functions.

Please prepare yourself for these exercises by printing them out, and also printing out the code samples and documentation that is referred to by links.

If you do not have time to do all these exercises, don't worry. The exercises are intended to provide enough work to keep the most experienced students busy. If you do all exercises marked with an (*) you have probably understood this week's material.

Good luck!

0 (*). Exercises (taken from the old book)

Expressions

Take a look at the following datatype:

  data Expr = Num Int
            | Add Expr Expr
            | Mul Expr Expr

A. Define a function size :: Expr -> Int that counts the number of operators in an expression.

B. Add Sub (subtraction) and Div (integer division) to the datatype Expr and modify the functions eval, show, and size accordingly. What do you in eval when you divide by 0?

C. Implement one version of eval with the result type Maybe Int. (You return Nothing when division by 0 occurs somewhere in the expression.)

Integer Trees

Take a look at the following datatype:

  data Tree = Leaf Int
            | Split Tree Tree

D. Implement a function collapse :: Tree -> [Int] that returns all integers in a given tree as a list, in the same order as they occurred in the tree.

E. Implement a function mirror :: Tree -> Tree that mirrors a tree (i.e. swaps the left and right subtrees everywhere).

F. State a QuickCheck property that expresses what happens when a tree is mirrored twice.

G. State a QuickCheck property that expresses the relationship between mirror, collapse and reverse.

(In order to be able to test your properties, you have to make Tree an instance of Arbitrary.)

1 (*). Tables

Recall the type Table from the lecture:
  data Table a b = Empty | Join (Table a b) a b (Table a b)
Write a function:
  build :: Ord a => [(a,b)] -> Table a b
That, given a list of pairs, builds the corresponding table. Try to make the resulting table as balanced as possible (each left and right subtree should be approximately equally big).

Now, write QuickCheck properties that check the behavior of this function. This will involve the definition of a function invariant :: Ord a => Table a b -> Bool.

Hint: Use the functions sortBy and nubBy from the Data.List module.

2 (*). File Systems

A file either contains data or is a directory. A directory contains other files (which may themselves be directories) along with a name for each one.

A. Design a data type to represent the contents of a directory. Ignore the contents of files: you are just trying to represent file names and the way they are organised into directories here.

B. Define a function to search for a given file name in a directory. You should return a path leading to a file with the given name. Thus if your directory contains a, b, and c, and b is a directory containing x and y, then searching for x should produce b/x.

3 (*). Simple Sets

(a) Design a datastructure for sets . I.e. there should be a type Set a, and a number of functions for creating, combining, and investigating sets. There should at least be a function to create an empty set, add an element to a set, take the union of two sets, remove an element from the set, and check if an element is in the set.

(b) Now, implement the Set datastructure. You may use lists internally.

(c) Specify properties for your Set functions, relating it to a simple specification implementation. There should be a property that specifies the behaviour for each of your functions. You should also define a generator for your sets.

Do not forget to specify an invariant for your datatype! Check that all your generated sets satisfy the invariant. There should also be a property that checks that the invariant is maintained for each of your functions.

(d) Add mistakes to your implementation, and check if these are caught by your properties.

4. Sorted Sets

Redo the above exercise, but now use sorted lists of unique elements as your internal representation. Set union becomes more efficient that way.

Make sure all your properties are OK!

5. Tree Sets

Redo the above exercise, but now make use of the same principle behind the lookup tables. Set membership checking becomes more efficient that way.

Make sure all your properties are OK!