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.
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 ...
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.
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.
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:
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.)
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.
Please have answers to the above exercises ready for the next lab session on Wednesday 6 April.