CSE 320: Programming Languages @ CSU, San Bernardino

Go back to home page

Lab #2: Typeclasses

This lab is intended to introduce you to the concept of typeclasses, how they can be used to make generic types and generic functions, and to learn about the design and usefulness of interfaces combined with parametric polymorphism.

If at any point you find something confusing, feel free to ask questions about it.

Generic Parameters

In the last lab, we saw some functions that took a generic parameter, like so:

generic :: [a] -> Int
generic l = length l

But we didn’t talk very much about it. This generic function signature means that generic can take in a list of any single type. The function is generic over the type of the values in the list.

So any of the following uses of the function will work:

generic [1, 2, 3]
generic ['a', 'b', 'c']
generic [1.0, 2.0, 3.0]

Even cooler, there’s no overhead (no performance cost at runtime) for this generic function! When the program is compiled, the compiler looks at all the “call sites” (places in the code that call generic) and sees the “concrete types” (Int, Char, Float) being passed, and it generates separate copies of generic for each concrete type. This process is called “monomorphization.”

So the above code gets turned into something like this:

genericInt :: [Int] -> Int
genericInt l = length l

genericChar :: [Char] -> Int
genericChar l = length l

genericFloat :: [Float] -> Int
genericFloat l = length l

genericInt [1, 2, 3]
genericChar ['a', 'b', 'c']
genericFloat [1.0, 2.0, 3.0]

This is monomorphization, and it’s one of the things that makes Haskell’s implementation of generics parameters so cool!

Now, when I say “generics,” I actually mean “parametric polymorphism.” Parametric polymorphism means that the function is “polymorphic” (many forms) with respect to its parameters. So you can pass parameters of different types, and the function handles them correctly. Parametric polymorphism is the technical term, but you’ll often see this called “generics” in the real world, so it’s good to know both.

Interfaces

Now, wouldn’t it be nice if we could put some constraints on the generic parameters to our functions? What if we want to say “this function takes any type that implements addition”? This would be a really powerful feature. In essence, we want to be able to constrain the generic parameters by requiring that they implement a particular interface. In Haskell, we can do that! With something called “typeclasses.”

A typeclass in Haskell looks like this:

class Add t where
    plus :: t -> t -> t

This defines a typeclass called Add. Add is an interface that types can implement, with only a single function it requires, called plus. Here’s an example implementation:

data Intish = Intish Integer

instance Add Intish where
    plus :: Intish -> Intish -> Intish
    plus (Intish i) (Intish j) = Intish (i + j)

This defines a type Intish that is just a wrapper around an Integer, and implements Add for it by just adding the internal integers together.

So now, if we have a function where we want the input type to implement Add, we write it like so:

blah :: (Add a) => a -> a -> a
Blah x y = plus x y

This signature says that blah takes in two parameters of the same type, which implements Add, and returns a result of that type. Inside the function body, it calls plus, which is provided by the Add interface.

And that’s how typeclasses work! Pretty cool right?

Write your own typeclass, write a type that implements it, and write a function that’s generic over it. Make sure the code compiles, and save it in a .hs file for submission at the end of the lab.

Important Haskell Typeclasses

Typeclasses are a major mechanism within Haskell (in fact, they’re probably Haskell’s core feature, outside of laziness and purity). As such, Haskell comes with a collection of built-in typeclasses you can and should use with your own types. They are as follows:

Eq

The Eq typeclass is used for types that can be compared for equality. It looks like this:

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

The first function is for comparing whether two instances of the implementing type are equal. The second function is for comparing whether they’re not equal. You only need to implement one, as the other is automatically derived in terms of the one you implement.

Ord

The Ord typeclass is used for types that can be compared for an ordering. It looks like this:

data Ordering = LT | GT | EQ

class Eq a => Ord a where
    compare :: a -> a -> Ordering
    < :: a -> a -> Bool
    <= :: a -> a -> Bool
    > :: a -> a -> Bool
    >= :: a -> a -> Bool
    max :: a -> a -> a
    min :: a -> a -> a

The Eq a => Ord a means that a type has to implement Eq to implement Ord. And all the functions are what you’d expect them to be.

Show

The Show type class is used for types that can be converted into Strings. It looks (roughly) like this:

class Show a where
    show :: a -> String

There’s technically more to the definition of Show, but this is the part we care about.

Read

Read is the opposite of Show. Where Show turns a value of some type into a String, Read turns a String into a value of some type. It looks (roughly) like this:

class Read a where
    read :: String -> a

One thing to note is that this function does something we haven’t seen before. The generic type is the return type! This means that we have to give the compiler a bit of help with a type annotation when we call read, so it knows what type we’re trying to get out, and can thus choose the correct implementation of Read. That looks like this:

read "1" :: Int

Which says “call read with the parameter "1", and convert the result into an Int”.

Bounded

Bounded is used for types that have a maximum possible value and a minimum possible value. It looks like this:

class Bounded a where
    minBound :: a
    maxBound :: a

minBound and maxBound return the largest possible and smallest possible value of the implementing type, respectively.

Enum

Enum is for types that can be enumerated (that is, listed in their entirety). It looks (roughly) like this:

class Enum a where
    toEnum :: Int -> a
    fromEnum :: a -> Int

This definition may seem a bit strange, but it makes sense. Ints can be enumerated, and so the simplest way to define something that can be enumerated is to create some way to convert back and forth between that type and an Int. That’s what toEnum and fromEnum do.

Integral

Integral is used for integer-like types, and looks (roughly) like this:

class Enum a => Integral a where
    quot :: a -> a -> a
    rem :: a -> a -> a
    div :: a -> a -> a
    mod :: a -> a -> a

quot performs integer division, returning the whole portion without remainder. rem performs integer division, returning the remainder only. div performs integer division truncated down. mod performs integer modulus.

Num

Num is used for numbers, and looks (roughly) like this:

class Num a where
    (+) :: a -> a -> a
    (-) :: a -> a -> a
    (*) :: a -> a -> a
    negate :: a -> a
    abs :: a -> a
    signum :: a -> a

So Nums are types that can be added, subtracted, multiplied, negated, and from which you can get the absolute value and a number indicating the sign (either -1, 0, or 1).

Fractional

Fractional is used for fraction-like types, and looks (roughly) like this:

class Num a => Fractional a where
    (/) :: a -> a -> a

So Fractionals are Nums that also support real division.

So Many Typeclasses!

That’s a lot of typeclasses! Fortunately, they’re pretty easy to remember.

Write some types of your own, and implement every type class listed above at least once. Save your work in a .hs file, make sure it compiles, and turn it in at the end of the lab.

A Convenient Shorthand

Now, it would be a real pain to always have to manually implement these type classes. Fortunately, many typeclasses in Haskell can be automatically derived in the following way.

data Blah Int = Blah Int deriving (Show)

The deriving (Show) part tells the Haskell compiler to attempt to automatically generate an implementation of Show for Blah.

Write five types for which you collectively derive at least once all the typeclasses listed above which can be derived. Take note of which ones can’t be derived. Save your work in a .hs file for submission at the end of the lab. Make sure it compiles.

Conclusion

Typeclasses are an excellent mechanism for writing generic code. By separating out your interfaces and combining them with the power of parametric polymorphism, you gain a simple, flexible, and powerful mechanism for writing generic code that works not only with the types you are aware of right now, but with future types which may be added to the code.

That’s it for the lab. Make sure to submit what you have for grading!