---
title: Thinking in Types
teaser: |
  A programming language with a type system can help you
  design abstractions and avoid mistakes.
tags: web,haskell
author: Pat Brisbin
published_on: 2014-05-02
---

A colleague of mine was stuck attempting to do something in Haskell that seemed
conceptually simple but resulted in a type error. While a particular form of
polymorphism, common in object-oriented languages, translated very well to
Haskell, a related technique was not permitted by the language's type system.

In this post, I'd like to outline a simplified version of the task and how this
limitation was overcome. Hopefully you'll see that by working with the type
system rather than against it, we find unexpected benefits in the resulting
design.

## The Task

The system my colleague was building models a [Pong]-like game. There
are two players and a ball, all of which need to be rendered on screen.
We're going to avoid any discussion of the graphics library used to
accomplish this and focus only on the task of flexibly sharing this
behavior across the two kinds of objects we have in our domain. This
simplification should allow the Haskell examples to make sense to
someone not familiar with the language.

[pong]: http://en.wikipedia.org/wiki/Pong

This task is well-suited to polymorphism with an object-oriented slant.
We could define some *Renderable* interface and have our two object
types (presumably `Ball` and `Player`) conform to that interface. This
way, we can simply tell an object, whatever it is, to render itself.

In Ruby, we can do this easily with duck typing; there is no safety but
it is concise and flexible. In Java, we could define an actual
`Interface` and get some form of type checking. Things would be a bit
safer but also very verbose.

This approach translates well to Haskell thanks to a feature called
*type classes*. They provide a concise, flexible, and completely type
safe way to define interfaces which multiple types can implement. In
order to understand the problem I want to discuss, we'll need to digress
just a little and explain what these are and how they work.

## Type Classes

A type class defines a set of functions which must be implemented for a
type to be considered *in* that type class. Other functions can then be
written which operate not on one specific type, but on any type which is
in its given *class constraint*.

An example should help.

For a type to be *Showable* or *in the `Show` type class*, we have to
define how to represent it as a `String`. Here is how the desired
interface is described:

```haskell
class Show a where
    show :: a -> String
```

It's common to represent "any type" with the variable `a`. The above
declaration states that for some type `a` to be in the `Show` class, you
must define the function `show` which takes that type as argument and
returns a `String`.

Imagine we declare a type representing people by their age and name:

```haskell
data Person = Person Int String
```

A value of type `Person` can be built by giving an `Int` (their age) and
a `String` (their name) to the *constructor* also called `Person`. It's
common to use the same word for the type and the constructor since there
is no ambiguity when either is used. It would've also been fine to say:

```haskell
data Person = BuildPerson Int String
```

But this is uncommon in cases where there is only one constructor.

Now that we have all of these people in our domain, we can specify how
to represent them as `String`s by implementing an *instance* of `Show`
for `Person`:

```haskell
instance Show Person where
    show (Person age name) = name ++ ", " ++ show age ++ " years old"
```

The left hand side uses [pattern matching] to take a value of type
`Person` and bind the individual components to the variables `age` and
`name` which we can then use in the function body.

[pattern matching]: http://en.wikipedia.org/wiki/Pattern_matching

It's now possible for our type to be used by functions which care only
that they're given a type with an instance for `Show`. One such function
is `print`. Its type signature specifies a *class constraint* to the
left of the `=>` allowing the use of `show` in the function body.

```haskell
print :: Show a => a -> IO ()
print x = putStrLn (show x)
```

We could use all of this in a Haskell program like so:

```haskell
main = print (Person 29 "Pat")
```

As you might have guessed, this program would print `Pat, 29 years old`
to your terminal.

## Renderable

With all that fresh Haskell knowledge, we can now speak to the actual
problem at hand.

Using `Show` as an example, we can define our own type class:

```haskell
class Render a where
    render :: a -> IO ()
```

This states that any type `a` can be made renderable by defining the
function `render` which takes that type as argument and does whatever is
required to render it on screen. Much like `print`, this would be an
`IO` action. The details of IO in Haskell and the actual meaning of `IO
()` are very interesting topics, but well outside the scope of this
post.

Presuming we have the types `Ball` and `Player` in our system, we can
make an instance of `Render` for each.

```haskell
data Ball = Ball

instance Render Ball where
    render ball = do
        -- whatever

data Player = Player

instance Render Player where
    render player = do
        -- whatever
```

By implementing an instance for both types currently in our domain, we
can now write functions which don't care if they're given a `Ball` or
`Player`, they simply need something that can be rendered.

```haskell
renderAll :: Render a => [a] -> IO ()
renderAll rs = mapM_ render rs
```

We need to use `mapM_` here in place of the `map` you might expect
because of the `IO` involved. This detail can be safely ignored, but I
direct any curious readers to the [docs][mapM].

[mapM]: http://hackage.haskell.org/package/base-4.7.0.0/docs/Prelude.html#v:mapM_

