Although lists and tuples are useful, we'll often want to construct new data types of our own. This allows us to add structure to the values in our programs. Instead of using an anonymous tuple, we can give a collection of related values a name and a distinct type. Defining our own types also improves the type safety of our code: Haskell will not allow us to accidentally mix values of two types that are structurally similar but have different names.

For motivation, we'll consider a few kinds of data that a small online bookstore might need to manage. We won't make any attempt at complete or realistic data definitions, but at least we're tying them to the real world.

We define a new data type using the data keyword.

data BookInfo = Book Int String [String]
                deriving (Show)

The BookInfo after the data keyword is the name of our new type. We call BookInfo a type constructor. (As we've already mentioned, a type name, and hence a type constructor, must start with a capital letter.) The string Book is the name of the value constructor we'll apply to create a value of this type. (A value constructor's name must also start with a capital letter.)

Finally, the Int, String, and [String] that follow are the components of the type. A component serves the same purpose in Haskell as a field in a structure or class would in another language: it's a “slot” where we keep a value. (We'll often refer to components as fields.)

In this example, the Int represents a book's identifier (e.g. in a stock database), String its name, and [String] the names of its authors.

To make the link to a concept we've already seen, the BookInfo type contains the same components as a 3-tuple of type (Int, String, [String]), but it has a distinct type. We can't accidentally (or deliberately) use one in a context where the other is expected.

	Deriving what?
	We'll explain the full meaning of deriving (Show) later, in the section called “Show”. For now, it's enough to know that we need to tack this onto a type declaration so that ghci will automatically know how to print a value of this type.

We can create a new value of type BookStore by treating Book as a function, and applying it with arguments of types Int, String, and [String].

bookInfo = Book 31337 "Algebra of Programming"
           ["Richard Bird", "Oege de Moor"]

Once we've defined a type, we can experiment with it in ghci. We begin by using the :load command to load our source file.

ghci> :load BookStore
[1 of 1] Compiling Main             ( BookStore.hs, interpreted )
Ok, modules loaded: Main.

Remember the fpBook variable we defined? Here it is.

ghci> bookInfo
Book 31337 "Algebra of Programming" ["Richard Bird","Oege de Moor"]
ghci> :type bookInfo
bookInfo :: BookInfo

We can construct new values interactively in ghci, too.

ghci> Book 0 "The Book of Imaginary Beings" ["Jorge Luis Borges"]
Book 0 "The Book of Imaginary Beings" ["Jorge Luis Borges"]

The ghci command :type lets us see what the type of that expression is.

ghci> :type Book 1 "Cosmicomics" ["Italo Calvino"]
Book 1 "Cosmicomics" ["Italo Calvino"] :: BookInfo

To find out more about a type, we can use some of ghci's browsing capabilities. The :info command gets ghci to tell us everything it knows about a type.

ghci> :info BookInfo
data BookInfo = Book Int String [String]
  	-- Defined at BookStore.hs:2:5-12
instance Show BookInfo -- Defined at BookStore.hs:2:5-12

We can also find out why we use Book to construct a new value of type BookStore.

ghci> :type Book
Book :: Int -> String -> [String] -> BookInfo

We can treat a value constructor as just another function, one that happens to create and return a new value of the type we desire.

data BookReview = BookReview BookInfo Customer String

We can introduce a synonym for an existing type at any time, for example to give a type a more descriptive name. For example, the String in our BookReview type doesn't tell us what the string is for, but we can clarify this.

type ReviewBody = String

data BetterReview = BetterReview BookInfo Customer ReviewBody

The type keyword introduces a type synonym. The new name is on the left of the =, with the existing name on the right. The two names identify the same type, so type synonyms are purely for making code more readable.

We can also use a type synonym to create a shorter name for a verbose type.

type BookRecord = (BookInfo, BookReview)

A type synonym just creates a new name for a type. It does not do anything with the type's value constructors.

The familiar Bool is the simplest common example of a category of type called an algebraic data type. An algebraic data type can have more than one value constructor.

data Bool = False | True

The Bool type has two value constructors, True and False. Each value constructor is separated in the definition by a | character, which we can read as “or”: we can construct a Bool that has the value True, or the value False. When a type has more than one value constructor, they are usually referred to as alternatives or cases.

	Why “algebraic”?
	The use of the word “algebraic” for describing these data types comes from abstract algebra. Although the phrase “algebraic data type” is long, we're being careful to avoid using the acronym “ADT”. That acronym is already widely understood to stand for “abstract data type”. Since Haskell supports both algebraic and abstract data types, we'll avoid the acronym entirely.

Each of an algebraic data type's value constructors can take zero or more arguments. As an example, here's one way we might represent billing information.

type CardHolder = String
type CardNumber = String
type Address = [String]

data BillingInfo = CreditCard CardNumber CardHolder Address
                 | CashOnDelivery
                 | Invoice Customer
                   deriving (Show)

Here, we're saying that we support three ways to bill our customers. They can pay by credit card, if they supply a card number, the holder's name, and the holder's billing address. Alternatively, they can pay the person who delivers their shipment. Finally, we can send an invoice to the specified customer.

When we apply a value constructors to create a value of type BillingInfo, we must supply the appropriate arguments.

ghci> :type CreditCard
CreditCard :: CardNumber -> CardHolder -> Address -> BillingInfo
ghci> CreditCard "2901650221064486" "Thomas Gradgrind" ["Dickens", "England"]
CreditCard "2901650221064486" "Thomas Gradgrind" ["Dickens","England"]

ghci> Book 2 "The Wealth of Networks" ["Yochai Benkler"]
Book 2 "The Wealth of Networks" ["Yochai Benkler"]
ghci> (2, "The Wealth of Networks", ["Yochai Benkler"])
(2,"The Wealth of Networks",["Yochai Benkler"])

-- Cartesian (x and y) coordinates.
data Vector2D = Vector2D Double Double
                deriving (Eq, Show)

-- Angle and distance.
data Polar2D = Polar2D Double Double
               deriving (Eq, Show)

ghci> Vector2D (sqrt 2) (sqrt 2) == Polar2D (pi / 4) 2

<interactive>:1:30:
    Couldn't match expected type `Vector2D'
           against inferred type `Polar2D'
    In the second argument of `(==)', namely `Polar2D (pi / 4) 2'
    In the expression: Vector2D (sqrt 2) (sqrt 2) == Polar2D (pi / 4) 2
    In the definition of `it':
        it = Vector2D (sqrt 2) (sqrt 2) == Polar2D (pi / 4) 2

ghci> (sqrt 2, sqrt 2) == (pi / 4, 2)
False

  data ClockTime = TOD Integer Integer
       deriving (Eq, Ord)
      

Analogues to algebraic data types in other languages

Algebraic data types provide a single powerful way to describe data types. Other languages often need several different features to achieve the same degree of expressiveness. Here are some analogues from C and C++, which might make it clearer what we can do with algebraic data types, and how they relate to concepts that might be more familiar.

The structure

With just one constructor, an algebraic data type is similar to a tuple: it groups related values together into a compound value. It corresponds to a struct in C or C++, and its components correspond to the fields of a struct. Here's a C equivalent of the BookInfo type that we defined earlier.

struct book_info {
    int id;
    char *name;
    char **authors;
};

The main difference between the two is that the fields in the Haskell type are anonymous and positional.

data BookInfo = Book Int String [String]
                deriving (Show)

By positional, we mean that the section number is in the first field of the Haskell type, and the title is in the second. We refer to them by location, not by name.

In the section called “Pattern matching”, we'll see how to access the fields of a BookStore value. In the section called “Record syntax”, we'll introduce an alternate syntax for defining data types that looks a little more C-like.

The enumeration

Algebraic data types also serve where we'd use an enum in C or C++, to represent a range of symbolic values. Such algebraic data types are sometimes referred to as enumeration types. Here's an example from C.

enum roygbiv {
    red,
    orange,
    yellow,
    green,
    blue,
    indigo,
    violet,
};

And here's a Haskell equivalent.

data Roygbiv = Red
             | Orange
             | Yellow
             | Green
             | Blue
             | Indigo
             | Violet
               deriving (Eq, Show)

	Comparing for equality
	Notice that in the deriving clause for our Roygbiv type, we added another word, Eq. This tells the Haskell implementation to allow us to compare the values for equality.

ghci> :type Yellow
Yellow :: Roygbiv
ghci> Red
Red
ghci> Red == Yellow
False
ghci> Green == Green
True

In C, the elements of an enum are integers. We can use an integer in a context where an enum is expected, and vice versa: a C compiler will automatically convert values between the two types. This can be a source of nasty bugs. In Haskell, this kind of problem does not occur. For example, we cannot use a Roygbiv value where an Int is expected.

ghci> take 3 "foobar"
"foo"
ghci> take Red "foobar"

<interactive>:1:5:
    Couldn't match expected type `Int' against inferred type `Roygbiv'
    In the first argument of `take', namely `Red'
    In the expression: take Red "foobar"
    In the definition of `it': it = take Red "foobar"

The discriminated union

If an algebraic data type has multiple alternatives, we can think of it as similar to a union in C or C++. A big difference between the two is that a union doesn't tell us which alternative is actually present; we have to explicitly and manually track which alternative we're using, usually in another field of an enclosing struct. This means that unions can be sources of nasty bugs, where our notion of which alternative we should be using is incorrect.

enum shape_type {
    shape_circle,
    shape_poly,
};

struct circle {
    struct vector centre;
    float radius;
};

struct poly {
    size_t num_vertices;
    struct vector *vertices;
};

struct shape 
{
    enum shape_type type;
    union {
	struct circle circle;
	struct poly poly;
    } shape;
};

In the example above, the union can contain valid data for either a struct circle or a struct poly. We have to use the enum shape_type by hand to indicate which kind of value is currently stored in the union.

The Haskell version of this code is both dramatically shorter and safer than the C equivalent.

data Shape = Circle Vector Double
           | Poly [Vector]

If we create a Shape value using the Circle constructor, the fact that we created a Circle is stored. When we later use a Circle, we can't accidentally treat it as a Square. We will see why in the section called “Pattern matching”

Now that we've seen how to construct values with algebraic data types, let's discuss how we work with them. If we have a value of some type, there are two things we would like to be able to do.

Haskell has a simple, but tremendously useful, pattern matching facility that lets us do both of these things.

A pattern lets us peer inside a compound value and bind variables to the values it contains. Here's an example of pattern matching in action on a list: we're going to add all elements of the list together.

sumList (x:xs) = x + sumList xs
sumList []     = 0

It might initially look like we have two functions named sumList here, but Haskell lets us define a function as a series of equations: these two clauses are defining the behaviour of the same function for different patterns of input. On each line, the patterns are the items following the function name, up until the = sign.

To understand how pattern matching works, let's step through an example, say sumList [1,2]. Remember that the expression [1,2] is syntactic sugar for the expression 1:(2:[]).

When we first call sumList, the value we're matching is 1:(2:[]). We begin by trying to match the pattern in the first equation. In the (x:xs) pattern, the “:” is the familiar list constructor, (:). We're now using it to match with, not to construct a value. Our value was constructed using (:), so its constructor matches the constructor in the pattern. We say that the pattern matches, or that the match succeeds. The variables x and xs are “bound to” the constructor's arguments, so here x is given the value 1, and xs the value 2:[].

The expression we're now evaluating is 1 + sumList (2:[]). When we call sumList (2:[]), the value we're matching is 2:[]. Once again, this was constructed using (:), so the match succeeds: x is bound to 2, and xs to [].

Now we're evaluating 1 + (2 + sumList []). Haskell will only use the right hand side of an equation if it can match all of the patterns on the left. In our call to sumList [], the value we're matching is now []. The value's constructor does not match the constructor in the first pattern, so we don't use that equation's body. Instead, we “fall through” to the next pattern, which matches. The right hand side of this equation is thus chosen as the function's body.

The result of sumList [1,2] is thus 1 + (2 + (0)), or 3.

	Ordering is important
	As we've already mentioned, a Haskell implementation checks patterns for matches in the order in which we specify them in our equations. Matching proceeds from top to bottom, and stops at the first success. This means that equations below a successful match have no effect.

As a final note, there already exists a standard function, sum, that performs this sum-of-a-list for us. Our sumList is purely for illustration.

Construction and deconstruction

Let's step back and take a look at the relationship between constructing a value and pattern matching on it.

A value constructor builds a value. The expression Book 9 "Close Calls" ["John Long"] applies the Book constructor to the values 9, "Close Calls", and ["John Long"] to produce a new compound value.

When we pattern match against the Book constructor, we reverse the construction process. First of all, we check to see if the value uses that constructor. If it does, we inspect the compound value to obtain the individual values that we originally passed to the constructor when we created the value.

Let's consider what happens if we match the pattern (Book id name authors) against our example expression.

• The match will succeed, because the constructor in the value matches the one in our pattern.

• The variable id will be bound to 9'.

• The variable name will be bound to "Close Calls".

• The variable authors will be bound to ["John Long"].

Because pattern matching acts as the inverse of construction, it's sometimes referred to as deconstruction.

	Deconstruction doesn't destroy anything
	If you're steeped in object oriented programming jargon, don't confuse deconstruction with destruction! Matching a pattern has no effect on the value we're examining: it just lets us “look inside” it.

third (a, b, c) = c

complicated (True, a, x:xs, 5) = (a, xs)

ghci> :load Tuple.hs
[1 of 1] Compiling Main             ( Tuple.hs, interpreted )
Ok, modules loaded: Main.
ghci> complicated (True, 1, [1,2,3], 5)
(1,[2,3])

ghci> complicated (False, 1, [1,2,3], 5)
*** Exception: Tuple.hs:6:0-39: Non-exhaustive patterns in function complicated

bookID      (Book id title authors) = id
bookTitle   (Book id title authors) = title
bookAuthors (Book id titla authors) = authors

ghci> bookID (Book 3 "Probability Theory" ["E.T.H. Jaynes"])
3
ghci> bookTitle (Book 3 "Probability Theory" ["E.T.H. Jaynes"])
"Probability Theory"
ghci> bookAuthors (Book 3 "Probability Theory" ["E.T.H. Jaynes"])
["E.T.H. Jaynes"]

ghci> :type bookID
bookID :: BookInfo -> Int
ghci> :type bookTitle
bookTitle :: BookInfo -> String
ghci> :type bookAuthors
bookAuthors :: BookInfo -> [String]

nicerID      (Book id _     _      ) = id
nicerTitle   (Book _  title _      ) = title
nicerAuthors (Book _  _     authors) = authors

Exhaustive patterns and wild cards

When writing a series of patterns, it's important to cover all of a type's constructors. For example, if we're inspecting a list, we should have one equation that matches the non-empty constructor (:), and one that matches the empty-list constructor [].

Let's see what happens if we fail to cover all the cases. Here, we're deliberately omitting a match against the [] constructor.

badExample (x:xs) = x + badExample xs

If we call this with a value that it can't match, we'll get an error at runtime: our software has a bug!

ghci> badExample []
*** Exception: BadPattern.hs:4:0-36: Non-exhaustive patterns in function badExample

In this example, there's no equation in the function's definition that matches against the value [].

	Warning about incomplete patterns
	GHC provides a helpful compilation option, -fwarn-incomplete-patterns, that will cause it to print a warning during compilation if a sequence of patterns don't match all of a type's constructors.

If we need to provide a default behaviour in cases where we don't care about specific constructors, we can use a wild card pattern.

goodExample (x:xs) = x + goodExample xs
goodExample _      = 0

The wild card above will match the [] constructor, so applying this function does not lead to a crash.

ghci> goodExample []
0
ghci> goodExample [1,2]
3

Writing accessor functions for each of a data type's components can be repetitive and tedious.

nicerID      (Book id _     _      ) = id
nicerTitle   (Book _  title _      ) = title
nicerAuthors (Book _  _     authors) = authors

We call this kind of code boilerplate: necessary, but bulky and irksome. Haskell programmers don't like boilerplate. Fortunately, the language addresses this particular boilerplate problem: we can define a data type, and accessors for each of its components, simultaneously.

data Customer = Customer {
      customerID      :: Int
    , customerName    :: String
    , customerAddress :: Address
    } deriving (Show)

This is almost exactly identical in meaning to the following, more familiar form.

data Customer = Customer Int String [String]
                deriving (Show)

customerID :: Customer -> Int
customerID (Customer id _ _) = id

customerName :: Customer -> String
customerName (Customer _ name _) = name

customerAddress :: Customer -> [String]
customerAddress (Customer _ _ address) = address

For each of the fields that we name in our type definition, Haskell creates an accessor function of that name.

ghci> :type customerID
customerID :: Customer -> Int

We can still use the usual function call syntax to create a value of this type.

customer1 = Customer 271828 "J.R. Hacker"
            ["255 Syntax Ct",
             "Milpitas, CA 95134",
             "USA"]

Record syntax adds a more verbose notation for creating a value. This can sometimes make code more readable.

customer2 = Customer {
              customerID = 271828
            , customerName = "Jane Q. Citizen"
            , customerAddress = ["1048576 Disk Drive",
                                 "Milpitas, CA 95134",
                                 "USA"]
            }

When we define a type using record syntax, it changes the printed representation of the type's values.

ghci> customer1
Customer {customerID = 271828, customerName = "J.R. Hacker", customerAddress = ["255 Syntax Ct","Milpitas, CA 95134","USA"]}

For comparison, let's take another look at a value of the BookInfo type, which we defined without record syntax.

ghci> bookInfo
Book 31337 "Algebra of Programming" ["Richard Bird","Oege de Moor"]
ghci> :type bookInfo
bookInfo :: BookInfo

The accessor functions that we get “for free” when we use record syntax really are normal Haskell functions.

ghci> :type customerName
customerName :: Customer -> String
ghci> customerName customer1
"J.R. Hacker"

The standard System.Time module makes good use of record syntax. Here's a type defined in that module:

data CalendarTime = CalendarTime {
  ctYear                      :: Int,
  ctMonth                     :: Month,
  ctDay, ctHour, ctMin, ctSec :: Int,
  ctPicosec                   :: Integer,
  ctWDay                      :: Day,
  ctYDay                      :: Int,
  ctTZName                    :: String,
  ctTZ                        :: Int,
  ctIsDST                     :: Bool
}
    

In the absence of record syntax, it would take quite some effort to extract particular fields from a type like this. Records make it easy to work with this sort of data.

We've repeatedly mentioned that the list type is polymorphic: the elements of a list can be of any type. We can also add polymorphism to our own types. To do this, we introduce type variables into a type declaration. Let's define a Nullable type: we can use this to represent a missing value, e.g. an empty field in a database row.

data Nullable a = Really a
                | Null

Here, the variable a is not a regular variable: it's a type variable. It indicates that our Nullable type takes another type as its parameter. This lets us use Nullable on values of any type.

nullableBool = Really True

nullableString = Really "something"

As usual, we can load our source file into ghci and experiment with it.

ghci> Really 1.5

<interactive>:1:0:
    No instance for (Show (Nullable t))
      arising from a use of `print' at <interactive>:1:0-9
    Possible fix: add an instance declaration for (Show (Nullable t))
    In the expression: print it
    In a 'do' expression: print it
ghci> Null

<interactive>:1:0:
    No instance for (Show (Nullable a))
      arising from a use of `print' at <interactive>:1:0-3
    Possible fix: add an instance declaration for (Show (Nullable a))
    In the expression: print it
    In a 'do' expression: print it
ghci> :type Really "Really"
Really "Really" :: Nullable [Char]

Nullable is a polymorphic, or generic, type. When we create a type by giving the Nullable type constructor a parameter, we can see what the new type looks like by substituting that type for the type variable a everywhere in the definition of Nullable. The type Nullable String has a value constructor, also named Nullable, that takes a parameter of type String. As we might expect, the type Nullable Int is distinct from Nullable Bool, and so on.

We can nest uses of parameterised types inside each other, but when we do, we may need to use parentheses to tell the Haskell compiler how to parse our expression.

wrapped = Really (Really "wrapped")

If we omitted the parentheses, this would be parsed as (Really Really) Int, which would lead to a compilation error.

To once again extend an analogy to more familiar languages, parameterised types give us a facility that bears some resemblance to templates in C++, and to generics in Java. Just be aware that this is a shallow analogy. Templates and generics were added to their respective languages long after the languages were initially defined, and have an awkward feel. Haskell's parameterised types are simpler and easier to use, as the language was designed with them from the beginning.

The familiar list type is recursive: it's defined in terms of itself. To understand what this means, let's create our own list-like type. We'll use Cons in place of the (:) constructor, and Nil in place of [].

data List a = Cons a (List a)
            | Nil
              deriving (Show)

Because List a appears on both the left and the right of the = sign, the type's definition refers to itself. What this means is that if we want to use the Cons constructor to create a new value, we must supply a value of type a, and another value of type List a. Let's see where this leads us in practice.

The smallest value of type List a that we can create is Nil.

ghci> Nil
Nil

Because Nil has the type List a, we can use it as a parameter to Cons.

ghci> Cons 0 Nil
Cons 0 Nil

And because Cons 0 Nil has the type List a, we can use this as a parameter to Cons.

ghci> Cons 1 (Cons 0 Nil)
Cons 1 (Cons 0 Nil)
ghci> Cons 2 (Cons 1 (Cons 0 Nil))
Cons 2 (Cons 1 (Cons 0 Nil))
ghci> Cons 3 (Cons 2 (Cons 1 (Cons 0 Nil)))
Cons 3 (Cons 2 (Cons 1 (Cons 0 Nil)))

We could obviously continue in this fashion indefinitely, creating ever longer Cons chains, each with a single Nil at the end. This gives us another way of thinking about List as recursive.

Is List an acceptable list?

We can easily prove to ourselves that our List a type has the same shape as the built-in list type [a]. To do this, we write a function that takes any value of type [a], and produces a value of type List a. fromList (x:xs) = Cons x (fromList xs) fromList [] = Nil By inspection, this clearly substitutes a Cons for every (:), and a Nil for each []. This covers both of the built-in list type's constructors. The two types are isomorphic; they have the same shape. ghci> fromList "durian" Cons 'd' (Cons 'u' (Cons 'r' (Cons 'i' (Cons 'a' (Cons 'n' Nil))))) ghci> fromList [Just True, Nothing, Just False] Cons (Just True) (Cons Nothing (Cons (Just False) Nil))

For a third perspective on what a recursive type is, here's a definition of a binary tree type.

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

This time, let's search for insight by comparing our definition with one from a more familiar language. Here's a similar class definition in Java.

class Tree<A>
{
    A value;
    Tree<A> left;
    Tree<A> right;

    public Tree(A v, Tree<A> l, Tree<A> r)
    {
	value = v;
	left = l;
	right = r;
    }
}

The one significant difference is that Java lets us use the special value null anywhere to indicate “nothing”, so we can use null to indicate that a node is missing a left or right child. Here's a small function that constructs a tree with two leaves (a leaf, by convention, has no children).

class Example 
{
    static Tree<String> simpleTree()
    {
	return new Tree<String>(
            "parent",
	    new Tree<String>("left leaf", null, null),
	    new Tree<String>("right leaf", null, null));
    }
}

In Haskell, we don't have an equivalent of null. We could use the Maybe type to provide a similar effect, but that bloats the pattern matching. Instead, we've decided to use a no-argument Empty constructor. Where the Java example provides null to the Tree constructor, we supply Empty in Haskell.

simpleTree = Node "parent" (Node "left child" Empty Empty)
                           (Node "right child" Empty Empty)

Haskell provides a standard function, error :: Char -> a, that we can call when something has gone terribly wrong in our code. We give it a string parameter, which is the error message to display. Its type signature looks peculiar: how can it produce a value of any type a given just a string? The answer is that it doesn't, because error is special.

It has a result type of a so that we can call it anywhere and it will always have the right type. However, instead of returning a value like a normal function, it immediately aborts evaluation, and prints the error message we give it.

Here's an example. The mySecond function returns the second element of its input list, but fails if its input list isn't long enough.

mySecond :: [a] -> a

mySecond xs = if null (tail xs)
              then error "list too short"
              else head (tail xs)

As usual, we can see how this works in practice in ghci.

ghci> mySecond "xi"
'i'
ghci> mySecond [2]
*** Exception: list too short
ghci> head (mySecond [[9]])
*** Exception: list too short

Notice that in the third case above, where we're trying to use the result of the call to mySecond as the argument to another function, evaluation still terminates and drops us back to the ghci prompt. This is the major weakness of using error: it doesn't let our caller distinguish between a recoverable error and a problem so severe that it really should terminate our program.

data Maybe a = Nothing
             | Just a

safeSecond :: [a] -> Maybe a

safeSecond xs = if null (tail xs)
                then Nothing
                else Just (head (tail xs))

tidySecond :: [a] -> Maybe a

tidySecond (_:x:_) = Just x
tidySecond _       = Nothing

Within the body of a function, we can introduce new local variables whenever we need them, using a let expression. As an example, let's write a function that calculates the real-valued roots of the quadratic equation a * (x ** 2) + b * x + c == 0. We're not interested in quadratic equations for their own sake; this is simply a function that has a few interesting properties.

To represent the result, we'll begin by using the Maybe type. The roots could potentially be infinite (if we divide by zero) or complex numbers (if the square root term is negative), in either of which cases we'll return Nothing.

ghci> Just "answer"
Just "answer"
ghci> Nothing
Nothing

We'll use Just to contain the roots when they're defined, and Nothing to indicate that the result is undefined for the given inputs.

-- (b^2 - 4ac) / 2a
realRoots :: Double -> Double -> Double -> Maybe (Double, Double)

realRoots a b c = let n  = b^2 - 4 * a * c
                      a2 = 2 * a
                      s = sqrt n
                  in if a /= 0 && n >= 0
                     then Just ((-b + s) / a2, (-b - s) / a2)
                     else Nothing

The keywords to look out for here are let, which starts a block of variable declarations, and in, which ends it. Each line introduces a new variable. The name is on the left of the =, and the expression it's bound to is on the right.

Add a graphic here to indicate which variables are in scope, and where.

Special notes

Let us re-emphasise our wording: a name in a let block is bound to an expression, not to a value. Because Haskell is a lazy language, the expression associated with a name won't actually be evaluated until it's needed. When we define a variable in a let block, we refer to it as a let-bound variable. This simply means what it says: we bound the variable in a let block. Also, our use of white space here is important. We'll talk about the layout rules in the section called “The offside rule and white space in an expression”.

We can use the names of a variable in a let block both within the block itself and in the expression that follows the in keyword.

In general, we'll refer to the places within our code where we can use a name as the name's scope. If we can use a name, it's in scope, otherwise it's out of scope. If a name is visible throughout a source file, we say it's at the top level.

Shadowing

We can “nest” multiple let blocks inside each other in an expression.

foo = let a = 1
      in let b = 2
         in a + b

Add a graphic to indicate which variables are in scope, and where.

It's perfectly legal, but not exactly wise, to repeat a variable name in a nested let expression.

bar = let x = 1
      in ((let x = "foo" in x), x)

Here, the inner x is hiding, or shadowing, the outer x. It has the same name, but a different type and value.

ghci> bar
("foo",1)

We can also shadow a function's parameters, leading to even stranger results. What is the type of this function?

quux a = let a = "foo"
         in a ++ "eek!"

Because the function's argument a is never used in the body of the function, due to being shadowed by the let-bound a, the argument can have any type at all.

ghci> :type quux
quux :: t -> [Char]

	Compiler warnings are your friends
	Shadowing can obviously lead to confusion and nasty bugs, so GHC has a helpful -fwarn-name-shadowing option. When enabled, GHC will print a warning message any time we shadow a name.

import Data.Complex

data QuadraticRoots = Undefined
                    | RealValued Double Double
                    | ComplexValued (Complex Double) (Complex Double)

roots :: Double -> Double -> Double -> QuadraticRoots

roots a b c =
    if a == 0
    then Undefined
    else if n >= 0
         then RealValued ((-b + s) / a2) ((-b - s) / a2)
         else ComplexValued ((-b' + s') / a2') ((-b' - s') / a2')
  where n   = b**2 - 4 * a * c
        a2  = 2 * a
        b'  = b :+ 0
        a2' = a2 :+ 0
        s = sqrt n
        s' = sqrt (n :+ 0)

pluralise :: String -> [Int] -> [String]
pluralise word counts = map plural counts
    where plural 0 = "no " ++ word ++ "s"
          plural 1 = "one " ++ word
          plural n = show n ++ " " ++ word ++ "s"

itemName = "Weighted Companion Cube"

In our definition of realRoots, the left margin of our text wandered around quite a bit. This was not an accident: in Haskell, white space has meaning.

Haskell uses indentation as a cue to parse sections of code. This use of layout to convey structure is sometimes called the offside rule. At the top level, the first declaration or definition can start in any column, and the Haskell compiler or interpreter remembers that indentation level. Every subsequent top-level declaration must have the same indentation.

Here's an illustration of the top-level indentation rule. Our first file, GoodIndent.hs, is well behaved.

-- This is the leftmost column.

  -- It's fine for top-level declarations to start in any column...
  firstGoodIndentation = 1

  -- ...provided all subsequent declarations do, too!
  secondGoodIndentation = 2

Our second, BadIndent.hs, doesn't play by the rules.

-- This is the leftmost column.

    -- Our first declaration is in column 4.
    firstBadIndentation = 1

  -- Our second is left of the first, which is illegal!
  secondBadIndentation = 2

Here's what happens when we try to load the two files into ghci.

ghci> :load GoodIndent.hs
[1 of 1] Compiling Main             ( GoodIndent.hs, interpreted )
Ok, modules loaded: Main.
ghci> :load BadIndent.hs
[1 of 1] Compiling Main             ( BadIndent.hs, interpreted )

BadIndent.hs:8:2: parse error on input `secondBadIndentation'
Failed, modules loaded: none.

An empty line is treated as a continuation of the current item, as is a line indented to the right of the current current item.

The rules for let expressions and where clauses are similar. After a let or where keyword, the Haskell compiler or interpreter remembers the indentation of the next token it sees. If the next line is empty, or its indentation is further to the right than the previous line, this counts as continuing the previous line. On the other hand, if the indentation is the same as the previous line, this is treated as beginning a new item in the same block.

Here are nested uses of let and where.

bar = let b = 2
          c = True
      in let a = b
         in (a, c)

The name a is only visible within the inner let expression. It's not visible in the outer let. If we try to use the name a there, we'll get a compilation error.

foo = a
    where a = b
              where b = 2

Similarly, the scope of the first where clause is the definition of foo, but the scope of the second is just the first where clause.

The indentation we use for the let and where clauses makes our intentions easy to figure out.

bar = let a = 1
          b = 2
          c = 3
      in a + b + c

foo = let { a = 1;  b = 2;
        c = 3 }
      in a + b + c

We're not limited to using patterns in function definitions. The case expression lets us match patterns at any time. Here's what it looks like.

hasRealRoots a b c = case realRoots a b c of
                       Just _  -> True
                       Nothing -> False

The case keyword is followed by an arbitrary expression: this is the expression that we're checking0. The of keyword signifies the end of the expression and the beginning of the block of patterns and expressions.

Each item in the block consists of a pattern, followed by an arrow ->, followed by an expression to evaluate if that pattern matches. These expressions must all have the same type. The result of the case expression is the result of the expression associated with the first pattern to match. Matches are attempted from top to bottom.

To express “here's the expression to evaluate if none of the other patterns match”, we just use the wild card pattern _ as the last in our list of patterns.

There are a few ways in which new Haskell programmers can misunderstand or misuse patterns. Here are a few potential missteps that you can easily avoid.

Here are some attempts at pattern matching gone awry. Depending on what you expect one of these examples to do, it might contain a surprise..

Matching against a variable

data Fruit = Apple | Orange

apple = "apple"

orange = "orange"        

whichFruit :: String -> Fruit

whichFruit f = case f of
                 apple  -> Apple
                 orange -> Orange

A naive glance suggests that this code is trying to check the value f to see whether it matches the value apple or orange.

The first appearance of apple in the case expression is a pattern, not a use of the top level apple variable. Because this pattern doesn't mention a type constructor or a literal value (the two things that might cause a pattern matching attempt to fail), this branch of the case will always match, no matter what the value of f is.

	Irrefutable patterns
	We refer to a pattern that consists only of a variable name, and thus cannot fail to match, as irrefutable. The wild card pattern _ is also irrefutable.

Here's a corrected version of this function.

betterFruit f = case f of
                  "apple"  -> Apple
                  "orange" -> Orange

Our bugfix involved making this function match against the literal values "apple" and "orange".

nodesAreSame (Node a _ _) (Node a _ _) = Just a
nodesAreSame _            _            = Nothing

Pattern matching only lets us make fixed tests of a value's shape. Although this is useful, we'd often like to be able to perform a more expressive check before evaluating a function's body. Haskell provides a feature, guards, that give us this ability. We'll introduce the idea with an example.

guardedRoots a b c
    | n >= 0 && a /= 0 = Just ((-b + s) / a2, (-b - s) / a2)
    | otherwise        = Nothing
  where n  = b^2 - 4 * a * c
        a2 = 2 * a
        s = sqrt n

A pattern can have zero or more guards, each an expression of type Bool. A guard is introduced by a | symbol, followed by the guard expression, then an = symbol (or -> if we're in a case expression), then the body to use if the guard succeeds. If the pattern matches, each guard is evaluated in turn. If a guard succeeds, its associated body is used as the result of the function. If no guard succeeds, pattern matching moves on to the next pattern.

A guard expression can use any variables mentioned in the pattern that it's associated with. The special-looking guard expression otherwise is simply a variable bound to the value True.

Here's another example of guards in action, where we've rewritten our nodesAreSame example to be correct and concise.

nodesAreSame (Node a _ _) (Node b _ _)
    | a == b     = Just a
nodesAreSame _ _ = Nothing

We can use guards anywhere that we can use patterns. The advantage of writing a function as a series of equations using pattern matching and guards is that it often makes code much clearer. Remember the myDrop function we defined in the section called “Conditional evaluation”?

-- this is a comment, which continues until the end of the line

-- and this is the function definition
myDrop n xs = if n <= 0 || null xs
              then xs
              else myDrop (n - 1) (tail xs)

Here's a reformulation that uses patterns and guards.

niceDrop n xs | n <= 0 = xs
niceDrop _ []          = []
niceDrop n (_:xs)      = niceDrop (n - 1) xs

This change in style lets us enumerate up front the cases in which we expect a function to behave differently. If we bury the decisions inside a function as if expressions, the code becomes harder to read.

In this chapter, we've seen how to define our own algebraic data types. We've read about Haskell's offside rule for laying out functions, and how we can avoid it if we need to. We've seen pattern matching and guards. We've discussed error handling.

At this point, our basic toolbox is complete. In Chapter 5, Functional programming, we'll use this knowledge to develop our functional programming and thinking skills.