This Article is a reworked lesson from the upcoming Manning book, Learn Haskell, originally titled: Creating Types with “and” and “or”.
In this article we’re going to take a closer look at Haskell’s Algebraic Data Types. The key to understanding Algebraic Data Types is to understand how we can combine existing types to create new ones. Thankfully there are only two ways. We can combine multiple types with an “and” (for example, a name is a String and another String), or we can combine types with an “or” (for example, a Bool is a True data constructor or a False data constructor). Types that are made by combining other types with an ‘and’ are called Product types. Types combined using ‘or’ are called Sum Types. Most programming languages use Product types. Sum types, while conceptually simple, prove to be a remarkably powerful tool when it comes to modeling data. By the end of this article we’ll see how Sum types allow us to dramatically simplify the design of complex data.
Product Types — Combing types with ‘and’
Product types are created by combining two or more existing types with ‘and’. Some common examples are:
- A fraction can be defined as a numerator (Integer) and denominator (another Integer)
- A street address might be a Number (Int) and a Street Name (String)
- A mailing address might be a street address and a city (String) and a state (String) and a zip code (Int)
The name “Product type” might make this method of combining types sound sophisticated, but it’s the most common way to define types. Nearly all programming languages support Product Types. The simplest example is a struct from C. Here is an example of a struct in C for a book, which uses another struct for the author_name:
struct author_name {
char *first_name;
char *last_name;
};struct book {
author_name author;
char *isbn;
char *title;
int year_published;
double price;
};
In this example we see that the author_name type is made by combining two Strings (for those unfamiliar, char* in C is an array of characters). The book type is made by combining an author_name, two strings, an int and a double. Both author_name and book are made by combining other types with an ‘and’. C’s structs are the predecessor to similar types in nearly every language including Classes and JSON. In Haskell our book example would look like this:
data AuthorName = AuthorName String String
data Book = Author String String IntPreferably we’d use Record Syntax to write a version of Book even more reminiscent of the C struct:
data Book = Book
{author :: AuthorName
,isbn :: String
,title :: String
,year :: Int
,price :: Double }Both Book and AuthorName are examples of product types, and they’ve an analog in nearly every modern programming language. What’s fascinating is that, in most programming languages, combining Types with an ‘and’ is often the only way to make new types.
The curse of product types: Hierarchical design.
Making new types by combining existing types using “and” leads to an interesting model of designing software. Because of the restriction that we can only expand an idea by adding to it, we’re constrained with top down design, starting with the most abstract representation of a type we can imagine. This is the basis for designing software in terms of class hierarchies.
As an example, suppose we’re writing Java and we want to start modeling data for a Book Store. We start with our Book example above (assume the Author class already exists):
public class Book {
Author author;
String isbn;
String title;
int yearPublished;
double price;
}This works great until we realize that we also want to sell vinyl records in our book store. Our default implementation of a VinylRecord looks like this:
public class VinylRecord {
String artist;
String title;
int yearPublished;
double price;
}A VinylRecord is similar to our Book, but dissimilar enough that it causes us some trouble. For starters we can’t reuse our Author type. The reason for this is some artists don’t have names. We could use the Author type for “Elliott Smith”, but not for “The Smiths”. In traditional hierarchical design there’s no good answer to this issue regarding the Author and artist mismatch. Another problem is that VinylRecords don’t have an ISBN number.
From a design standpoint, we want a single type that represents both VinylRecords and Books, which would support a searchable inventory. The need to compose types using only “and” forces us to develop an abstraction that describes everything that records and books have in common. We then implement only the differences in the separate classes. This is the fundamental idea behind inheritance. We’ll next create a class StoreItem, which will be a super class of both VinylRecord and Book. Here is our refactored Java:
public class StoreItem {
String title;
int yearPublished;
double price;
}public class Book extends StoreItem{
Author author;
String isbn;
}public class VinylRecord extends StoreItem{
String artist;
}
This solution works. We can create code to work with StoreItems, and then use conditional statements to handle Book and VinylRecord.
Suppose we also ordered a range of collectible toy figurines to sell. Here’s the basic CollectibleToy class:
public class CollectibleToy {
String name;
String description;
double price;
}To make everything work we have to refactored all of our code again! Now StoreItem can only have a price attribute, because it’s the only value that all items share in common. This means that the common attributes between VinylRecords and Books have to go back into those classes. Alternately we could make some new class that inherits from StoreItem and is a super class of VinylRecord and Book. What about CollectibleToy’s name attribute, is that different than title? Maybe we should make an interface for all of our items instead! The point is that, even in relatively simple cases, designing in strictly product types can get complex quickly.
In theory creating class hierarchies is elegant and captures some abstraction about how everything in the world is interrelated. In practice creating even trivial class hierarchies is riddled with design challenges. The root of all these challenge is that the only way to combine types in most languages is with an “and”. This forces us to start from extreme abstraction and move downward. Unfortunately, real life is full of strange edge cases that make this more complicated than we’d like.
Sum types: Combining Types with ‘or’
Sum types are a surprisingly powerful tool given that they combine two types with “or”. Examples of combining types with “or” include:
- A die is either a 6-sided die or a 20-sided die
- A paper is authored by either a person (String) or a group of people ([String])
- A list is either an empty list ([]) or an item appended to another list (a:[a])
The most straightforward Sum type is Bool:
data Bool = False | TrueAn instance of Bool is either the False data constructor or the True data constructor. This can give the mistaken impression that Sum types are Haskell’s way of creating enumerated types that exist in many other programming languages. Here’s an example of where we can use Sum types to create a Name type. Notice that we’re able to model both the possibility of a name having a middle name and not. In most other language we would be force to assign a Null value to the case where the middle name was missing. With Sum types we can model each case distinctly:
type FirstName = Stringtype LastName = Stringtype MiddleName = Stringdata Name = Name FirstName LastName
| NameWithMiddle FirstName MiddleName LastName
In this example we’re able to use two different type constructors that can either be a FirstName consisting of two Strings, or a NameWithMiddle consisting of three Strings. Here using “or” between two types allows us to be expressive about what types mean. By adding “or” to the tools we use to combine types, we open up worlds of possibility in Haskell that aren’t available in any other programming language that lack Sum types. To see how powerful Sum types can be let’s resolve some of the issues in the previous section.
An interesting place to start is the difference between author and artist. In our example we needed two different types because the names of book authors can be assumed to be a first and last name, but an artist making records can be a person’s name or a band name. It’s tricky to resolve this problem with Product types alone. With Sum types we can tackle this problem rather easily. We can start with a Creator type, which is either an Author or an Artist (we’ll define these next):
data Creator = AuthorCreator Author | ArtistCreator ArtistWe already have a Name type that allows us to define Author as a name
data Author = Author NameAn artist is trickier because an Artist can be a person’s name or a band name. To solve this issue, we’ll use another Sum type!
data Artist = Person Name | Band StringThis is a good solution, but what about some of those tricky edge cases that pop up in real life? For example, we forgot about authors like H.P. Lovecraft! We could force ourselves to use “Howard Phillips Lovecraft”, but why force ourselves to be constrained by our data model; it should be flexible. We can easily fix this by adding another data constructor to Name:
data Name = Name FirstName LastName
| NameWithMiddle FirstName MiddleName LastName
| TwoInitialsWithLast Char Char LastNameNotice that Artist, Author and, as a result Creator, all depend on the definition of Name. We only had to change the definition of Name itself, and didn’t need to worry about how any other types using Name are defined. At the same time, we still benefit from code reuse, as both Artist and Author types benefit from having Name defined in a single place. As an example of all of this is our H.P. Lovecraft Creator type:
hpLovecraft :: Creator
hpLovecraft = AuthorCreator(Author
(TwoInitialsWithLast
'H' 'P' "Lovecraft"))Our data constructors may be a bit verbose, but in practice we’d likely make use of functions that would ‘abstract out’ much of this. Think of how this solution compares to one we’d create using hierarchical design forced by product types. From the hierarchical design standpoint we’d need to have a Name super class with only a last name attribute, because this is the only property all three types of name share. We’d need separate sub-classes for each of the three data constructors used. Even then a Name, such as “Louis C.K.”, with a last name as a char, would completely break our model. This is an easy fix with Sum types:
data Name = Name FirstName LastName
| NameWithMiddle FirstName MiddleName LastName
| TwoInitialsWithLast Char Char LastName
| FirstNameWithTwoInits FirstName Char CharThe only solution for the product type view would be to create a Name class with a growing list of unused attributes:
public class Name {
String firstName;
String lastName;
String middleName;
char firstInitial;
char middleInitial;
char lastInitial;
}This would require a lot of extra code to ensure everything behaved correctly. Additionally, we’ve no guarantees about our Name being in a valid state. What if all these attributes had values? A Java type checker can’t ensure that a Name object meets the constraints we’ve specified for names. In Haskell we know that only the explicit types we’ve defined exist.
Putting together our book store
Now let’s revisit our book store problem and see how thinking with Sum types can help. With our powerful Creator type in hand we can rewrite Book
data Book = Book
{author :: Creator
, isbn :: String
, bookTitle :: String
, bookYear :: Int
, bookPrice :: Double}We can also define our VinylRecord type
data VinylRecord = VinylRecord
{ artist :: Creator
, recordTitle :: String
, recordYear :: Int
, recordPrice :: Double}Now we can trivially create a StoreItem type
data StoreItem = BookItem Book | RecordItem VinylRecordOnce again we’ve forgotten about the CollectibleToy. Because of Sum types it’s easy to add this data type and extend our StoreItem type to include it:
data CollectibleToy = CollectibleToy
{ name :: String
, descrption :: String
, toyPrice :: Double}We can easily refactor StoreItem by just adding one more ‘or’
data StoreItem = BookItem Book
| RecordItem VinylRecord
| ToyItem CollectibleToyFinally, we’ll demonstrate how we can build functions that work on all of these types by writing a price function that gets the price of any item:
price :: StoreItem -> Double
price (BookItem book) = bookPrice book
price (RecordItem record) = recordPrice record
price (ToyItem toy) = toyPrice toySum types allow us to be dramatically more expressive with our types, yet still allowing us convenient ways to create groups of similar types.