Let's test this thing out.

```haskell
main = do
    -- ...

    renderAll [ball, playerOne, playerTwo]
```

<pre>
<samp>/home/patrick/test.hs:4:22:
    Couldn't match expected type `Ball' with actual type `Player'
    In the expression: playerOne
    In the first argument of `renderAll', namely `[ball, playerOne, playerTwo]'
    In the expression: renderAll [ball, playerOne, playerTwo]</samp>
</pre>

Uh-Oh.

## The Problem

The reason this is an error is because Haskell does not allow
heterogeneous lists. In other words, all elements in a list must be of
the same type. We might consider this list of game elements as
homogeneous because they are all *renderable*. In a language like Ruby
or Java, this code would work fine. In Haskell, we have a much stricter
type system and even though these values share an interface, they are
not the same type.

This is where my colleague got stuck and asked me the question which
sparked this blog post. It is a very common question for those learning
a new language to ask those that already know it:

> How do I do X in language Y?

In this case, X was "heterogeneous lists" and Y was "Haskell".

I gave him what is probably the most common response to such questions:

> Why on earth do you want to do X?

In actuality, there are a few [approaches] for doing heterogeneous lists
in Haskell. However, I don't think this is a good use case. We can get
around this problem in a cleaner and safer way by using the type system
rather than subverting it.

[approaches]: http://www.haskell.org/haskellwiki/Heterogenous_collections

## Thinking in Types

A list of a specific type is suitably descriptive, *you have many Foos*.
However, if you find yourself attempting to put objects of different
types into a single list you lose any descriptiveness. Even if the
language allowed it, all you'd have is a blob of generic *things* with
no sense of what those things represent when taken together.

As one solution to this problem, I would define a type to play the role
of what is currently that nondescript list. This adds shape and safety
to our program:

```haskell
data Game = Game Ball Player Player
```

A `Game` consists of a `Ball` and two `Player`s. As a trade-off, we
could've also specified a `Game` as a `Ball` and list of `Player`s. This
would be more flexible, but less safe since it would make it possible to
create a game with the wrong number of players. Haskell's type system
shines best when you encode as many invariants as possible within the
types themselves. It's impossible to run a Haskell program with a type
error, so it follows that any logic encoded in those types is
**guaranteed** correct. This is why we hear that Haskell reprise *if it
compiles, it works*.

While any technique that reduces the possibility of certain bugs is a
very real and tangible benefit, moving from a generic list to a more
structured type has many other advantages. The code is easier to read
and understand when you group data in a structured type rather than an
opaque list. We can also extend our system by adding behavior around
this data type specifically. Those behaviors will also be easier to
understand because their arguments or return values will be of a more
structured and well-understood type.

## Composite

The next change motivated by this type is turning `renderAll` into
`renderGame` --but wait-- that could just be `render`:

```haskell
instance Render Game where
    render (Game b p1 p2) = do
        render b
        render p1
        render p2

main = do
    -- ...

    render game
```

What we have now is a form of the [Composite] pattern: a compound
value indistinguishable from its individual parts (at least when it
comes to rendering). By using type class polymorphism and this composite
data type, our system more closely follows [Open/Closed][ocp] and does
its best to minimize the impact of the [Expression Problem][expr].
Extending our game can occur in a number of flexible ways.

[composite]: http://en.wikipedia.org/wiki/Composite_pattern
[ocp]: http://en.wikipedia.org/wiki/Open/closed_principle
[expr]: http://en.wikipedia.org/wiki/Expression_problem

For example, we could extend the `Game` type and its instance with
another record of some renderable type:

```haskell
data Game = Game Ball Player Player Score

instance Render Game where
    render (Game b p1 p2 s) = do
        render b
        render p1
        render p2
        render s
```

If we're careful in our module exports, a change like this can be done
in a backward-compatible way. Such an approach is outlined [here].

[here]: http://www.yesodweb.com/blog/2011/10/settings-types

If for whatever reason we cannot change `Game`, we may choose to extend
our Composite another layer:

```haskell
data ExtendedGame = ExtendedGame Game Score

instance Render ExtendedGame where
    render (ExtendedGame g s) = do
        render g
        render s
```

Hopefully this post has shown that a strong static type system is not
some evil thing to be avoided. It can help guide you in designing
abstractions and ensure you don't make mistakes. Languages like Haskell
embrace this idea and make it easy to utilize to great effect. I hope
you found it as interesting as I did to see how a small shift in
thinking can not only work around a "limitation" but also improve the
code you write.

## What's next

* Interested in learning some Haskell? Start with [Learn you a
  Haskell][lyah].
* Want to learn more about type classes in particular? Check out [this
  talk][talk]. Type classes come in around minute 40.

[lyah]: http://learnyouahaskell.com/
[talk]: http://yow.eventer.com/events/1004/talks/1054