Thinking in Types

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.

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:

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:

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:

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 Strings by implementing an instance of Show for Person:

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.

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.

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

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

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:

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.

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.

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.

Let’s test this thing out.

main = do
    -- ...

    renderAll [ball, playerOne, playerTwo]

/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]

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.

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:

data Game = Game Ball Player Player

A Game consists of a Ball and two Players. As a trade-off, we could’ve also specified a Game as a Ball and list of Players. 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:

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 and does its best to minimize the impact of the Expression Problem. Extending our game can occur in a number of flexible ways.

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

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.

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

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.
• Want to learn more about type classes in particular? Check out this talk. Type classes come in around minute 40.