Data Types and Typeclasses

1 Natural numbers recommended atHome

Consider the set of natural numbers \(\mathbb{N}\), and observe that:

• zero is a natural number, and
• any other natural number is the successor of some other natural number.

1. Define a data type Nat representing natural numbers using the above observation.

2. Write functions toInt :: Nat -> Int and fromInt :: Int -> Nat that allows you to convert between Nat and Int.

2 atHome

Give a direct definition of the < operator on lists. This definition should not use operators like <= for lists.

When trying out this definition using ghci, do not use the < symbol, since it is already defined in the Prelude.

3 Complex numbers recommended atHome

1. Write a data type Complex to represent complex numbers. A complex number is defined as a pair of real numbers \(a\) and \(b\), and is written as \(a + b*i\).

2. Make Complex an instance of Show, Eq, and Num (write the instances explicitly rather than deriving them). For more information about operations on complex numbers, see Wikipedia.

4 Bikes atHome

1. Define data types that model the following situation as precisely as possible:

   A bikeshop sells three kinds of bikes: city bikes, road bikes and mountainbikes, in three different sizes. In most cases, bike sizes are standardized into (small, medium, and large), however it is also possible for bikes to have a custom (integral) size (the size of the frame in inches). The mountainbikes and road bikes have gears. They have a cassette with many cogs on the rear wheel, and some of them may have a second chainring in the front (doubling the number of available gears). City bikes do not have gears. However, unlike the other types of bikes they have fenders either in the front, the back, or on both wheels). Fenders themselves come in two types; they are either made from plastic or metal.

2. Consider a function getFenders that returns the fenders of a bike, if it has any. What would be a good type for this function?

3. Write the function getFenders

4. Write a function byGears that lists all bikes available in the bikeshop, ordered by number of gears.

5 Sets atHome

1. Define a type Set a whose values represent sets of elements of type a, and define a function subset :: Eq a => Set a -> Set a -> Bool which checks whether all the elements in the first set also belong to the second.

2. Use the subset function above to define an Eq instance for Set a.

3. Why do we have to define Set a as its own data type, instead of an alias over [a]?

6 Implementing the Eq type class atHome

Recall that there is an Eq typeclass which expresses that some type a has a notion of equality. In particular, it can be defined as:

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x /= y = not (x == y)

Give explicit Eq instances for the following types. Your implementations should have the same behavior as the “default” behavior that one would get by deriving Eq for these types.

1. The StandardSize and BikeSize types defined above.

2. The Maybe a type

3. The [a] type

4. The Either a b type, which can be defined as

   data Either a b = Left a | Right b

7 Finite atHome

Define a class Finite. This class has only one method: the list of all the elements of that type. The idea is that such list is finite, hence the name. Define the following instances for Finite:

• Bool.
• Char.
• (a, b) for finite a and b.
• Set a, as defined in the previous exercise, when a is finite.
• a -> b whenever a and b are finite and a supports equality. Use this to make a -> b an instance of Eq.

8 Lines recommended atHome

Given the data types

data Point = Point Float Float -- Point x y is the point with coordinates (x, y) in the plane
data Vector = Vector Float Float -- Vector dx dy is the 2d vector in the direction (dx, dy)
data EqLine = EqLine Float Float Float -- EqLine a b c represents the line a * x + b * y + c = 0
data VectLine = VectLine Point Vector -- VectLine p v represents the line through p in the direction v 

define a class Line whose instances l implement a method that calculates the distance from an l to a Point and a method vshift that shifts the line vertically by a Float offset.

Please make EqLine and VectLine instances of Line.

Can you think of any more, different representations for lines? If so, please implement them as a datatype and make them an instance of Line.

Can you think of any more things we can compute for any line? Please add them as methods in the definition of Line. Can you give some of them default implementations?

9 atHome challenging

We can use a type class

class DGraph g where
    succs :: Eq a => g a -> a -> [a]

for representing directed graphs. The idea is that a is a type of vertices, that g a is the type of directed graphs with vertices of type a and succs someGraph aVertex gives the list of all successors of aVertex :: a in the graph someGraph :: g a.

We can define types

newtype PList k v = PList {keyValues :: [(k, v)]}
newtype SMPList k = SMPList (PList k [k])

data RoseTree l = RoseTree l [RoseTree l]
newtype FRoseTree l = FRoseTree [RoseTree l]

SMPList and FRoseTree give two different representations of directed graphs. For example, the graph

can be represented as

dgraph1SMPL = SMPList $ PList [(1, [2, 3]), (2, []), (3, [2, 4]), (4, [3])]
dgraph1FRT = FRoseTree [one] where 
  one = RoseTree 1 [two, tree]
  two = RoseTree 2 []
  three = RoseTree 3 [two, four]
  four = RoseTree 4 [three]

To warm up, please implement the graph

in both representations.

Please make SMPList and FRoseTree instances of DGraph.

Can you come up with any more different representations of directed graphs? Please implement them as parameterised datatypes and make them an instance of DGraph. To practice some more, you can implement your favourite directed graph (for example one of the two above) in your new representations.

We want to write a function maxPaths that takes a directed graph someGraph – it should accept any representation – and a list inits of vertices as inputs and produces a list of all maximal directed paths, i.e. directed paths that cannot be made longer, in someGraph that start from a vertex i in inits. Please specify the type signature of maxPaths.

Now, please implement maxPaths. You may assume, for simplicity, that it is only ever used on directed graphs without cycles.

Can you come up with any more operations that we can perform on any directed graph?

Please add them to the type class and give their implementations. Can you use a default implementation?