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 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
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.
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
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
String (their name) to the constructor also called
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
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
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
=> 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.
With all that fresh Haskell knowledge, we can now speak to the actual problem at hand.
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
render which takes that type as argument and does whatever is
required to render it on screen. Much like
IO action. The details of IO in Haskell and the actual meaning of
() are very interesting topics, but well outside the scope of this
Presuming we have the types
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
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]
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
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
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.
The next change motivated by this type is turning
renderGame –but wait– that could just be
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.