Lab #7: Classes, instances and IO

Assigned: Wed 30 Mar 2005
Due: Wed 6 Apr 2005

These exercises are concerned with a couple of new language features in Haskell, classes and instances; they also introduce Haskell's IO (input/output) facilities. Between them, these features will form the basis for our investigation of Haskell's notion of a monad, an idea with important theoretical origins, but also very practical uses in Haskell.

For background on these features, read the textbook on pages 31-33, 39, 76-80 and Chapter 10 (which discusses IO). I will also give some background on these ideas in lecture and lab.

Note that classes and instances in Haskell correspond very roughly to interfaces and implementations (keyword "implements") in Java (this intuition may help you understand how they are used in structuring larger programs and libraries).

Hey!: here is some test data for Tree and BTree equality.

This week's exercises

1. Consider the BTree data structure defined in Lab 5. You defined a function mapbt for BTrees; this means that BTrees are eligible for an instance of the Functor class (see this reference).

   Make instances of both the Functor and Eq classes for BTrees.

   Note that you actually have to write a new function in the second case; also, you will want to use a "conditional" form for the instance as follows:

   instance Eq a => Eq (BTree a) where ...

2. Consider the Tree data structure defined in Lab 5 (the one using a Spread of multiple children), and recall especially the program you wrote there to display trees as outlines.

   Make Trees an instance of the Show class by defining their default printing to be in the form of the outline.

   Test out your definition by cutting and pasting in the sample "dog tree" from the lab and noting how it looks now.

3. Consider multi-branch Tree structures again: in many cases, we might want to think of the children of a Spread node to be ordered (e.g., "left to right"). For some applications, however, it would be desirable to think of the children as unordered, i.e., as being a set of children rather than a list. Of course, we still need to represent the children using some concrete data structure such as a list, so we will leave the definition the same, but the change in perspective about ordering would affect some functions we define on Trees.

   For example, we have often used Haskell's deriving feature to automatically derive an equality operation on data structures we define. For Trees, the automatically defined one will consider two Trees to be equal if (and only if) they have the same children in the same order. If we think of the children as an unordered set, it makes sense to define equality on Trees so that as long as two Trees have the same set of children (and of course the same root node value), independent of their order, then they are considered equal.

   Using a definition of Trees without an automatically derived Eq instance, define an instance of Eq for Trees which respects a notion of sets of children. You will need to use a "conditional" instance as for BTree quality above; you will also (of course) need to figure out how to make the equality test insensitive to the order of sub-trees.

4. We have used several kinds of tree data structures, as well as Haskell's built in lists, in our lectures, labs and exams. In each case, we have looked at several similar functions definable on these data structures, including maps, zips, folds, size, flatten (i.e., convert to a list of items), etc.

   Rather than coming up with new names for each of these functions in each instance, we can capture the basic ideas in a class definition. Write such a class definition, calling it Structure, so that it includes each of the following functions:

   • a size function which takes a structure and returns how many items there are in it;

   • a depth function which takes a structure and returns an integer representing its depth, i.e., the longest "chain" of nested constructors contained in the structure;

   • an unzip function which takes a structure of pairs and returns a pair of structures;

   • a flatten function which takes a structure and returns a list of items (choose either depth-first/pre-order or breadth-first order for the items).

   Using the "conditional" class syntax as in the equality examples above, make sure that every instance of the Structure class which you define must also be an instance of the Functor class, so that it will have an fmap defined for it. (In essence, this makes Structure a sub-class of the Functor class.)

5. Define two instances of the Structure class above, choosing from among Haskell's pre-defined lists and any of the other tree-like structures we have defined this semester.

6. There is no easy way to include a fold function in the above class for Structures; explain why.

7. The Haskell Prelude function interact allows us to take any function from Strings to Strings and turn it into an interactive function which reads input from the user and then prints back outputs to them.

   Define an IO-style function using interact which will repeatedly read in "lists" of integers and print out their average. Note that the input should not require the usual Haskell list syntax; that is, the numbers should simply be separated by spaces on a line.

8. The Haskell Prelude functions readFile and writeFile allows us to read and write files as (long) strings. Using these functions, and techniques discussed in Chapter 10 of the textbook, write a function (or command) which will read in a file and write it out (say to a new filename with "rev" appended to the name) in reverse order, at both the level of lines and the level of characters. In other words, the lines of the new file should be those of the old file in reverse order, and each line should also itself be in reverse order.

Please have answers to the above exercises ready for the next lab session on Wednesday 6 April.