CSE 320: Programming Languages @ CSU, San Bernardino
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.
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” (
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.
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 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
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 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 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
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 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 is the opposite of
Show turns a value of some type into a
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
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
maxBound return the largest possible and smallest possible value of the implementing type, respectively.
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
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 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
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
Fractional is used for fraction-like types, and looks (roughly) like this:
class Num a => Fractional a where (/) :: a -> a -> a
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)
deriving (Show) part tells the Haskell compiler to attempt to automatically generate an implementation of
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.
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!