Haskell/Print version
This is the print version of Haskell You won't see this message or any elements not part of the book's content when you print or preview this page. 
Table Of Contents
Haskell Basics
 Getting set up
 Variables and functions
 Truth values
 Type basics
 Lists and tuples
 Type basics II
 Next steps
 Building vocabulary
 Simple input and output
Elementary Haskell
 Recursion
 More about lists
 Folds, scans & comprehension
 Type declarations
 Pattern matching
 Control structures
 More on functions
 Higher order functions
 Using GHCi effectively
Intermediate Haskell
 Modules
 Standalone programs
 Indentation
 More on datatypes
 Other data structures
 Classes and types
 The Functor class
Monads
Advanced Haskell
 Monoids
 Applicative Functors
 Arrow tutorial
 Understanding arrows
 Continuation passing style (CPS)
 Value recursion (MonadFix)
 Zippers
 Mutable objects
 Concurrency
 Template Haskell
Fun with Types
 Polymorphism basics
 Existentially quantified types
 Advanced type classes
 Phantom types
 Generalised algebraic datatypes (GADT)
 Datatype algebra
 Type constructors & Kinds
Wider Theory
 Denotational semantics
 Equational reasoning
 Program derivation
 Category theory
 The Curry–Howard isomorphism
 fix and recursion
Haskell Performance
 Introduction
 Step by step examples
 Graph reduction
 Laziness
 Time and space profiling
 Strictness
 Algorithm complexity
 Data structures
 Parallelism
Libraries Reference
General Practices
 Debugging
 Testing
 Packaging your software (Cabal)
 Using the Foreign Function Interface (FFI)
 Generic programming: Scrap your boilerplate
Specialised Tasks
 Graphical user interfaces (GUI)
 Databases
 Working with XML
 Parsing mathematical expressions
 Writing a basic type checker
Haskell Basics
Getting set up
This chapter describes how to install the programs you'll need to start coding in Haskell.
Installing Haskell
Haskell is a programming language, i.e. a language in which humans can express how computers should behave. It's like writing a cooking recipe: you write the recipe and the computer executes it.
To use Haskell programs, you need a special program called a Haskell compiler. A compiler takes code written in Haskell and translates it into machine code, a more primitive language that the computer understands. Using the cooking analogy, you write a recipe (your Haskell program) and a cook (a compiler program) does the work of putting together actual ingredients into an edible dish (an executable file). Of course, you can't easily get the recipe from a final dish (and you can't get the Haskell program code from executable after it's compiled).
To start learning Haskell, download and install the Haskell platform. It will contain the "Glasgow Haskell Compiler", or GHC, and everything else you need.
If you're just trying out Haskell, or are averse to downloading and installing the full compiler, you can try Hugs, the lightweight Haskell interpreter (it also happens to be portable). You might also like to play around with TryHaskell, an interpreter hosted online. Note that all instructions here will be for GHC.
Note
UNIX users:
If you are a person who prefers to compile from source: This might be a bad idea with GHC, especially if it's the first time you install it. GHC is itself mostly written in Haskell, so trying to bootstrap it by hand from source is very tricky. Besides, the build takes a very long time and consumes a lot of disk space. If you are sure that you want to build GHC from the source, see Building and Porting GHC at the GHC homepage.
In short, we strongly recommend downloading the Haskell Platform instead of compiling from source.
Very first steps
After you have installed the Haskell Platform, it's now time to write your first Haskell code.
For that, you will use the program called GHCi (the 'i' stands for 'interactive'). Depending on your operating system, perform the following steps:
 On Windows: Click Start, then Run, then type 'cmd' and hit Enter, then type
ghci
and hit Enter once more.  On MacOS: Open the application "Terminal" found in the "Applications/Utilities" folder, type the letters
ghci
into the window that appears and hit the Enter key.  On Linux: Open a terminal and run the
ghci
program.
You should get output that looks something like the following:
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghcprim ... linking ... done. Loading package integergmp ... linking ... done. Loading package base ... linking ... done. Prelude>
The first bit is GHCi's version. It then informs you it's loading the base package, so you'll have access to most of the builtin functions and modules that come with GHC. Finally, the Prelude>
bit is known as the prompt. This is where you enter commands, and GHCi will respond with their results.
Now you're ready to write your first Haskell code. In particular, let's try some basic arithmetic:
Prelude> 2 + 2 4 Prelude> 5 + 4 * 3 17 Prelude> 2 ^ 5 32
The operators are similar to what they are in other languages: +
is addition, *
is multiplication, and ^
is exponentiation (raising to the power of, or ). Note from the second example that Haskell follows standard order of operations.
Now you know how to use Haskell as a calculator. Actually, Haskell is always basically a calculator  a really powerful one, able to deal not only with numbers but also with other objects like characters, lists, functions, trees, and even other programs (if you aren't familiar with these terms yet, don't worry).
GHCi is a very powerful development environment. As we progress, we will learn how we can load files with source code into GHCi, and evaluate different parts of them.
If you're clear on everything so far (if not, use the talk page and help us improve this Wikibook!), then you are ready for next chapter, in which we will introduce some of the basic concepts of Haskell, along with our first Haskell functions.
Variables and functions
All the examples in this chapter can be typed into a Haskell source file and evaluated by loading that file into GHC or Hugs. Do not include the "Prelude>" prompts at the beginning of input. When the prompt is shown, you can type the code into an environment like GHCi. Otherwise, you should put the code in a file and run it.
Variables
We have seen how to use GHCi as a calculator. Of course, this is only practical for short calculations. For longer calculations and for writing Haskell programs, we want to keep track of intermediate results.
Intermediate results can be stored in variables, to which we refer by their name. A variable contains a value, which is substituted for the variable name when the variable is used. For instance, consider the following calculation
Prelude> 3.1416 * 5^2 78.53999999999999
That is the approximate area of a circle with radius 5
, according to the formula . It is cumbersome to type in the digits of , or even to remember them at all. In fact, an important motivation of programming is delegating mindless repetition and rote memorization to a machine so that our minds are free to deal with more interesting ideas. For the present case, Haskell already includes a variable named pi
that stores over a dozen digits of for us. This allows for not just clearer code, but also greater precision.
Prelude> pi 3.141592653589793 Prelude> pi * 5^2 78.53981633974483
Note that the variable pi
and its value, 3.141592653589793
, can be used interchangeably in calculations.
Haskell source files
Whenever we write code that will be used more than momentarily, we save it in a Haskell source file with the extension .hs. Basically, .hs files are plain text. If you need suggestions for text editors appropriate for coding, the Wikipedia article on text editors is a reasonable place to start. Vim and Emacs are popular choices among Haskell programmers. Proper source code editors will provide syntax highlighting, which colors the code in relevant ways to make reading and understanding easier.
To keep things tidy, create a directory (i.e. a folder) in your computer to save the Haskell files you will create while doing the exercises in this book. Call the directory something like HaskellWikibook. Then, create a new file in that directory called Varfun.hs with the following code:
r = 5.0
That code defines the variable r
as being 5.0
. Setting our own variables can make it easier to do future calculations.
Note: make sure that there are no spaces at the beginning of the line because Haskell is sensitive to whitespace.
Next, navigate to the HaskellWikibook directory in your terminal, start GHCi and load the Varfun.hs file using the :load
command:
Prelude> :load Varfun.hs [1 of 1] Compiling Main ( Varfun.hs, interpreted ) Ok, modules loaded: Main.
:load
can be abbreviated as :l
(as in :l Varfun.hs
).
If GHCi gives an error like Could not find module 'Varfun.hs'
, you probably are in the wrong directory. You can use the :cd
command to change directories within GHCi (for instance, :cd HaskellWikibook
).
With the file loaded, you can use the newly defined variable r
in your calculations.
*Main> r 5.0 *Main> pi * r^2 78.53981633974483
So, to calculate the area of a circle of radius 5, we simply define r = 5.0
and then type in the wellknown formula for the area of a circle. There is no need to write the numbers out every time; that's very convenient!
Since this was so much fun, let's add another definition: Change the contents of the source file to
r = 5.0 area = pi * r ^ 2
Save the file and type the :reload
(shorter version is :r
) command in GHCi to load the new contents (note that this is a continuation of the last session):
*Main> :reload Compiling Main ( Varfun.hs, interpreted ) Ok, modules loaded: Main. *Main>
Now we have two variables r
and area
available
*Main> area 78.53981633974483 *Main> area / r 15.707963267948966
Note
It is also possible to define variables directly at the GHCi prompt, without a source file. Skipping the details, the syntax for doing so uses the let
keyword (a word with a special meaning) and looks like:
Prelude> let area = pi * 5 ^ 2
Although we will occasionally use let this way for expediency, it will become obvious that this practice is not convenient once we move into slightly more complex tasks. So, we are emphasizing the use of source files from the very start.
Note
GHC can also be used as a compiler (that is, you can use GHC to convert your Haskell files into a standalone program that can be run without depending on the interpreter). How that is done will be explained later, in the Standalone programs chapter.
Comments
Before we continue, it is good to understand that it is possible to include text in a program without having it treated as code. This is achieved by use of comments. In Haskell, a comment can be started with 
and continues until the end of the line:
x = 5  The variable x is 5. y = 6  The variable y is 6.  z = 7
In this case, x
and y
are defined, but z
is not. Comments can also go anywhere using the alternative syntax { ... }
:
x = { Do this just because you can. } 5
Comments are generally used for explaining parts of a program that might be, on their own, confusing to readers. Beware of overdoing it, though. Too many comments make programs harder to read. Also, comments must be carefully updated whenever the corresponding code is changed, so that they do not become outdated, incorrect and misleading.
Variables in imperative languages
If you are already familiar with imperative programming languages like C, you will notice that variables in Haskell are quite different from variables as you know them. We now explain why and how.
If you have no programming experience, you might like to skip this section and continue reading with Functions.
Unlike in imperative languages, variables in Haskell do not vary. Once defined, their value never changes; they are immutable. For instance, the following code does not work:
r = 5 r = 2
The variables in functional programming languages are more related to variables in mathematics than to changeable locations in a computer's memory. In a math classroom, you would definitely never see a variable change its value within a single problem. Likewise, in Haskell the compiler will respond to the code above with an error: "multiple declarations of r
". Those familiar with imperative programming, which involves explicitly telling the computer what to do, may be used to read this as first setting r = 5
and then changing it to r = 2
. In functional programming languages, however, the program is in charge of figuring out what to do with the computer's memory.
Here's another example of a major difference from imperative languages:
r = r + 1
Instead of "incrementing the variable r
", this is actually a recursive definition of r
in terms of itself (we will explain recursion in detail later on; just remember that there is a radical difference from what would happen in an imperative language). If r
had been defined with any value beforehand, then r = r + 1
in Haskell would bring an error message. That is akin to saying, in a mathematical context, that , which is plainly wrong.
Because their values do not change within a program, variables can be defined in any order. For example, the following fragments of code do exactly the same thing:
y = x * 2 x = 3 
x = 3 y = x * 2 
We can write things in any order that we want, there is no notion of "x
being declared before y
" or the other way around. This is also why you can't declare something more than once; it would be ambiguous otherwise. Of course, using y
will still require a value for x
, but this is unimportant until you need a specific numeric value.
By now, you might be wondering how you can actually do anything at all in Haskell where variables don't change. But trust us; as we hope to show you in the rest of this book, you can write every program under the sun without ever changing a single variable! In fact, variables that don't change make life much easier because it makes programs much more predictable. That is a key feature of purely functional programming; it requires a very different approach and mindset from those of imperative programming.
Functions
Now, suppose that we have multiple circles with different radii whose areas we want to calculate. For instance, let us calculate the area of another circle with radius 3. If we were to build on the program we have just written, r
would already have been defined as 5
. We could change the entire program so that r = 3
, but then we would lose the ability to calculate the first circle. An alternative is defining a new variable r2
, and also another new variable area2
for the area calculated with r2
.^{[1]} Our new source file for both circles is:
r = 5 area = pi * r ^ 2 r2 = 3 area2 = pi * r2 ^ 2
Clearly, that is unsatisfactory because we are repeating the formula for the area of a circle verbatim. To eliminate this mindless repetition, we would prefer to write it down only once and then apply it to different radii. That's exactly what functions allow us to do.
A function takes an argument value (or parameter) and gives a result value (this is essentially the same as mathematical functions). Defining functions in Haskell is simple: It is like defining a variable, except that we take note of the function argument that we put on the left hand side. For instance, the following is the definition of a function area
which depends on an argument which we name r
:
area r = pi * r ^ 2
Look closely at the syntax: the function name comes first (in our example, it is area
), followed by a space and then the argument (r
in the example). Following the = sign, the function definition is a formula that uses the argument in context with other already defined terms.
Now, we can plug in different values for the argument in a call to the function. Save the code in a file, load it into GHCi and try the following:
*Main> area 5 78.53981633974483 *Main> area 3 28.274333882308138 *Main> area 17 907.9202768874502
Thus, we can call this function with different radii to calculate the area of a circle with a radius of any length.
Our function here is defined mathematically as
In mathematics, the parameter is enclosed between parentheses, as in or . The Haskell code will also work with parentheses, but they are normally omitted. As Haskell is a functional language, we will use functions all the time, and whenever possible we want to minimize extra symbols.
Parentheses are still used for grouping expressions (any code that gives a value) to be evaluated together. Note how the following expressions are parsed differently:
5 * 3 + 2  15 + 2 = 17 (multiplication is done before addition) 5 * (3 + 2)  5 * 5 = 25 (thanks to the parentheses) area 5 * 3  (area 5) * 3 area (5 * 3)  area 15
Notice how Haskell functions take precedence over all other operators such as +
and *
, in the same way that, for instance, multiplication is done before addition in mathematics.
Evaluation
Let us try to understand what exactly happens when you enter an expression into GHCi. After you press the enter key, GHCi will evaluate the expression you have given. That means it will replace each function with its definition and calculate the results until a single value is left. For example, the evaluation of area 5
proceeds as follows:
area 5 => { replace the lefthand side area r = ... by the righthand side ... = pi * r^2 } pi * 5 ^ 2 => { replace pi by its numerical value } 3.141592653589793 * 5 ^ 2 => { apply exponentiation (^) } 3.141592653589793 * 25 => { apply multiplication (*) } 78.53981633974483
As this shows, to apply or call a function means to replace the lefthand side of its definition by its righthand side. As a last step, GHCi prints the final result on the screen.
Here are some more functions:
double x = 2 * x quadruple x = double (double x) square x = x * x half x = x / 2
Exercises 


Multiple parameters
Of course, functions can also have more than one argument. For example, here is a function for calculating the area of a rectangle given its length and its width:
areaRect l w = l * w
*Main> areaRect 5 10 50
Another example that calculates the area of a triangle :
areaTriangle b h = (b * h) / 2
*Main> areaTriangle 3 9 13.5
As you can see, multiple arguments are separated by spaces. That's also why you sometimes have to use parentheses to group expressions. For instance, to quadruple a value x
, you can't write
quadruple x = double double x
because that would mean to apply a function named double
to the two arguments double
and x
: functions can be arguments to other functions (and you will see why later). Instead, you have to put parentheses around the argument:
quadruple x = double (double x)
Arguments are always passed in the order given. For example:
subtract x y = x  y
*Main> subtract 10 5 5 *Main> subtract 5 10 5
Here, subtract 10 5
evaluates to 10  5
, but subtract 5 10
evaluates to 5  10
because the order changes.
Exercises 


Remark on combining functions
It goes without saying that you can use functions that you have already defined to define new functions, just like you can use the predefined functions like addition (+)
or multiplication (*)
(operators are defined as functions in Haskell). For example, to calculate the area of a square, we can reuse our function that calculates the area of a rectangle:
areaRect l w = l * w areaSquare s = areaRect s s
*Main> areaSquare 5 25
After all, a square is just a rectangle with equal sides.
This principle may seem innocent enough, but it is really powerful, in particular when we start to calculate with other objects instead of numbers.
Exercises 


Local definitions
where
clauses
When defining a function, it is not uncommon to define intermediate results that are local to the function. For instance, consider Heron's formula for calculating the area of a triangle with sides a
, b
, and c
:
heron a b c = sqrt (s * (s  a) * (s  b) * (s  c)) where s = (a + b + c) / 2
The variable s
is half the perimeter of the triangle and it would be tedious to write it out four times in the argument of the square root function sqrt
.
Simply writing the definitions in sequence will not work...
heron a b c = sqrt (s * (s  a) * (s  b) * (s  c))  s is not defined here s = (a + b + c) / 2  a, b, and c are not defined here
... because the variables a
, b
, c
are only available in the righthand side of the function heron
, but the definition of s
as written here is not part of the righthand side of heron
. To make it part of the righthand side, we have to use the where
keyword.
Note that both the where
and the local definitions are indented by 4 spaces, to distinguish them from subsequent definitions. Here is another example that shows a mix of local and toplevel definitions:
areaTriangleTrig a b c = c * height / 2  use trigonometry where cosa = (b ^ 2 + c ^ 2  a ^ 2) / (2 * b * c) sina = sqrt (1  cosa ^ 2) height = b * sina areaTriangleHeron a b c = result  use Heron's formula where result = sqrt (s * (s  a) * (s  b) * (s  c)) s = (a + b + c) / 2
Scope
If you look closely at the previous example, you'll notice that we have used the variable names a
, b
, c
twice, once for each of the two area functions. How does that work?
Fortunately, the following fragment of code does not contain any unpleasant surprises:
Prelude> let r = 0 Prelude> let area r = pi * r ^ 2 Prelude> area 5 78.53981633974483
An "unpleasant surprise" here would have been getting 0
for the area because of the let r = 0
definition getting in the way. That does not happen because when you defined r
the second time you are talking about a different r
. This is something that happens in real life as well. How many people do you know that have the name John? What's interesting about people named John is that most of the time, you can talk about "John" to your friends, and depending on the context, your friends will know which John you are referring to. Programming has a notion similar to context, called scope.
We will not explain the technicalities behind scope (at least not now). Just keep in mind that the value of a parameter is strictly what you pass in when you call the function, regardless of what the variable was called in the function's definition.
Summary
 Variables store values. In fact, they store any arbitrary Haskell expressions.
 Variables do not change.
 Functions help you write reusable code.
 Functions can accept more than one parameter.
We also learned that comments are noncode text within a source file.
Notes
 ↑ As this example shows, the names of variables may contain numbers as well as letters. Variables must begin with a lowercase letter, but for the rest, any string consisting of letter, numbers, underscore (_) or tick (') is allowed.
Truth values
Equality and other comparisons
In the last chapter, we saw how to use the equals sign to define variables and functions in Haskell. The following code
r = 5
causes occurrences of r to be replaced by 5 in all places where it makes sense to do so according to the scope of the definition. Similarly,
f x = x + 3
causes occurrences of f followed by a number (which is taken as f's argument) to be replaced by that number plus three.
In mathematics, however, the equals sign is also used in a subtly different and equally important way. For instance, consider this simple problem:
Example: Solve the following equation:
When we look at a problem like this one, our immediate concern is not the ability to represent the value as , or viceversa. Instead, we read the equation as a proposition, which says that some number gives 5 as result when added to 3. Solving the equation means finding which, if any, values of make that proposition true. In this example, we can use elementary algebra to determine that (i.e. 2 is the number we need to substitute to make the equation true, giving .
Comparing values to see if they are equal is also useful in programming. Haskell allows us to write such tests in a natural way that looks just like an equation. Since the equals sign is already used for defining things, we use a double equals sign, == instead. To see that at work, you can start GHCi and enter the proposition we wrote above like this:
Prelude> 2 + 3 == 5 True
GHCi returns "True" because is equal to 5. What if we use an equation that is not true?
Prelude> 7 + 3 == 5 False
Nice and coherent. The next step is to use our own functions in these tests. Let us try it with the function f we mentioned at the start of the module:
Prelude> let f x = x + 3 Prelude> f 2 == 5 True
Just as expected, since f 2 is just 2 + 3.
In addition to tests for equality, we can just as easily compare two numerical values to see which one is larger. Haskell provides a number of tests including: < (less than), > (greater than), <= (less than or equal to) and >= (greater than or equal to), which work just like == (equal to). For a simple application, we could use < alongside the area function from the previous module to see whether a circle of a certain radius would have an area smaller than some value.
Prelude> let area r = pi * r ^ 2 Prelude> area 5 < 50 False
Boolean values
Now we know that GHCi can tell us whether some arithmetical propositions are true or false. That's all fine and dandy, but how could that help us to write programs? And what is actually going on when GHCi "answers" such "questions"?
To understand what is happening, consider a different but related issue. If we enter an arithmetical expression in GHCi the expression gets evaluated, and the resulting numerical value is displayed on the screen:
Prelude> 2 + 2 4
If we replace the arithmetical expression with an equality comparison, something similar seems to happen:
Prelude> 2 == 2 True
But what is that "True" that gets displayed? It certainly does not look like a number. We can think of it as something that tells us about the veracity of the proposition 2 == 2. From that point of view, it makes sense to regard it as a value – except that instead of representing some kind of count, quantity, etc. it stands for the truth of a proposition. Such values are called truth values, or boolean values^{[1]}. Naturally, there are only two possible boolean values – True and False.
An introduction to types
When we say True and False are values, we are not just making an analogy. Boolean values have the same status as numerical values in Haskell, and indeed you can manipulate them just as well. One trivial example would be equality tests on truth values:
Prelude> True == True True Prelude> True == False False
True is indeed equal to True, and True is not equal to False. Now, quickly: can you answer whether 2 is equal to True?
Prelude> 2 == True <interactive>:1:0: No instance for (Num Bool) arising from the literal `2' at <interactive>:1:0 Possible fix: add an instance declaration for (Num Bool) In the first argument of `(==)', namely `2' In the expression: 2 == True In the definition of `it': it = 2 == True
The correct answer is you can't, because the question just does not make sense. It is impossible to compare a number with something that is not a number, or a boolean with something that is not a boolean. Haskell incorporates that notion, and the ugly error message we got is, in essence, stating exactly that. Ignoring all of the obfuscating clutter (which we will get to understand eventually), that message says that there was a number (Num) on the left side of the ==, and so some kind of number was expected on the right side; however, a boolean value (Bool) is not a number, and so the equality test exploded into flames.
Thus, the general concept is that values have types, and these types define what we can or cannot do with the values. In this case, for instance, True is a value of type Bool, as is False (as for the 2, while there is a welldefined concept of number in Haskell the situation is slightly more complicated, so we will defer the explanation for a little while). Types are a very powerful tool because they provide a way to regulate the behaviour of values with rules which make sense, making it easier to write programs that work correctly. We will come back to the topic of types many times as they are very important to Haskell.
Infix operators
What we have seen so far leads us to the conclusion that an equality test like 2 == 2 is an expression just like 2 + 2, and that it also evaluates to a value in pretty much the same way. That fact is actually given a passing mention on the ugly error message we got on the previous example:
In the expression: 2 == True
Therefore, when we type 2 == 2 in the prompt and GHCi "answers" True it is just evaluating an expression. But there is a deeper truth involved in this process. A hint is provided by the very same error message:
In the first argument of `(==)', namely `2'
GHCi called 2 the first argument of (==). In the previous module, we used argument to describe the values we feed a function with so that it evaluates to a result. It turns out that == is just a function, which takes two arguments, namely the left side and the right side of the equality test. The only special thing about it is the syntax: Haskell allows twoargument functions with names composed only of nonalphanumeric characters to be used as infix operators, that is, placed between their arguments. The only caveat is that if you wish to use such a function in the "standard" way (writing the function name before the arguments, as a prefix operator) the function name must be enclosed in parentheses. So the following expressions are completely equivalent:
Prelude> 4 + 9 == 13 True Prelude> (==) (4 + 9) 13 True
This makes it clear how (==) is a function with two arguments just like areaRect from the previous module. What's more, the same considerations apply to the other relational operators we mentioned (<, >, <=, >=) and to the arithmetical operators (+, *, etc.) – all of them are just functions. This generality is an illustration of one of the strengths of Haskell: it is a language with very few "special cases", which helps to keep things simple. In general, we can say that all tangible things in Haskell are either values or functions.^{[2]}
Boolean operations
To see both truth values and infix operators in action, let's consider the boolean operations which manipulate truth values as in logic propositions. Haskell provides us three basic functions for that purpose:
 (&&) performs the and operation. Given two boolean values, it evaluates to True if both the first and the second are True, and to False otherwise.
Prelude> (3 < 8) && (False == False) True Prelude> (&&) (6 <= 5) (1 == 1) False
 () performs the or operation. Given two boolean values, it evaluates to True if either the first or the second are True (or if both are true), and to False otherwise.
Prelude> (2 + 2 == 5)  (2 > 0) True Prelude> () (18 == 17) (9 >= 11) False
 not performs the negation of a boolean value; that is, it converts True to False and viceversa.
Prelude> not (5 * 2 == 10) False
Another relational operator is not equal to. It is already provided by Haskell as the (/=) function, but if we were to implement it ourselves, a natural way would be:
x /= y = not (x == y)
Note that it is perfectly legal syntax to write operators infix, even when defining them. Completely new operators can also be created out of ASCII symbols (which means mostly the common symbols used on a keyboard).
Guards
Now we have explored what is really happening with boolean operators, but we've done little more than testing oneline expressions here. We still don't know how this can be used to make real programs. We will tackle this issue by introducing guards, a feature that relies on boolean values and allows us to write more interesting functions.
Let us implement the absolute value function. The absolute value of a number is the number with its sign discarded^{[3]}; so if the number is negative (that is, smaller than zero) the sign is inverted; otherwise it remains unchanged. We could write the definition as:
Here, the actual expression to be used for calculating depends on a set of propositions made about . If is true, then we use the first expression, but if is the case, then we use the second expression instead. We need a way to express this decision process in Haskell. Using guards, the implementation could look like this:^{[4]}
Example: The abs function.
abs x  x < 0 = 0  x  otherwise = x
Remarkably, the above code is about as readable as the corresponding mathematical definition. Let us dissect the components of the definition:
 We start just like a normal function definition, providing a name for the function, abs, and saying it will take a single parameter, which we will name x.
 Instead of just following with the = and the righthand side of the definition, we entered a line break, and, following it, the two alternatives, placed in separate lines.^{[5]} These alternatives are the guards proper. Note that the whitespace is not just for aesthetic reasons; it is necessary for the code to be parsed correctly.
 Each of the guards begins with a pipe character, . After the pipe, we put an expression which evaluates to a boolean (also called a boolean condition or a predicate), which is followed by the rest of the definition – the equals sign and the righthand side which should be used if the predicate evaluates to True.
 The otherwise case is used when none of the preceding predicates evaluate to True. In this case, if x is not smaller than zero, it must be greater than or equal to zero, so the final predicate could have just as easily been x >= 0; but otherwise works just as well.
Note
There is no syntactical magic behind otherwise. It is defined alongside the default variables and functions of Haskell as simply
otherwise = True
This definition makes otherwise a catchall guard. As evaluation of the guard predicates is sequential, the otherwise predicate will only be reached if none of the other ones evaluates to True (so make sure you always place otherwise as the last guard!). In general, it is a good idea to always provide an otherwise guard, because a rather ugly runtime error will be produced if none of the predicates is true for some input.
Note
You might be wondering why we wrote 0  x and not simply x to denote the sign inversion. Truth is, we could have written the first guard as
 x < 0 = x
and it would have worked just as well. The only issue is that this way of expressing sign inversion is actually one of the few "special cases" in Haskell, in that in this case the  is not a function that takes one argument and evaluates to 0  x, but just a syntactical abbreviation. While very handy, this shortcut occasionally conflicts with the usage of () as an actual function (the subtraction operator), which is a potential source of annoyance (for example, try writing three minus negativefour without using any parentheses for grouping). Here, we wrote 0  x explicitly so that we could take the opportunity to point out this issue.
where
and Guards
where
clauses are particularly handy when used with guards. For instance, consider a function which computes the number of (real) solutions for a quadratic equation, :
numOfRealSolutions a b c  disc > 0 = 2  disc == 0 = 1  otherwise = 0 where disc = b^2  4*a*c
The where definition is within the scope of all of the guards, sparing us from repeating the expression for disc.
Notes
 ↑ The term is a tribute to the mathematician and philosopher George Boole.
 ↑ In case you found this statement bold, know that we will go even further in due course.
 ↑ Technically, that just covers how to get the absolute value of a real number, but let's ignore this detail for now.
 ↑ abs is also provided by Haskell, so in a realworld situation you don't need to worry about providing an implementation yourself.
 ↑ We could have joined the lines and written everything in a single line, but in this case it would be a lot less readable.
Type basics
In programming, Types are used to group similar values into categories. In Haskell, the type system is a powerful way of reducing the number of mistakes in your code.
Introduction
Programming deals with different sorts of entities. For example, consider adding two numbers together:
What are 2 and 3? Well, they are numbers. What about the plus sign in the middle? That's certainly not a number, but it stands for an operation which we can do with two numbers – namely, addition.
Similarly, consider a program that asks you for your name and then greets you with a "Hello" message. Neither your name nor the word Hello are numbers. What are they then? We might refer to all words and sentences and so forth as text. It's normal in programming to use a slightly more esoteric word: String, which is short for "string of characters".
Databases illustrate clearly the concept of types. For example, say we had a table in a database to store details about a person's contacts; a kind of personal telephone book. The contents might look like this:
First Name  Last Name  Telephone number  Address 
Sherlock  Holmes  743756  221B Baker Street London 
Bob  Jones  655523  99 Long Road Street Villestown 
The fields in each entry contain values. Sherlock is a value as is 99 Long Road Street Villestown as well as 655523. As we've said, types are a way of categorizing data, so let's classify the values in this example. The first three fields seem straightforward enough. "First Name" and "Last Name" contain text, so we say that the values are of type String, while "Telephone Number" is clearly a number.
At first glance one may be tempted to classify address as a String. However, the semantics behind an innocent address are quite complex. There are a whole lot of human conventions that dictate how we interpret it. For example, if the beginning of the address text contains a number it is likely the number of the house. If not, then it's probably the name of the house – except if it starts with "PO Box", in which case it's just a postal box address and doesn't indicate where the person lives at all.
Clearly, there's more going on here than just text, as each part of the address has its own meaning. In principle, there is nothing wrong with saying addresses are Strings, but that doesn't capture many important features of addresses. When we describe something as a String, all that we are saying is that it is a sequence of letters, numbers, etc. Recognizing something as a specialized type is far more meaningful. If we know something is an Address, we instantly know much more about the piece of data – for instance, that we can interpret it using the "human conventions" that give meaning to addresses.
In retrospect, we might also apply this rationale to the telephone numbers. It could be a good idea to speak in terms of a TelephoneNumber type. Then, if we were to come across some arbitrary sequence of digits which happened to be of type TelephoneNumber we would have access to a lot more information than if it were just a Number – for instance, we could start looking for things such as area and country codes on the initial digits.
Another reason not to consider the telephone numbers as just Numbers is that doing arithmetics with them makes no sense. What is the meaning and expected effect of, say, multiplying a TelephoneNumber by 100? It would not allow calling anyone by phone. That's a good reason for using a more specialized type than Number. Also, each digit comprising a telephone number is important; it's not acceptable to lose some of them by rounding it or even by omitting leading zeroes.
Why types are useful
So far, it seems that all what we've done was to describe and categorize things, and it may not be obvious why all of this talk would be so important for writing actual programs. Starting with this module, we will explore how Haskell uses types to the programmer's benefit, allowing us to incorporate the semantics behind, say, an address or a telephone number seamlessly in the code.
Using the interactive :type
command
The best way to explore how types work in Haskell is from GHCi. The type of any expression can be checked with the immensely useful :type
(or shortened to :t
) command. Let us test it on the boolean values from the previous module:
Example: Exploring the types of boolean values in GHCi
Prelude> :type True True :: Bool Prelude> :type False False :: Bool Prelude> :t (3 < 5) (3 < 5) :: Bool
Usage of :type is straightforward: enter the command into the prompt followed by whatever you want to find the type of. On the third example, we use :t, which we will be using from now on. GHCi will then print the type of the expression. The symbol ::, which will appear in a couple other places, can be read as simply "is of type", and indicates a type signature.
:type reveals that truth values in Haskell are of type Bool, as illustrated above for the two possible values, True and False, as well as for a sample expression that will evaluate to one of them. It is worthy to note at this point that boolean values are not just for value comparisons. Bool captures in a very simple way the semantics of a yes/no answer, and so it can be useful to represent any information of such kind – say, whether a name was found in a spreadsheet, or whether a user has toggled an on/off option.
Characters and strings
Now let's try :t on something new. Literal characters are entered by enclosing them with single quotation marks. For instance, this is the single letter H:
Example: Using the :type command in GHCi on a literal character
Prelude> :t 'H' 'H' :: Char
So, literal character values have type Char (short for "character"). Single quotation marks, however, only work for individual characters. If we need to enter actual text – that is, a string of characters – we use double quotation marks instead:
Example: Using the :t command in GHCi on a literal string
Prelude> :t "Hello World" "Hello World" :: [Char]
Why did we get Char again? The difference is in the square brackets. [Char] means a number of characters chained together, forming a list. That is what text strings are in Haskell – lists of characters.^{[1]}
Exercises 


Incidentally, Haskell allows for type synonyms, which work pretty much like synonyms in human languages (words that mean the same thing – say, 'big' and 'large'). In Haskell, type synonyms are alternative names for types. For instance, String is defined as a synonym of [Char], and so we can freely substitute one with the other. Therefore, to say:
"Hello World" :: String
is also perfectly valid, and in many cases a lot more readable. From here on we'll mostly refer to text values as String, rather than [Char].
Functional types
So far, we have seen how values (strings, booleans, characters, etc.) have types and how these types help us to categorize and describe them. Now, the big twist that makes Haskell's type system truly powerful: Functions have types as well.^{[2]} Let's look at some examples to see how that works.
Example: not
We can negate boolean values with not (e.g. not True evaluates to False and viceversa). To figure out the type of a function, we consider two things: the type of values it takes as its input and the type of value it returns. In this example, things are easy. not takes a Bool (the Bool to be negated), and returns a Bool (the negated Bool). The notation for writing that down is:
Example: Type signature for not
not :: Bool > Bool
You can read this as "not
is a function from things of type Bool to things of type Bool".
Using :t on a function will work just as expected:
Prelude> :t not not :: Bool > Bool
The description of a function's type is in terms of the types of argument(s) it takes and gives.
Example: chr
and ord
Text presents a problem to computers. Once everything is reduced to its lowest level, all a computer knows how to deal with are 1s and 0s: computers work in binary. As working with binary numbers isn't at all convenient, humans have come up with ways of making computers store text. Every character is first converted to a number, then that number is converted to binary and stored. That's how a piece of text (which is just a sequence of characters) is encoded into binary. Normally, we're only interested in how to encode characters into their numerical representations, because the computer generally takes care of the conversion to binary numbers without our intervention.
The easiest way of converting characters to numbers is simply to write all the possible characters down, then number them. For example, we might decide that 'a' corresponds to 1, then 'b' to 2, and so on. This is exactly what something called the ASCII standard is: take 128 commonlyused characters and number them. Of course, it would be a bore to sit down and look up a character in a big lookup table every time we wanted to encode it, so we've got two functions that do it for us, chr
(pronounced 'char') and ord
^{[3]}:
Example: Type signatures for chr
and ord
chr :: Int > Char ord :: Char > Int
We already know what Char means. The new type on the signatures above, Int, amounts to integer numbers, and is one of quite a few different types of numbers.^{[4]} The type signature of chr tells us that it takes an argument of type Int, an integer number, and evaluates to a result of type Char. The converse is the case with ord: It takes things of type Char and returns things of type Int. With the info from the type signatures, it becomes immediately clear which of the functions encodes a character into a numeric code (ord) and which does the decoding back to a character (chr).
To make things more concrete, here are a few examples of function calls to chr
and ord
. Notice that the two functions aren't available by default; so before trying them in GHCi you need to use the :module Data.Char (or :m Data.Char) command to load the Data.Char module, where they are defined.
Example: Function calls to chr
and ord
Prelude> :m Data.Char Prelude Data.Char> chr 97 'a' Prelude Data.Char> chr 98 'b' Prelude Data.Char> ord 'c' 99
Functions with more than one argument
The style of type signatures we have been using works well enough for functions of one argument, but what would be the type of a function like this one?
Example: A function with more than one argument
xor p q = (p  q) && not (p && q)
(xor
is the exclusiveor function, which evaluates to True
if either one or the other argument is True
, but not both; and False
otherwise.)
The general technique for forming the type of a function that accepts more than one argument is simply to write down all the types of the arguments in a row, in order (so in this case p
first then q
), then link them all with >
. Finally, add the type of the result to the end of the row and stick a final >
in just before it.^{[5]} In this example, we have:
 Write down the types of the arguments. In this case, the use of
()
and(&&)
gives away thatp
andq
have to be of typeBool
:Bool Bool ^^ p is a Bool ^^ q is a Bool as well
 Fill in the gaps with
>
:Bool > Bool
 Add in the result type and a final
>
. In our case, we're just doing some basic boolean operations so the result remains a Bool.Bool > Bool > Bool ^^ We're returning a Bool ^^ This is the extra > that got added in
The final signature, then, is:
Example: The signature of xor
xor :: Bool > Bool > Bool
Real world example: openWindow
As you'll learn in the Haskell in Practice section of the course, one popular group of Haskell libraries are the GUI (Graphical User Interface) ones. These provide functions for dealing with the visual things computer users are familiar with: menus and buttons, application windows, moving the mouse around, etc. One of the functions from one of these libraries is called openWindow
, and you can use it to open a new window in your application. For example, say you're writing a word processor, and the user has clicked on the 'Options' button. You need to open a new window which contains all the options that they can change. Let's look at the type signature for this function^{[6]}:
Example: openWindow
openWindow :: WindowTitle > WindowSize > Window
Don't panic! Here are a few more types you haven't come across yet. But don't worry, they're quite simple. All three of the types there, WindowTitle, WindowSize and Window are defined by the GUI library that provides openWindow
. As we saw when constructing the types above, because there are two arrows, the first two types are the types of the parameters, and the last is the type of the result. WindowTitle holds the title of the window (which typically appears in a title bar at the very top of the window), and WindowSize specifies how big the window should be. The function then returns a value of type Window which represents the actual window.
One key point illustrated by this example, as well as the chr/ord one is that, even if you have never seen the function or don't know how it actually works, a type signature can immediately give you a good general idea of what the function is supposed to do. For that reason, a very useful habit to acquire is testing every new function you meet with :t. If you start doing that now, you'll not only learn about the standard library Haskell functions quite a bit quicker but also develop a useful kind of intuition. Curiosity pays off. :)
Exercises 

Finding types for functions is a basic Haskell skill worth mastering. What are the types of the following functions?
For any functions hereafter involving numbers, you can just pretend the numbers are Ints.

Type signatures in code
We have explored the basic theory behind types and how they apply to Haskell. Now, we will see how type signatures are used for annotating functions in source files. Let's see what that looks like for xor
function from an earlier example:
Example: A function with its signature
xor :: Bool > Bool > Bool xor p q = (p  q) && not (p && q)
That is all we have to do, really. Signatures are placed just before the corresponding functions, for maximum clarity.
The signatures we add in this way serve a dual role. They inform the type of the functions both to human readers of the code and to the compiler/interpreter.
Type inference
We just said that type signatures tell the interpreter (or compiler) what the function type is. Yet we have been writing perfectly good Haskell code without any signatures so far, and it was accepted by GHC/GHCi. Indeed, it is not mandatory to add type signatures. That doesn't mean, however, that when they are missing Haskell simply forgets about types altogether! Instead, when you don't tell Haskell the types of your functions and variables it figures them out through a process called type inference. In essence, the compiler performs inference by starting with the types of things it knows and then working out the types of the rest of the values. Let's see how that works with a general example.
Example: Simple type inference
 We're deliberately not providing a type signature for this function isL c = c == 'l'
isL is a function that takes an argument c and returns the result of evaluating c == 'l'. Without a type signature, the type of c and the type of the result are not specified. In the expression c == 'l', however, the compiler knows that 'l' is a Char. Since c and 'l' are being compared with equality with (==) and both arguments of (==) must have the same type,^{[7]} it follows that c must be a Char. Finally, since isL c is the result of (==) it must be a Bool. And thus we have a signature for the function:
Example: isL
with a type
isL :: Char > Bool isL c = c == 'l'
Indeed, if you leave out the type signature, the Haskell compiler will discover it through this process. You can verify that by using :t on isL with or without a signature.
So, if type signatures are optional in most cases,^{[8]} why should we care so much about them? Here are a few reasons:
 Documentation: type signatures make your code easier to read. With most functions, the name of the function along with the type of the function is sufficient to guess what the function does. Of course, you should always comment your code properly too, but having the types clearly stated helps a lot, too.
 Debugging: when you annotate a function with a type signature and then make a typo in the body of the function which changes the type of a variable, the compiler will tell you, at compiletime, that your function is wrong. Leaving off the type signature might allow your erroneous function to compile, and the compiler would assign it the wrong type. You wouldn't know until you ran your program that you made this mistake.
Types and readability
To understand better how signatures can help documentation, here is a somewhat more realistic example. The piece of code quoted below is a tiny module (modules are the typical way of preparing a library), and this way of organizing code is not too different from what you might find when reading source code for the libraries bundled with GHC.
Note
Do not go crazy trying to understand how the functions here actually work; that is beside the point as we still have not covered many of the features being used. Just keep reading and play along.
Example: Module with type signatures
module StringManip where import Data.Char uppercase, lowercase :: String > String uppercase = map toUpper lowercase = map toLower capitalize :: String > String capitalize x = let capWord [] = [] capWord (x:xs) = toUpper x : xs in unwords (map capWord (words x))
This tiny library provides three string manipulation functions. uppercase
converts a string to upper case, lowercase
to lower case, and capitalize
capitalizes the first letter of every word. Each of these functions takes a String
as argument and evaluates to another String
. What is relevant to our discussion here is that, even if we do not understand how these functions work, looking at the type signatures allows us to immediately know the types of the arguments and return values. That information, when paired with sensible function names, can make it a lot easier to figure out how we can use the functions.
Note that when functions have the same type we have the option of writing just one signature for all of them, by separating their names with commas, as it was done with uppercase
and lowercase
.
Types prevent errors
The role of types in preventing errors is central to typed languages. When passing expressions around you have to make sure the types match up like they did here. If they don't, you'll get type errors when you try to compile; your program won't pass the typecheck. That is how types help you to keep your programs bugfree. To take a very trivial example:
Example: A nontypechecking program
"hello" + " world"
Having that line as part of your program will make it fail to compile, because you can't add two strings together! In all likelihood the intention was to use the similarlooking string concatenation operator, which joins two strings together into a single one:
Example: Our erroneous program, fixed
"hello" ++ " world"
An easy typo to make, but because you use Haskell, it was caught when you tried to compile. You didn't have to wait until you ran the program for the bug to become apparent.
That was only a simple example, but the idea of types forming a system to catch mistakes works on a much larger scale too. In general, when you make a change to your program, you'll change the type of one of the elements. If this change isn't something that you intended, or has unforeseen consequences, then it will show up immediately. A lot of Haskell programmers remark that once they have fixed all the type errors in their programs, and their programs compile, that they tend to "just work": run the first time with only minor problems. Runtime errors, where your program goes wrong when you run it rather than when you compile it, are much rarer in Haskell than in other languages. This is a huge advantage of having a strong type system like Haskell does.
Notes
 ↑ Lists, be they of characters or of other things, are very important entities in Haskell, and we will cover them in more detail in a little while.
 ↑ The deeper truth is that functions are values, just like all the others.
 ↑ This isn't quite what
chr
andord
do, but that description fits our purposes well, and it's close enough.  ↑ In fact, it is not even the only type for integers! We will meet its relatives in a short while.
 ↑ This method might seem just a trivial hack by now, but actually there are very deep reasons behind it, which we'll cover in the chapter on Currying.
 ↑ This has been somewhat simplified to fit our purposes. Don't worry, the essence of the function is there.
 ↑ As we discussed in "Truth values". That fact is actually stated by the type signature of (==) – if you are curious you can check it, although you will have to wait a little bit more for a full explanation of the notation used in it.
 ↑ There are a few situations in which the compiler lacks information to infer the type, and so the signature becomes obligatory; and, in some other cases, we can influence to a certain extent the final type of a function or value with a signature. That needn't concern us for the moment, however.
Lists and tuples
Lists and tuples are the two fundamental ways of manipulating several values. They both work by grouping multiple values into a single combined value.
Lists
Functions are one of the two major building blocks of any Haskell program. The other is the list. So let's switch over to the interpreter and build lists:
Prelude> let numbers = [1,2,3,4] Prelude> let truths = [True, False, False] Prelude> let strings = ["here", "are", "some", "strings"]
The square brackets delimit the list, and individual elements are separated by commas. The only important restriction is that all elements in a list must be of the same type. Trying to define a list with mixedtype elements results in a typical type error:
Prelude> let mixed = [True, "bonjour"] <interactive>:1:19: Couldn't match `Bool' against `[Char]' Expected type: Bool Inferred type: [Char] In the list element: "bonjour" In the definition of `mixed': mixed = [True, "bonjour"]
Building lists
In addition to specifying the whole list at once using square brackets and commas, you can build them up piece by piece using the (:) operator. This process is often referred to as consing^{[1]}.
Example: Consing something on to a list
Prelude> let numbers = [1,2,3,4] Prelude> numbers [1,2,3,4] Prelude> 0:numbers [0,1,2,3,4]
When you cons something on to a list (something:someList), what you get back is another list. Thus, you can keep on consing for as long as you wish. Note that the cons operator evaluates from right to left. Another (more general) way to think of it is that it takes the first value to its left and the whole expression to its right.
Example: Consing lots of things to a list
Prelude> 1:0:numbers [1,0,1,2,3,4] Prelude> 2:1:0:numbers [2,1,0,1,2,3,4] Prelude> 5:4:3:2:1:0:numbers [5,4,3,2,1,0,1,2,3,4]
In fact, this is how lists are actually built, by consing all elements to the empty list, []. The commasandbrackets notation is just syntactic sugar (which means a more pleasant and/or readable way to write code). So [1,2,3,4,5] is exactly equivalent to 1:2:3:4:5:[]
You will, however, want to watch out for a potential pitfall in list construction. Whereas something like True:False:[] is perfectly good Haskell, True:False is not:
Example: Whoops!
Prelude> True:False <interactive>:1:5: Couldn't match `[Bool]' against `Bool' Expected type: [Bool] Inferred type: Bool In the second argument of `(:)', namely `False' In the definition of `it': it = True : False
True:False produces a familiarlooking type error message, which tells us that the cons operator (:) (which is really just a function) expected a list as its second argument but we gave it another Bool instead. (:) only knows how to stick things onto lists.^{[2]}
So, when using cons, remember:
 The elements of the list must have the same type.
 You can only cons
(:)
something onto a list, not the other way around (you cannot cons a list onto an element). So, the final item on the right must be a list, and the items on the left must be independent elements, not lists.
Exercises 

let myCons list thing = 
Strings are just lists
As we briefly mentioned in the Type Basics module, strings in Haskell are just lists of characters. That means values of type String can be manipulated just like any other list. For instance, instead of entering strings directly as a sequence of characters enclosed in double quotation marks, they may also be constructed through a sequence of Char values, either linked with (:) and terminated by an empty list or using the commasandbrackets notation.
Prelude>"hey" == ['h','e','y'] True Prelude>"hey" == 'h':'e':'y':[] True
Using doublequoted strings is just more syntactic sugar.
Lists within lists
Lists can contain anything, just as long as they are all of the same type. Because lists are things too, lists can contain other lists! Try the following in the interpreter:
Example: Lists can contain lists
Prelude> let listOfLists = [[1,2],[3,4],[5,6]] Prelude> listOfLists [[1,2],[3,4],[5,6]]
Lists of lists can be pretty tricky sometimes, because a list of things does not have the same type as a thing all by itself; the type Int, for example, is different from [Int]. Let's sort through these implications with a few exercises:
Exercises 


Lists of different types of things cannot be consed, but the empty list can be consed with lists of anything. For example, []:[[1, 2], [1, 2, 3]] is valid and will produce [[], [1, 2], [1, 2, 3]], and [1]:[[1, 2], [1, 2, 3]] is valid and will produce [[1], [1, 2], [1, 2, 3]], but ['a']:[[1, 2], [1, 2, 3]] will produce an error message.
Lists of lists can be useful because they allow one to express some kinds of complicated, structured data (twodimensional matrices, for example). They are also one of the places where the Haskell type system truly shines. Human programmers, or at least this wikibook coauthor, get confused all the time when working with lists of lists, and having restrictions of types often helps in wading through the potential mess.
Tuples
A different notion of many
Tuples are another way of storing multiple values in a single value. There are two key differences between tuples and lists:
 Tuples have a fixed number of elements (immutable); you can't cons to a tuple. Therefore, it makes sense to use tuples when you know in advance how many values are to be stored. For example, we might want a type for storing 2D coordinates of a point. We know exactly how many values we need for each point (two – the x and y coordinates), so tuples are applicable.
 The elements of a tuple do not need to be all of the same type. For instance, in a phonebook application we might want to handle the entries by crunching three values into one: the name, phone number, and the address of each person. In such a case, the three values won't have the same type, so lists wouldn't help, but tuples would.
Tuples are created within parentheses with elements delimited by commas. Let's look at some sample tuples:
Example: Some tuples
(True, 1) ("Hello world", False) (4, 5, "Six", True, 'b')
The first example is a tuple containing two elements: the first one is True, and the second is 1. The next example again has two elements: the first is "Hello world", and the second is False. The third example is a tuple consisting of five elements: the first is 4 (a number), the second is 5 (another number), the third is "Six" (a string), the fourth is True (a boolean value), and the fifth is 'b' (a character).
A quick note on nomenclature: In general you use ntuple to denote a tuple of size n. 2tuples (that is, tuples with 2 elements) are normally called pairs and 3tuples triples. Tuples of greater sizes aren't actually all that common, but if you were to logically extend the naming system, you'd have quadruples, quintuples and so on, hence the general term tuple.
Exercises 


Tuples are also handy when you want to return more than one value from a function. In many languages, returning two or more things at once often requires wrapping them up in a singlepurpose data structure, maybe one that only gets used in that function. In Haskell, you have the very convenient alternative of just returning them as a tuple.
Tuples within tuples (and other combinations)
We can apply the same reasoning to tuples about storing lists within lists. Tuples are things too, so you can store tuples with tuples (within tuples up to any arbitrary level of complexity). Likewise, you could also have lists of tuples, tuples of lists, and all sorts of other combinations along the same lines.
Example: Nesting tuples and lists
((2,3), True) ((2,3), [2,3]) [(1,2), (3,4), (5,6)]
There is one bit of trickiness to watch out for, however. The type of a tuple is defined not only by its size, but by the types of objects it contains. For example, the tuples ("Hello",32)
and (47,"World")
are fundamentally different. One is of type (String,Int)
, whereas the other is (Int,String)
. This has implications for building up lists of tuples. We could very well have lists like [("a",1),("b",9),("c",9)]
, but having a list like [("a",1),(2,"b"),(9,"c")]
is right out. Can you spot the difference?
Exercises 


Retrieving values
So much for putting values into lists and tuples. If they are to be of any use, though, there must be a way of getting back the stored values!
Let's begin with pairs (that is, 2tuples). A very common use for them is to store the (x, y) coordinates of a point: imagine you have a chess board, and want to specify a specific square. You could do this by labelling all the ranks from 1 to 8, and similarly with the files. Then, a pair (2, 5)
could represent the square in rank 2 and file 5. Say we want to define a function for finding all the pieces in a given rank. One way of doing this would be to find the coordinates of all the pieces, then look at the rank part and see whether it's equal to whatever row we're being asked to examine. Once it had the coordinate pair (x, y)
of a piece, the function would need to extract the x
(the rank coordinate). To do that there are two functions, fst
and snd
, that retrieve^{[3]} the first and second elements out of a pair, respectively. Let's see some examples:
Example: Using fst
and snd
Prelude> fst (2, 5) 2 Prelude> fst (True, "boo") True Prelude> snd (5, "Hello") "Hello"
Note that these functions only work on pairs. Why? Yet again, it has to do with types. Pairs and triples (and quadruples, etc.) have necessarily different types, and fst
and snd
only accept pairs as arguments.^{[4]}
As for lists, the functions head
and tail
are roughly analogous to fst
and snd
, in that they disassemble a list by taking apart what (:)
joined: head
evaluates to the first element of the list, while tail
gives the rest of the list.
Example: Using head
and tail
Prelude> 2:[7,5,0] [2,7,5,0] Prelude> head [2,7,5,0] 2 Prelude> tail [2,7,5,0] [7,5,0]
Unfortunately, there is a serious problem with head
and tail
. If we apply either of them to an empty list...
Prelude> head [] *** Exception: Prelude.head: empty list
... it blows up, as an empty list has no first element, nor any other elements at all. Had this happened in a full program rather than in GHCi, it would crash. We would rather avoid functions that could cause our programs to malfunction and thus leave us with an egg on our faces; therefore, while we will play with head
and tail
for the moment, we will be on the lookout for better options.
Note
One possible reaction to the warning we just gave would be "What is the problem? Using head
and tail
is fine if we are careful and never pass them an empty list, or if we somehow test whether a list is empty before calling them." But that way lies madness.
As programs get bigger and more complicated, the number of places in which an empty list that could end up being passed to head
and tail
grows quickly; and so does the number of places in which we might make a mistake. As a rule of thumb, you should avoid functions that might fail without warning, producing errors. As we advance through the book, we will see that there almost always is a better way to deal with failure.
Pending questions
The four functions introduced here do not appear to be enough to fully solve the problem we started this section with. While fst
and snd
provide a satisfactory solution for pairs, what about tuples with three or more elements? And with lists, can't we do any better than just breaking them after the first element? head
and tail
just don't seem to cut it. For the moment, we will have to leave these questions pending, but don't worry  the issues are perfectly solvable. Once we do some necessary groundwork we will return to this subject with a number of chapters on list manipulation. We will explain there how separating head and tail allows us to do anything we want with lists.
Exercises 


Polymorphic types
As you may have found out already by playing with :t, the type of a list depends on the types of its elements, and is denoted by enclosing it in square brackets:
Prelude>:t [True, False] [True, False] :: [Bool] Prelude>:t ["hey", "my"] ["hey", "my"] :: [[Char]]
Therefore, lists of Bool have different types than lists of [Char] (that is, strings), of Int and so on. Since functions only accept arguments of the types specified in the type of the function, that leads to some practical complications. For example, imagine a function that finds the length of a list. But since [Int], [Bool] and [String] are different types it seems we would need separate functions for each case – lengthInts :: [Int] > Int
, as well as a lengthBools :: [Bool] > Int
, as well as a lengthStrings :: [String] > Int
, as well as a...
That would be horribly frustrating because counting how many things there are in a list should be independent of what the things actually are. Fortunately, it does not work like that: there is a single function length, which works on all lists. But how can that possibly work? As usual, checking the type of length provides a good hint that there is something different going on...
Example: Our first polymorphic type
Prelude>:t length length :: [a] > Int
The a in the square brackets is not a type – remember that type names always start with uppercase letters. Instead, it is a type variable. When Haskell sees a type variable, it allows any type to take its place. This is exactly what we want. In type theory (a branch of mathematics), this is called polymorphism: functions or values with only a single type are called monomorphic, and things that use type variables to admit more than one type are polymorphic.
Note that within a single type signature, all cases of the same type variable must be of the same type. For example,
f :: a > a
means that f takes an argument of any type and gives something of the same type as the argument, as opposed to
f :: a > b
which means that f takes an argument of any type and gives a result of any type. Like a, b is another type variable. In any given function call, the type of the value assigned to the a may or may not match the type of whatever we have for b.
Example: fst
and snd
As we saw, you can use the fst
and snd
functions to extract parts of pairs. By now, you should already be building the habit of wondering "what type is this?" about every function you come across. Let's consider the cases of fst
and snd
. These two functions take a pair as their argument and return one element of this pair. First of all, the type of a pair depends on the type of its elements, just as with lists, so the functions need to be polymorphic. Also it is important to keep in mind that pairs, and tuples in general, don't have to be homogeneous with respect to types; their different parts can be different types. So if we were to say:
fst :: (a, a) > a
That would mean fst would only work if the first and second part of the pair given as input had the same type. So what is the correct type? Simply:
Example: The types of fst
and snd
fst :: (a, b) > a snd :: (a, b) > b
Note that if you knew nothing about fst and snd other than the type signatures you might guess that they return the first and second parts of a pair, respectively. Although that is correct, the type signature isn't limited to this case. All the signatures say is that they just have to return something with the same type of the first and second parts of the pair.
Exercises 

Give type signatures for the following functions:

Summary
We have introduced two new notions in this chapter: lists and tuples. Let us sum up the key similarities and differences between them:
 Lists are defined by square brackets and commas :
[1,2,3]
. Lists can contain anything as long as all the candidate elements of the list are of the same type.
 Lists can also be built by the cons operator,
(:)
, but you can only cons things onto lists.
 Tuples are defined by parentheses and commas :
("Bob",32)
 Tuples contain anything, even things of different types.
 The length of a tuple is encoded in its type. That is, two tuples with different lengths will have different types.
 Lists and tuples can be combined in any number of ways: lists within lists, tuples with lists, etc, but their criteria must still be fulfilled for the combinations to be valid.
Notes
 ↑ You might object that "cons" isn't even a proper word. Well, it isn't. LISP programmers invented the verb "to cons" to refer to this specific task of appending an element to the front of a list. "cons" happens to be a mnemonic for "constructor". Later on we will see why that makes sense.
 ↑ At this point you might be justified in seeing types as an annoying thing. In a way they are, but more often than not they are actually a lifesaver. In any case, when you are programming in Haskell and something blows up, you'll probably want to think "type error".
 ↑ Or, more technically, "... projections that project the elements..." In mathspeak, a function that gets some data out of a structure is called a projection.
 ↑ Yes, there are ways that a function could be designed to extract the first thing from any size tuple, but it wouldn't be as simple as you might think, and it isn't how the fst and snd functions work.
Type basics II
So far, we have shrewdly avoided number types in our examples. In one exercise, we even went as far as asking you to "pretend" the arguments to (+) had to be of type Int. So, from what are we hiding?
In this chapter, we will show how numerical types are handled in Haskell. While doing so, we will introduce some important features of the type system. Before diving into the text, though, pause for a moment and consider the following question: what should be the type of the function (+)?^{[1]}
The Num class
As far as everyday mathematics is concerned, there are very few restrictions on which kind of numbers we can add together. (two natural numbers), (a negative integer and a rational number), (a rational and an irrational)... all of these are valid – indeed, any two real numbers can be added together. In order to capture such generality in the simplest way possible we would like to have a very general Number type in Haskell, so that the signature of (+) would be simply
(+) :: Number > Number > Number
That design, however, does not fit well with the way computers perform arithmetic. While integer numbers in programs can be quite straightforwardly handled as sequences of binary digits in memory, that approach does not work for noninteger real numbers,^{[2]} thus making it necessary for a more involved encoding to support them: floating point numbers. While floating point provides a reasonable way to deal with real numbers in general, it has some inconveniences (most notably, loss of precision) which make using the simpler encoding worthwhile for integer values. We are thus left with at least two different ways of storing numbers, one for integers and another one for general real numbers, which should correspond to different Haskell types. Furthermore, computers are only able to perform operations like (+) on a pair of numbers if they are in the same format. That should put an end to our hopes of using a universal Number type – or even having (+) working with both integers and floatingpoint numbers...
It is easy, however, to see reality is not that bad. We can use (+) with both integers and floating point numbers:
Prelude>3 + 4 7 Prelude>4.34 + 3.12 7.46
When discussing lists and tuples, we saw that functions can accept arguments of different types if they are made polymorphic. In that spirit, one possible type signature for (+) that would account for the facts above would be:
(+) :: a > a > a
(+) would then take two arguments of the same type a (which could be integers or floatingpoint numbers) and evaluate to a result of type a. There is a problem with that solution, however. As we saw before, the type variable a can stand for any type at all. If (+) had that type signature we would be able to (+) two Bool, or two Char, which would make very little sense. Rather, the actual type signature of (+) takes advantage of a language feature that allows us to express the semantic restriction that a can be any type as long as it is a number type:
(+) :: (Num a) => a > a > a
Num is a typeclass  a group of types which includes all types which are regarded as numbers^{[3]}. The (Num a) => part of the signature restricts a to number types – or, more accurately, instances of Num.
Numeric types
But what are the actual number types – the instances of Num that a stands for in the signature? The most important numeric types are Int, Integer and Double:
 Int corresponds to the vanilla integer type found in most languages. It has fixed maximum and minimum values that depend on a computer's processor. (In 32bit machines the range goes from 2147483648 to 2147483647).
 Integer also is used for integer numbers, but unlike Int it supports arbitrarily large values – at the cost of some efficiency.
 Double is the doubleprecision floating point type, a good choice for real numbers in the vast majority of cases. (There is also Float, the singleprecision counterpart of Double, which is usually less attractive due to further loss of precision.)
These types are available by default in Haskell and are the ones you will generally deal with in everyday tasks.
Polymorphic guesswork
There is one thing we haven't explained yet. If you tried the examples of addition we mentioned at the beginning you know that something like this is perfectly valid:
Prelude> (7) + 5.12 1.88
Here, it seems we are adding two numbers of different types – an integer and a noninteger. Shouldn't the type of (+) make that impossible?
To answer that question we have to see what the types of the numbers we entered actually are:
Prelude> :t (7) (7) :: (Num a) => a
And, lo and behold, (7) is neither Int nor Integer! Rather, it is a polymorphic constant, which can "morph" into any number type if need be. The reason for that becomes clearer when we look at the other number...
Prelude> :t 5.12 5.12 :: (Fractional t) => t
5.12 is also a polymorphic constant, but one of the Fractional class, which is more restrictive than Num – every Fractional is a Num, but not every Num is a Fractional (for instance, Ints and Integers are not Fractional).
When a Haskell program evaluates (7) + 5.12, it must settle for an actual type for the numbers. It does so by performing type inference while accounting for the class specifications. (7) can be any Num, but there are extra restrictions for 5.12, so its type will define what (7) will become. Since there is no other clues to what the types should be, 5.12 will assume the default Fractional type, which is Double; and, consequently, (7) will become a Double as well, allowing the addition to proceed normally and return a Double^{[4]}.
There is a nice quick test you can do to get a better feel of that process. In a source file, define
x = 2
then load the file in GHCi and check the type of x. Then, change the file to add a y variable,
x = 2 y = x + 3
reload it and check the types of x and y. Finally, modify y to
x = 2 y = x + 3.1
and see what happens with the types of both variables.
Monomorphic trouble
The sophistication of the numerical types and classes occasionally leads to some complications. Consider, for instance, the common division operator (/). It has the following type signature:
(/) :: (Fractional a) => a > a > a
Restricting a to fractional types is a must because the division of two integer numbers will often not result in an integer. Nevertheless, we can still write something like
Prelude> 4 / 3 1.3333333333333333
because the literals 4 and 3 are polymorphic constants and therefore assume the type Double at the behest of (/). Suppose, however, we want to divide a number by the length of a list^{[5]}. The obvious thing to do would be using the length function:
Prelude> 4 / length [1,2,3]
Unfortunately, that blows up:
<interactive>:1:0: No instance for (Fractional Int) arising from a use of `/' at <interactive>:1:017 Possible fix: add an instance declaration for (Fractional Int) In the expression: 4 / length [1, 2, 3] In the definition of `it': it = 4 / length [1, 2, 3]
As usual, the problem can be understood by looking at the type signature of length:
length :: [a] > Int
The result of length is not a polymorphic constant, but an Int; and since an Int is not a Fractional it can't fit the signature of (/).
There is a handy function which provides a way of escaping from this problem. Before following on with the text, try to guess what it does only from the name and signature:
fromIntegral :: (Integral a, Num b) => a > b
fromIntegral takes an argument of some Integral type (like Int or Integer) and makes it a polymorphic constant. By combining it with length we can make the length of the list fit into the signature of (/):
Prelude> 4 / fromIntegral (length [1,2,3]) 1.3333333333333333
While this expression may look overly complex at first, this approach makes it easier to be rigorous when manipulating numbers. If you define a function with an Int argument, it will never be converted to an Integer or Double, unless you explicitly tell the program to do so by using a function like fromIntegral. As a direct consequence of its refined type system, there is a surprising diversity of classes and functions dealing with numbers in Haskell.
Classes beyond numbers
There are many other use cases for typeclasses beyond arithmetic. For example, the type signature of (==) is:
(==) :: (Eq a) => a > a > Bool
Like (+) or (/), (==) is a polymorphic function. It compares two values of the same type, which must belong to the class Eq and returns a Bool. Eq is simply the class of types of values which can be compared for equality, and includes all of the basic nonfunctional types.^{[6]}
Typeclasses are a very general language feature which adds a lot to the power of the type system. Later in the book we will return to this topic to see how to use them in custom ways.
Notes
 ↑ If you followed our recommendations in "Type basics", chances are you have already seen the rather exotic answer by testing with :t... if that is the case, consider the following analysis as a path to understanding the meaning of that signature.
 ↑ One of the reasons being that between any two real numbers there are infinitely many real numbers – and that can't be directly mapped into a representation in memory no matter what we do.
 ↑ That is a very loose definition, but will suffice until we are ready to discuss typeclasses in more detail.
 ↑ For seasoned programmers: This appears to have the same effect that programs in C (and many other languages) manage with an implicit cast – by which an integer literal is silently converted to a double. The difference is that in C, the conversion is done behind your back, while in Haskell it only occurs if the variable/literal is a polymorphic constant. The difference will become clearer shortly, when we show a counterexample.
 ↑ A reasonable scenario – think of computing an average of the values in a list.
 ↑ Comparing two functions for equality is considered to be intractable
Building vocabulary
This chapter will be somewhat different from the surrounding ones. Think of it as an interlude, where the main goal is not to introduce new features, but to present advice for studying (and using!) Haskell. Here, we will discuss the importance of acquiring a vocabulary of functions and how this book, along with other resources, can help you with that. First, however, we need to make a few quick points about function composition.
Function composition
Function composition is a really simple concept. It just means applying one function to a value and then applying another function to the result. Consider these two very simple functions:
Example: Simple functions
f x = x + 3 square x = x ^ 2
We can compose them in two different ways, depending on which one we apply first:
Prelude> square (f 1) 16 Prelude> square (f 2) 25 Prelude> f (square 1) 4 Prelude> f (square 2) 7
The parentheses around the inner function are necessary; otherwise, the interpreter would think that you were trying to get the value of square f
, or f square
; and both have no meaning.
The composition of two functions results in a function in its own right. If applying f and then square, or viceversa, to a number were a frequent, meaningful or otherwise important operation in a program, a natural next step would be defining:
Example: Composed functions
squareOfF x = square (f x) fOfSquare x = f (square x)
There is a second, nifty way of writing composed functions. It uses (.)
, the function composition operator, and is as simple as putting a period between the two functions:
Example: Composing functions with (.)
squareOfF x = (square . f) x fOfSquare x = (f . square) x
Note that functions are still applied from right to left, so that g(f(x)) == (g . f) x
^{[1]}.
The need for a vocabulary
Function composition allows us to define complicated functions using simpler ones as building blocks. One of the key qualities of Haskell is how simple it is to write composed functions, no matter if the base functions are written by ourselves or by someone else,^{[2]} and the extent that helps us in writing simple, elegant and expressive code.
In order to use function composition, we first need to have functions to compose. While naturally the functions we write ourselves will always be available, every installation of GHC comes with a vast assortment of libraries (that is, packaged code), which provide functions for various common tasks. For that reason, it is vital for effective Haskell programming to develop some familiarity with the essential libraries. At the very least, you should know how to find useful functions in the libraries when you need them.
We can look at this issue from a different perspective. We have gone through a substantial portion of the Haskell syntax already; and, by the time we are done with the upcoming Recursion chapter, we could, in principle, write pretty much any list manipulation program we want. However, writing full programs at this point would be terribly inefficient, mainly because we would end up rewriting large parts of the standard libraries. It is far easier to have the libraries deal as much as possible with trivial wellknown problems while we dedicate our brain cells to solving the problems we are truly interested in. Furthermore, the functionality provided by libraries helps us in developing our own algorithms.^{[3]}
Prelude and the libraries
Here are a few basic facts about Haskell libraries:
First and foremost, there is Prelude, which is the core library loaded by default in every Haskell program. Alongside with the basic types, it provides a set of ubiquitous and extremely useful functions. We will refer to Prelude and its functions all the time throughout these introductory chapters.
Beyond Prelude, there is a set of core libraries, which provide a much wider range of tools. Although they are provided by default with GHC, they are not loaded automatically like Prelude. Instead, they are made available as modules, which must be imported into your program. Later on, we will explain the minutiae of how modules work. For now, just know that your source file needs lines near the top to import any necessary modules. For example, the function permutations
is in the module Data.List
, and, to import that, add the line import Data.List
to the top of your .hs file. Here's how a full source file looks:
Example: Importing a module in a source file
import Data.List testPermutations = permutations "Prelude"
For quick GHCi tests, just enter :m +Data.List
at the command line to load that module.
Prelude> :m +Data.List Prelude Data.List> :t permutations permutations :: [a] > [[a]]
One exhibit
Before continuing, let us see one (slightly histrionic, we admit) example of what familiarity with a few basic functions from Prelude can bring us.^{[4]} Suppose we need a function which takes a string composed of words separated by spaces and returns that string with the order of the words reversed, so that "Mary had a little lamb"
becomes "lamb little a had Mary"
. Now, we can solve that problem using exclusively what we have seen so far about Haskell, plus a few insights that can be acquired by studying the Recursion chapter. Here is what it might look like. Don't stare at it for too long!
Example: There be dragons
monsterRevWords :: String > String monsterRevWords input = rejoinUnreversed (divideReversed input) where divideReversed s = go1 [] s where go1 divided [] = divided go1 [] (c:cs)  testSpace c = go1 [] cs  otherwise = go1 [[]] (c:cs) go1 (w:ws) [c]  testSpace c = (w:ws)  otherwise = ((c:w):ws) go1 (w:ws) (c:c':cs)  testSpace c = if testSpace c' then go1 (w:ws) (c':cs) else go1 ([c']:w:ws) cs  otherwise = if testSpace c' then go1 ((c:w):ws) (c':cs) else go1 ((c:w):ws) (c':cs) testSpace c = c == ' ' rejoinUnreversed [] = [] rejoinUnreversed [w] = reverseList w rejoinUnreversed strings = go2 (' ' : reverseList newFirstWord) (otherWords) where (newFirstWord : otherWords) = reverseList strings go2 rejoined ([]:[]) = rejoined go2 rejoined ([]:(w':ws')) = go2 (rejoined) ((' ':w'):ws') go2 rejoined ((c:cs):ws) = go2 (c:rejoined) (cs:ws) reverseList [] = [] reverseList w = go3 [] w where go3 rev [] = rev go3 rev (c:cs) = go3 (c:rev) cs
There are too many problems with this thing; so let us consider just three of them:
 If we claimed that
monsterRevWords
does what is expected, you could either take our word for it, test it exhaustively on all sorts of possible inputs or attempt to understand it and get an awful headache (please don't).  Furthermore, if we write a function this ugly and have to fix a bug or slightly modify it later on,^{[5]} we are set for an awful time.
 Finally, there is at least one easy to spot potential problem: if you have another glance at the definition, about halfway down there is a
testSpace
helper function which checks if a character is a space or not. The test, however, only includes the common space character (that is,' '
), and not other whitespace characters (tabs, newlines, etc.)^{[6]}.
Instead of the junk above, we can do much better by using the following Prelude functions:
words
, which reliably breaks down a string in whitespace delimited words, returning a list of strings;reverse
, which reverses a list (incidentally, that is exactly what thereverseList
above does); andunwords
, which does the opposite ofwords
;
then function composition means our problem is instantly solved.
Example: revWords
done the Haskell way
revWords :: String > String revWords input = (unwords . reverse . words) input
That's short, simple, readable and, since Prelude is reliable, bugfree.^{[7]} So, any time some program you are writing begins to look like monsterRevWords
, look around and reach for your toolbox  the libraries.
Acquiring vocabulary
After the stern warnings above, you might expect us to continue with diving deep into the standard libraries. That is not the route we will follow, however  at least not in the first part of the book. The Beginner's Track is meant to cover most of the Haskell language functionality in a readable and reasonably compact account, and a linear, systematic study of the libraries would in all likelihood have us sacrificing either one attribute or the other.
In any case, the libraries will remain close at hand as we advance in the course (so there's no need for you to pause your reading just to study the libraries on your own). Here are a few suggestions on resources you can use to learn about them.
With this book
 Once we enter Elementary Haskell, you will notice several of the exercises  mainly, among those about list processing  involve writing equivalent definitions for Prelude functions. For each of these exercises you do, one more function will be added to your repertoire.
 Every now and then we will introduce more library functions; maybe within an example, or just with a mention in passing. Whenever we do so, take a minute to test the function and do some experiments. Remember to extend that habitual curiosity about types we mentioned in Type basics to the functions themselves.
 While the first few chapters are quite tightlyknit, later parts of the book are more independent — especially the third track, Haskell in Practice. There, among other things, you can find chapters on the Hierarchical libraries; and most of their content can be understood soon after having completed Elementary Haskell.
 As we reach the later parts of the Beginner's track, the concepts we will discuss (monads in particular) will naturally lead to exploration of important parts of the core libraries.
Other resources
 First and foremost, there is the documentation. While it is probably too dry to be really useful right now, it will prove valuable soon enough. You can read the Prelude specification online as well as the documentation of the libraries bundled with GHC, with nice navigation and source code just one click away.
 Hoogle is a great way to search through the documentation. It is a Haskell search engine which covers the core libraries. You can search for everything from function names to type definitions and more.
 Beyond the libraries included with GHC, there is a large ecosystem of libraries, made available through Hackage and installable with a tool called cabal. The Hackage site you can find documentation for the libraries available through it. We will not venture outside of the core libraries in the Beginner's Track; however, you will certainly be drawn to Hackage once you begin your own projects. A second Haskell search engine is Hayoo!; it covers all of Hackage.
 When appropriate, we will give pointers to other useful learning resources, specially when we move towards intermediate and advanced topics.
Notes
 ↑
(.)
is modelled after the mathematical operator , which works in the same way:  ↑ Such ease is not only due to the bits of syntax we mentioned above, but mainly due to features we will explain and discuss in depth later in the book  in particular, higherorder functions.
 ↑ One simple example is provided by functions like
map
,filter
and the folds, which we will cover in the chapters on list processing just ahead. Another would be the various monad libraries, which will be studied in depth later on.  ↑ The example here is inspired by the Simple Unix tools demo in the HaskellWiki.
 ↑ Coauthor's note: "Later on? I wrote that half an hour ago and I'm not totally sure about how it works already..."
 ↑ A reliable way of checking whether a character is whitespace is with the
isSpace
function, which is in the moduleData.Char
.  ↑ In case you are wondering, there are lots of other functions, either in Prelude or in
Data.List
which, in one way or another, would help to makemonsterRevWords
somewhat saner  just to name a few:(++)
,concat
,groupBy
,intersperse
. There is no need for them in this case, though, since nothing compares to the oneliner above.
Next steps
This chapter introduces pattern matching, a key feature of Haskell, and two new pieces of syntax: if
expressions and let
bindings.
if / then / else
Haskell syntax supports gardenvariety conditional expressions of the form if... then... (else ...). For instance, consider a function that returns (1)
if its argument is less than 0
; 0
if its argument is 0
; and 1
if its argument is greater than 0
. There is a predefined function which does that job already (it is called signum
); for the sake of illustration, though, let's define a version of our own:
Example: The signum function.
mySignum x = if x < 0 then 1 else if x > 0 then 1 else 0
You can experiment with this as:
*Main> mySignum 5 1 *Main> mySignum 0 0 *Main> mySignum (5  10) 1 *Main> mySignum (1) 1
The parentheses around "1" in the last example are required; if missing, the system will think you are trying to subtract 1
from mySignum
, which is illtyped.
In an if/then/else construct, first the condition (in this case x < 0
) is evaluated. If it results True
, the whole construct evaluates to the then expression; otherwise (if the condition is False
), the construct evaluates to the else expression. All of that is pretty intuitive. If you have programmed in an imperative language before, however, it might seem surprising to know that Haskell always requires both a then and an else clause. This is because the construct has to result in a value in both cases  more specifically, a value of the same type in both cases.
if / then / else function definitions like the one above can be easily rewritten with the guards syntax presented in past modules:
Example: From if to guards
mySignum x  x < 0 = 1  x > 0 = 1  otherwise = 0
And conversely, the absolute value function in Truth values can be rendered with if/then/else:
Example: From guards to if
abs x = if x < 0 then x else x
Why use if/then/else versus guards? As you will see with later examples and in your own programming, each way of handling conditionals may be more readable or convenient depending on the circumstances. In many cases, both options work equally well.
Introducing pattern matching
Suppose we are writing a program which tracks statistics from a racing competition in which racers receive points based on their classification in each race, the scoring rules being:
 10 points for the winner;
 6 for secondplaced;
 4 for thirdplaced;
 3 for fourthplaced;
 2 for fifthplaced;
 1 for sixthplaced;
 no points for other racers.
We can write a simple function which takes a classification (represented by an integer number: 1
for first place, etc.^{[1]}) and returns how many points were earned. One possible solution uses if/then/else:
Example: Computing points with if/then/else
pts :: Int > Int pts x = if x == 1 then 10 else if x == 2 then 6 else if x == 3 then 4 else if x == 4 then 3 else if x == 5 then 2 else if x == 6 then 1 else 0
Yuck! Admittedly, it wouldn't look this hideous had we used guards instead of if/then/else, but it still would be tedious to write (and read!) all those equality tests. We can do better, though:
Example: Computing points with a piecewise definition
pts :: Int > Int pts 1 = 10 pts 2 = 6 pts 3 = 4 pts 4 = 3 pts 5 = 2 pts 6 = 1 pts _ = 0
Much better. However, even though defining pts
in this style (which we will arbitrarily call piecewise definition from now on) shows to a reader of the code what the function does in an awesomely clear way, the syntax looks odd given what we have seen of Haskell so far. Why are there seven equations for pts
? What are those numbers doing in their lefthand sides? Where has the x
gone?
The example above is our first encounter with a key feature of Haskell called pattern matching. When we call the second version of pts
, the argument is matched against the numbers on the left side of each of the equations, which in turn are the patterns. This matching is done in the order we wrote the equations; so first of all the argument is matched against the 1
in the first equation. If the argument is indeed 1
, we have a match and the first equation is used; and so pts 1
evaluates to 10
as expected. Otherwise, the other equations are tried in order following the same procedure. The final one, though, is rather different: the _
is a special pattern, often called a "wildcard", that might be read as "whatever": it matches with anything; and therefore if the argument doesn't match any of the previous patterns pts
will return zero.
As for why there is no x
or any other variable standing for the argument, it is simply because we don't need that to write the definitions. All possible return values are constants; and since the point of specifying a variable name on the left side is using it to write the right side, the x
is unnecessary in our function.
There is, however, an obvious way to make pts
even more concise. The points given to a racer decrease regularly from third place to sixth place, at a rate of one point per position. After noticing that, we can eliminate three of the seven equations as follows:
Example: Mixing styles
pts :: Int > Int pts 1 = 10 pts 2 = 6 pts x  x <= 6 = 7  x  otherwise = 0
The first thing to point out here is that we can mix both styles of definitions. In fact, when we write pts x
in the left side of an equation we are using pattern matching too! As a pattern, the x
(or any other variable name) matches anything just like _
; the only difference being that it also gives us a name to use on the right side (which, in this case, is necessary to write 7  x
).
Exercises 

We cheated a little when moving from the second version of pts to the third one: they do not do exactly the same thing. Can you spot what the difference is? 
Beyond integers, pattern matching works with values of various other types. One handy example are booleans. For instance, the ()
logicalor operator we met in Truth values could be defined as:
Example: ()
() :: Bool > Bool > Bool False  False = False _  _ = True
Or:
Example: ()
, done another way
() :: Bool > Bool > Bool True  _ = True False  y = y
When matching two or more arguments at once, the equation will only be used if all of them match.
To conclude this section, let us discuss a few things that might go wrong when using pattern matching:
 If we put a pattern which matches anything (such as the final patterns in each of the
pts
example) before the more specific ones the latter will be ignored. GHC(i) will typically warn us that "Pattern match(es) are overlapped" in such cases.  If no patterns match, an error will be triggered. Generally, it is a good idea to ensure the patterns cover all cases, in the same way that the
otherwise
guard is not mandatory but highly recommended.  Finally, while you can play around with various ways of (re)defining
(&&)
^{[2]}, here is one version that will not work:
(&&) :: Bool > Bool > Bool x && x = x  oops! _ && _ = False
 The program won't test whether the arguments are equal just because we happened to use the same name for both. As far as the matching goes, we could just as well have written
_ && _
in the first case. And even worse: since we gave the same name to both arguments, GHC(i) will refuse the function due to "Conflicting definitions for `x'".
Tuple and list patterns
While the examples above show that pattern matching helps in writing more elegant code, that does not explain why it is so important. So, let's consider the problem of writing a definition for fst
, the function which extracts the first element of a pair. At this point, that appears to be an impossible task, as the only way of accessing the first value of the pair is by using fst
itself... The following function, however, does the same thing as fst
(confirm it in GHCi):
Example: A definition for fst
fst' :: (a, b) > a fst' (x, _) = x
It's magic! Instead of using a regular variable in the left side of the equation, we specified the argument with the pattern of the 2tuple  that is, (,)
 filled with a variable and the _
pattern. Then the variable was automatically associated with the first component of the tuple, and we used it to write the right side of the equation. The definition of snd
is, of course, analogous.
Furthermore, the trick demonstrated above can be done with lists as well. Here are the actual definitions of head
and tail
:
Example: head
, tail
and patterns
head :: [a] > a head (x:_) = x head [] = error "Prelude.head: empty list" tail :: [a] > [a] tail (_:xs) = xs tail [] = error "Prelude.tail: empty list"
The only essential change in relation to the previous example was replacing (,)
with the pattern of the cons operator (:)
. These functions also have an equation using the pattern of the empty list, []
; however, since empty lists have no head or tail there is nothing to do other than use error
to print a prettier error message.
In summary, the real power of pattern matching comes from how it can be used to access the parts of a complex value. Pattern matching on lists, in particular, will be extensively deployed in Recursion and the chapters that follow it. Later on, we will explore what is happening behind this seemingly magical feature.
let bindings
To conclude this chapter, a brief word about let
bindings, which are an alternative to where
clauses for making local declarations. For instance, take the problem of finding the roots of a polynomial of the form (or, in other words, the solution to a second degree equation  think back to your middle school math courses). Its solutions are given by:
 .
We could write the following function to compute the two values of :
roots a b c = ((b + sqrt(b * b  4 * a * c)) / (2 * a), (b  sqrt(b * b  4 * a * c)) / (2 * a))
Writing the sqrt(b * b  4 * a * c)
term in both cases is annoying, though; we can use a local binding instead, using either where
or, as will be demonstrated below, a let
declaration:
roots a b c = let sdisc = sqrt (b * b  4 * a * c) in ((b + sdisc) / (2 * a), (b  sdisc) / (2 * a))
We put the let
keyword before the declaration, and then use in
to signal we are returning to the "main" body of the function. It is possible to put multiple declarations inside a single let
...in
block  just make sure they are indented the same amount, otherwise there will be syntax errors:
roots a b c = let sdisc = sqrt (b * b  4 * a * c) twice_a = 2 * a in ((b + sdisc) / twice_a, (b  sdisc) / twice_a)
Because indentation matters syntactically in Haskell, you need to be careful about whether you are using tabs or spaces. By far the best solution is to configure your text editor to insert two or four spaces in place of tabs. If you keep tabs as distinct, at least ensure that your tabs have always the same length, or you're likely to run into trouble. 
Note
Still on indentation, the Indentation chapter has a full account of indentation rules; so if doubts about that arise as you code you might want to give it a glance.
Notes
 ↑ Here we will not be much worried about what happens if a nonsensical value (say,
(4)
) is passed to the function. In general, however, it is a good idea to give some thought to such "strange" cases, in order to avoid nasty surprises down the road.  ↑ If you are going to experiment with it in GHCi, call your version something else to avoid a name clash; say, (&!&).
Simple input and output
Back to the real world
So far, we have discussed many examples of functions that calculate values. Of course, we also want to use our programs for other things. For example, the standard program in the beginning of tutorials about other languages: a program that displays a "hello world" greeting. Here's one Haskell version:
Prelude> putStrLn "Hello, World!"
putStrLn
is one of the standard Prelude functions. As the "putStr" part of the name suggests, it takes a String
as an argument and prints it to the screen. The "Ln" indicates it also prints a line break, so that whatever else is printed next will appear on a new line.
So now you should be thinking, "what is the type of the putStrLn function?" It takes a String
and gives… um… what? What do we call that? The program doesn't get something back that it can use in another function. Instead, the result involves having the computer change the screen. In other words, it does something in the world outside of the program. What type could that have? Let's see what GHCi tell us:
Prelude> :t putStrLn putStrLn :: String > IO ()
"IO" stands for "input and output". Wherever there is IO
in a type, interaction with the world outside the program is involved. We'll call IO
values, such as the result of putStrLn
, actions. The other part of the IO
type, in this case ()
, is the type of the return value of the action; that is, the type of what it gives back to the program (as opposed to what it does outside the program). ()
(read as "unit") is an uninteresting type with just a single value, also called ()
. Since putStrLn
sends output to the world but doesn't return anything to the program, ()
is used as a placeholder. We might read IO ()
as "action which returns ()
", just like we read [Int]
as "list of Int
elements".
Here are just a few examples of when we need to use IO:
 print a string to the screen
 read a string from a keyboard
 write data to a file
 read data from a file
What makes IO actually work? Lots of things happen behind the scenes to take us from a putStrLn
to pixels in the screen; however, we don't have to worry about them right now. What we have to know is that a complete Haskell program is actually a big IO action that is run when the program is executed. In a compiled program, this action is called main
, and has type IO ()
. From this point of view, to write a Haskell program is to combine actions and functions to form the overall function main
that will be executed when the program is run.
Exercises 

Back in the Type Basics chapter, we mentioned that the type of the openWindow function had been simplified. Can you guess what the simplification was? 
Sequencing actions with do
do notation provides a convenient means of putting actions together, which is essential in getting useful things done with Haskell. Let's see what it looks like by considering a more complex program:
Example: What is your name?
main = do putStrLn "Please enter your name: " name < getLine putStrLn ("Hello, " ++ name ++ ", how are you?")
Note
Even though do
notation looks very different from the Haskell code we have seen so far, it is just syntactic sugar for a handful of functions, the most important of them being the (>>=)
operator. Ideally, we would explain how those functions work and then introduce do
notation. However, there are a number of topics we need to go through before we can give a convincing explanation, notably higher order functions and type classes. Jumping in with do
right now is a pragmatic short cut that will allow you to start writing complete programs with IO right now. We will see why do
works later in the book, beginning with the Understanding monads chapter.
Before we get into how do works, take a look at getLine
. It goes to the outside world, in this case to the terminal, and brings back a String
from it. What is its type?
Prelude> :t getLine getLine :: IO String
That means getLine
is an IO action that, when run, will return a String
. But what about the input? While functions have types like a > b
which reflect that they take arguments and give back results, getLine
doesn't actually take an argument. It takes as input whatever is in the line in the terminal. However, that line in the outside world can't be a value with a type because it isn't even in Haskell yet! The Haskell program can't know in advance what it will be, and indeed the value could be different every time.
As there is no way to predict the exact results of IO actions (since the program doesn't know the state of the outside world until runtime), they have to be executed in a predictable sequence defined in advance in our code. With regular functions that do not perform IO, the exact sequencing of execution is less of a concern as long as the results eventually go to the right places.
In our name program, we're sequencing three actions: a putStrLn
with a greeting, a getLine
and another putStrLn
. With the getLine
, we use <
notation, which is a way to get the return value out of an action, so that we can use it elsewhere (in this case, to prepare the final message being printed). The final action defines the type of the whole do
block and, in this case, of the program. Here, the final action is the result of a putStrLn
, and so it has type IO ()
.
Exercises 

Write a program which asks the user for the base and height of a right angled triangle, calculates its area and prints it to the screen. The interaction should look something like: The base? 3.3 The height? 5.4 The area of that triangle is 8.91Hint: you can use the function read to convert user strings like "3.3" into numbers like 3.3 and function show to convert a number into string. 
Left arrow clarifications
While actions like getLine
are almost always used to get values, we are not obliged to actually get them. For example, we could very well have written something like this:
Example: executing getLine
directly
main = do putStrLn "Please enter your name: " getLine putStrLn ("Hello, how are you?")
Clearly, that isn't very useful: the whole point of prompting the user for his or her name was so that we could do something with the result. That being said, it is conceivable that one might wish to read a line and completely ignore the result. In real life, we often get someone's name when meeting them and then promptly forget it even though we keep talking… By omitting the <
, the action will happen, but the data won't be stored anywhere.
It's nicer to actually remember someone's name, of course. So, in order to get the value out of the action, we write name < getLine
, which basically means "run getLine
, and put the results in the variable called name
."
<
can be used with any action except the last
There are very few restrictions on which actions can have values obtained from them. Consider the following example, where we put the results of each action into a variable (except the last... more on that later):
Example: putting all results into a variable
main = do x < putStrLn "Please enter your name: " name < getLine putStrLn ("Hello, " ++ name ++ ", how are you?")
The variable x
gets the value out of its action, but that isn't useful in this case because the action returns the unit value ()
. So while we could technically get the value out of any action, it isn't always worth it.
So, what about that last action? Why can't we get a value out of that? Let's see what happens when we try:
Example: getting the value out of the last action
main = do x < putStrLn "Please enter your name: " name < getLine y < putStrLn ("Hello, " ++ name ++ ", how are you?")
Whoops! Error!
HaskellWikibook.hs:5:2: The last statement in a 'do' construct must be an expression
This is a much more interesting example, but it requires a somewhat deeper understanding of Haskell than we currently have. Suffice it to say, whenever you use <
to get the value of an action, Haskell is always expecting another action to follow it. So the very last action better not have any <
s.
Controlling actions
Normal Haskell constructions like if/then/else can be used within the do notation, but you need to be somewhat careful. For instance, in a simple "guess the number" program, we have:
doGuessing num = do putStrLn "Enter your guess:" guess < getLine if (read guess) < num then do putStrLn "Too low!" doGuessing num else if (read guess) > num then do putStrLn "Too high!" doGuessing num else putStrLn "You Win!"
If we think about how the if/then/else construction works, it essentially takes three arguments: the condition, the "then" branch, and the "else" branch. The condition needs to have type Bool
, and the two branches can have any type, provided that they have the same type. The type of the entire if/then/else construction is then the type of the two branches.
In the outermost comparison, we have (read guess) < num
as the condition. This clearly has the correct type. Let's just consider the "then" branch. The code here is:
do putStrLn "Too low!" doGuessing num
Here, we are sequencing two actions: putStrLn
and doGuessing
. The first has type IO ()
, which is fine. The second also has type IO ()
, which is fine. The type result of the entire computation is precisely the type of the final computation. Thus, the type of the "then" branch is also IO ()
. A similar argument shows that the type of the "else" branch is also IO ()
. This means the type of the entire if/then/else construction is IO ()
, which is just what we want.
Note: be careful if you find yourself thinking, "Well, I already started a do block; I don't need another one." We can't have code like:
do if (read guess) < num then putStrLn "Too low!" doGuessing num else ...
Here, since we didn't repeat the do, the compiler doesn't know that the putStrLn
and doGuessing
calls are supposed to be sequenced, and the compiler will think you're trying to call putStrLn
with three arguments: the string, the function doGuessing
and the integer num
, and thus reject the program.
Exercises 

Write a program that asks the user for his or her name. If the name is one of Simon, John or Phil, tell the user that you think Haskell is a great programming language. If the name is Koen, tell them that you think debugging Haskell is fun (Koen Classen is one of the people who works on Haskell debugging); otherwise, tell the user that you don't know who he or she is. (As far as syntax goes there are a few different ways to do it; write at least a version usingif / then / else .) 
Actions under the microscope
Actions may look easy up to now, but they are actually a common stumbling block for new Haskellers. If you have run into trouble working with actions, you might consider looking to see if one of your problems or questions matches the cases below. It might be worth skimming this section now, and coming back to it when you actually experience trouble.
Mind your action types
One temptation might be to simplify our program for getting a name and printing it back out. Here is one unsuccessful attempt:
Example: Why doesn't this work?
main = do putStrLn "What is your name? " putStrLn ("Hello " ++ getLine)
Ouch! Error!
HaskellWikiBook.hs:3:26: Couldn't match expected type `[Char]' against inferred type `IO String'
Let us boil the example above down to its simplest form. Would you expect this program to compile?
Example: This still does not work
main = do putStrLn getLine
For the most part, this is the same (attempted) program, except that we've stripped off the superfluous "What is your name" prompt as well as the polite "Hello". One trick to understanding this is to reason about it in terms of types. Let us compare:
putStrLn :: String > IO () getLine :: IO String
We can use the same mental machinery we learned in Type basics to figure how this went wrong. Simply put, putStrLn is expecting a String
as input. We do not have a String
, but something tantalisingly close, an IO String
. This represents an action that will give us a String
when it's run. To obtain the String
that putStrLn
wants, we need to run the action, and we do that with the everhandy left arrow, <
.
Example: This time it works
main = do name < getLine putStrLn name
Working our way back up to the fancy example:
main = do putStrLn "What is your name? " name < getLine putStrLn ("Hello " ++ name)
Now the name is the String we are looking for and everything is rolling again.
Mind your expression types too
So, we've made a big deal out of the idea that you can't use actions in situations that don't call for them. The converse of this is that you can't use nonactions in situations that expect actions. Say we want to greet the user, but this time we're so excited to meet them, we just have to SHOUT their name out:
Example: Exciting but incorrect. Why?
import Data.Char (toUpper) main = do name < getLine loudName < makeLoud name putStrLn ("Hello " ++ loudName ++ "!") putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)  Don't worry too much about this function; it just capitalises a String makeLoud :: String > String makeLoud s = map toUpper s
This goes wrong...
Couldn't match expected type `IO' against inferred type `[]' Expected type: IO t Inferred type: String In a 'do' expression: loudName < makeLoud name
This is similar to the problem we ran into above: we've got a mismatch between something that is expecting an IO type, and something which does not produce one. This time, the cause is our use of the left arrow <
; we're trying to left arrow a value of makeLoud name
, which really isn't left arrow material. It's basically the same mismatch we saw in the previous section, except now we're trying to use regular old String (the loud name) as an IO String, when those clearly are not the same thing. The latter is an action, something to be run, whereas the former is just an expression minding its own business. We cannot simply use loudName = makeLoud name
because a do
sequences actions, and loudName = makeLoud name
is not an action.
So how do we extricate ourselves from this mess? We have a number of options:
 We could find a way to turn
makeLoud
into an action, to make it returnIO String
. However, we don't want to make actions go out into the world for no reason. Within our program, we can reliably verify how everything is working. When actions engage the outside world, our results are much less predictable. An IOmakeLoud
could be made somehow, but that would be misguided. Consider another issue though: what if we wanted to use makeLoud from some other, nonIO, function? We really don't want to engage IO actions except when absolutely necessary.  We could use a special code called
return
to promote the loud name into an action, writing something likeloudName < return (makeLoud name)
. This is slightly better, in that we are at least leaving themakeLoud
function itself nice and IOfree, whilst using it in an IOcompatible fashion. That's still moderately clunky because, by virtue of left arrow, we're implying that there's action to be had  how exciting!  only to let our reader down with a somewhat anticlimacticreturn
(note: we will learn more about appropriate uses forreturn
in later chapters).  Or we could use a let binding...
It turns out that Haskell has a special extraconvenient syntax for let bindings in actions. It looks a little like this:
Example: let
bindings in do
blocks.
main = do name < getLine let loudName = makeLoud name putStrLn ("Hello " ++ loudName ++ "!") putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)
If you're paying attention, you might notice that the let binding above is missing an in
. This is because let
bindings inside do
blocks do not require the in
keyword. You could very well use it, but then you'd have messy extra do blocks. For what it's worth, the following two blocks of code are equivalent.
sweet  unsweet 

do name < getLine let loudName = makeLoud name putStrLn ("Hello " ++ loudName ++ "!") putStrLn ( "Oh boy! Am I excited to meet you, " ++ loudName) 
do name < getLine let loudName = makeLoud name in do putStrLn ("Hello " ++ loudName ++ "!") putStrLn ( "Oh boy! Am I excited to meet you, " ++ loudName) 
Exercises 


Learn more
At this point, you should have the fundamentals needed to do some fancier input/output. Here are some IOrelated topics you may want to check in parallel with the main track of the course.
 You could continue the sequential track, by learning more about types and eventually monads.
 Alternately: you could start learning about building graphical user interfaces in the GUI chapter
 For more IOrelated functionality, you could also consider learning more about the System.IO library
Elementary Haskell
Recursion
Recursion plays a central role in Haskell (and computer science and mathematics in general). Recursion is merely a form of repetition, but sometimes it is taught in a confusing or obscure way. It is easy enough to understand as long as you separate the meaning of a recursive function from its behaviour.
Generally speaking, a recursive function has two parts to its definition. A function is recursive when one part of its definition includes the function itself again. There must also be at least one base case that does not call the function being defined stopping (i.e. termination) condition; otherwise, recursive functions could lead to infinite regress (i.e. an infinite loop).
Numeric recursion
The factorial function
In mathematics, especially combinatorics, there is a function called factorial.^{[1]} It takes a single nonnegative integer as an argument, finds all the positive integers less than or equal to "n", and multiplies them all together. For example, the factorial of 6 (denoted as ) is . We can use a recursive style to define this in Haskell:
Let's look at the factorials of two adjacent numbers:
Example: Factorials of consecutive numbers
Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1 Factorial of 5 = 5 × 4 × 3 × 2 × 1
Notice how we've lined things up. You can see here that the includes the . In fact, is just . Let's look at another example:
Example: Factorials of consecutive numbers
Factorial of 4 = 4 × 3 × 2 × 1 Factorial of 3 = 3 × 2 × 1 Factorial of 2 = 2 × 1 Factorial of 1 = 1
The factorial of any number is just that number multiplied by the factorial of the number one less than it. There's one exception: if we ask for the factorial of 0, we don't want to multiply 0 by the factorial of 1 (factorial is only for positive numbers). In fact, we just say the factorial of 0 is 1 (we define it to be so. Just take our word for it that this is right.^{[2]}). So, 0 is the base case for the recursion: when we get to 0 we can immediately say that the answer is 1, no recursion needed. We can summarize the definition of the factorial function as follows:
 The factorial of 0 is 1.
 The factorial of any other number is that number multiplied by the factorial of the number one less than it.
We can translate this directly into Haskell:
Example: Factorial function
factorial 0 = 1 factorial n = n * factorial (n  1)
This defines a new function called factorial
. The first line says that the factorial of 0 is 1, and the second line says that the factorial of any other number n
is equal to n
times the factorial of n  1
. Note the parentheses around the n  1
; without them this would have been parsed as (factorial n)  1
; remember that function application (applying a function to a value) takes precedence over anything else when grouping isn't specified otherwise (we say that function application binds more tightly than anything else).
Note
The factorial
function above is best defined in a file, but since it is a small function, it is feasible to write it in GHCi as a oneliner. To do this, we need to add braces (that is, { and } ) and a semicolon:
> let { factorial 0 = 1; factorial n = n * factorial (n  1) }
Haskell actually uses line separation and other whitespace as a substitute for these separation and grouping characters. Haskell programmers generally prefer the clean look of separate lines and appropriate indentations, but explicit use of semicolons and other markers is fine whenever preferred. Note that if we left out the braces in this let
statement, the function would use only the last definition, losing the terminating base case and thus leading to infinite recursion.
The example above demonstrate a very simple relationship between factorial of a number, n, and the factorial of a slightly smaller number, n  1.
Think of a function call as delegation. The instructions for a recursive function delegate a subtask. It just so happens that the delegate function uses the same instructions as the delegator; it's only the input data that changes. The only really confusing thing about recursive functions is the fact that each function call uses the same parameter names, so it can be tricky to keep track of the many delegations.
Let's look at what happens when you execute factorial 3
:
 3 isn't 0, so we calculate the factorial of 2
 2 isn't 0, so we calculate the factorial of 1
 1 isn't 0, so we calculate the factorial of 0
 0 is 0, so we return 1.
 To complete the calculation for factorial 1, we multiply the current number, 1, by the factorial of 0, which is 1, obtaining 1 (1 × 1).
 1 isn't 0, so we calculate the factorial of 0
 To complete the calculation for factorial 2, we multiply the current number, 2, by the factorial of 1, which is 1, obtaining 2 (2 × 1 × 1).
 2 isn't 0, so we calculate the factorial of 1
 To complete the calculation for factorial 3, we multiply the current number, 3, by the factorial of 2, which is 2, obtaining 6 (3 × 2 × 1 × 1).
(Note that we end up with the one appearing twice, since the base case is 0 rather than 1; but that's okay since multiplying by 1 has no effect. We could have designed factorial
to stop at 1 if we had wanted to, but it's conventional, and often useful, to have the factorial of 0 defined.)
We can see how the result of the recursive call is calculated first, then combined using multiplication. Of course, you'll rarely need to "unwind" the recursion like this when reading or composing recursive functions. Compilers have to implement the behaviour, but programmers can work at the abstract level.
One more thing to note about the recursive definition of factorial
: the order of the two declarations (one for factorial 0
and one for factorial n
) is important. Haskell decides which function definition to use by starting at the top and picking the first one that matches. If we had the general case (factorial n
) before the 'base case' (factorial 0
), then the general n
would match anything passed into it – including 0. The compiler would then conclude that factorial 0
equals 0 * factorial (1)
, and so on to negative infinity (which is definitely not what we want). So, always list multiple function definitions starting with the most specific and proceeding to the most general.
Exercises 


Loops, recursion and accumulating parameters
Loops are the bread and butter of imperative languages. They are a way to directly specify a sequence of steps to be executed repeatedly by the program. When using an imperative language, loops are often a more natural way of solving problems that would, in Haskell, be dealt with recursion. For example, an idiomatic way of writing a factorial function in C, a typical imperative language, would be using a for loop, like this:
Example: The factorial function in an imperative language
int factorial(int n) { int res = 1; for ( ; n > 1; n) res *= n; return res; }
Here, the for loop causes res
to be multiplied by n
repeatedly. After each repetition, 1
is subtracted from n
(that is what n
does). The repetitions stop when n
is no longer greater than 1
.
A straightforward translation of such a function to Haskell is not possible, since changing the value of the variables res
and n
(a destructive update) would not be allowed. However, you can always translate a loop into an equivalent recursive form. The idea is to make each loop variable in need of updating into an argument of a recursive function. For example, here is a recursive "translation" of the above loop into Haskell:
Example: Using recursion to simulate a loop
factorial n = go n 1 where go n res  n > 1 = go (n  1) (res * n)  otherwise = res
go
is an auxiliary function which actually performs the factorial calculation. It takes an extra argument, res
, which is used as an accumulating parameter to build up the final result.
Note
Depending on the languages you are familiar with, you might be concerned about performance problems caused by recursion. As far as Haskell is concerned, you should not be worried. Compilers for Haskell and other functional programming languages include a number of optimisations for recursion, which is not surprising given how often it is needed. Another thing to keep in mind is that Haskell is lazy. That means calculations are only performed once their results are required by other calculations, which helps avoiding some of the performance issues usually associated with recursion. We'll further discuss such issues, and some of the subtleties they involve, in later chapters.
Other recursive functions
As it turns out, there is nothing particularly special about the factorial
function; a great many numeric functions can be defined recursively in a natural way. For example, let's think about multiplication. When you were first introduced to multiplication (remember that moment? :)), it may have been through a process of 'repeated addition'. That is, 5 × 4 is the same as summing four copies of the number 5. Of course, summing four copies of 5 is the same as summing three copies, and then adding one more – that is, 5 × 4 = 5 × 3 + 5. This leads us to a natural recursive definition of multiplication:
Example: Multiplication defined recursively
mult _ 0 = 0  anything times 0 is zero mult n 1 = n  anything times 1 is itself mult n m = (mult n (m  1)) + n  recurse: multiply by one less, and add an extra copy
Stepping back a bit, we can see how numeric recursion fits into the general recursive pattern. The base case for numeric recursion usually consists of one or more specific numbers (often 0 or 1) for which the answer can be immediately given. The recursive case computes the result by calling the function recursively with a smaller argument and using the result in some manner to produce the final answer. The 'smaller argument' used is often one less than the current argument, leading to recursion which 'walks down the number line' (like the examples of factorial
and mult
above). However, the prototypical pattern is not the only possibility; the smaller argument could be produced in some other way as well.
Exercises 


Listbased recursion
A lot of functions in Haskell turn out to be recursive, especially those concerning lists.^{[4]} Let's begin by considering the length
function, that finds the length of a list:
Example: The recursive definition of length
length :: [a] > Int length [] = 0 length (x:xs) = 1 + length xs
Let's explain the algorithm in English to clarify how it works. The type signature of length
tells us that it takes any type of list and produces an Int
. The next line says that the length of an empty list is 0; and that, naturally, is the base case. The final line is the recursive case: if a list isn't empty, then it can be broken down into a first element (here called x
) and the rest of the list (which will just be the empty list if there are no more elements) which will be called xs
(i.e. plural of x
). The length of the list is 1 (accounting for the x
) plus the length of xs
(as in the tail
example in Next steps, xs
is set when the argument list matches the (:) pattern).
How about the concatenation function (++)
, which joins two lists together?
Example: The recursive (++)
Prelude> [1,2,3] ++ [4,5,6] [1,2,3,4,5,6] Prelude> "Hello " ++ "world"  Strings are lists of Chars "Hello world"
(++) :: [a] > [a] > [a] [] ++ ys = ys (x:xs) ++ ys = x : xs ++ ys
This is a little more complicated than length
but not too difficult once we break it down. The type says that (++)
takes two lists of the same type and produces another list of the same type. The base case says that concatenating the empty list with a list ys
is the same as ys
itself. Finally, the recursive case breaks the first list into its head (x
) and tail (xs
) and says that to concatenate the two lists, concatenate the tail of the first list with the second list, and then tack the head x
on the front.
There's a pattern here: with listbased functions, the base case usually involves an empty list, and the recursive case involves passing the tail of the list to our function again, so that the list becomes progressively smaller.
Exercises 

Give recursive definitions for the following listbased functions. In each case, think what the base case would be, then think what the general case would look like, in terms of everything smaller than it. (Note that all of these functions are available in Prelude, so you will want to give them different names when testing your definitions in GHCi.)

Recursion is used to define nearly all functions to do with lists and numbers. The next time you need a listbased algorithm, start with a case for the empty list and a case for the nonempty list and see if your algorithm is recursive.
Don't get TOO excited about recursion...
Although it's very important to have a solid understanding of recursion when programming in Haskell, one rarely has to write functions that are explicitly recursive. Instead, there are all sorts of standard library functions which perform recursion for you in various ways, and one usually ends up using those instead. For example, a much simpler way to implement the factorial
function is as follows:
Example: Implementing factorial with a standard library function
factorial n = product [1..n]
Almost seems like cheating, doesn't it? :) This is the version of factorial
that most experienced Haskell programmers would write, rather than the explicitly recursive version we started out with. Of course, the product
function is using some list recursion behind the scenes,^{[6]} but writing factorial
in this way means you, the programmer, don't have to worry about it.
Notes
 ↑ In mathematics, n! normally means the factorial of a nonnegative integer n, but that syntax is impossible in Haskell, so we don't use it here.
 ↑ Actually, defining the factorial of 0 to be 1 is not just arbitrary; it's because the factorial of 0 represents an empty product.
 ↑ Interestingly, older scientific calculators can't handle things like factorial of 1000 because they run out of memory with that many digits!
 ↑ This is no coincidence; without mutable variables, recursion is the only way to implement control structures. This might sound like a limitation until you get used to it.
 ↑ Incidentally,
(!!)
provides a reasonable solution for the problem of the fourth exercise in Lists and tuples/Retrieving values.  ↑ Actually, it's using a function called
foldl
, which actually does the recursion.
More about lists
We have already met the basic tools for working with lists. We can build lists up from the cons operator (:)
and the empty list []
, and we can take them apart by using a combination of recursion and pattern matching. In this chapter and the next, we will consider more indepth techniques for list processing and discover a bit of new notation. Here, we will get our first taste of characteristic Haskell features like infinite lists, list comprehensions, and higherorder functions.
Note
Throughout this chapter, you will read and write functions which sum, subtract, and multiply elements of lists. For simplicity's sake, we will pretend the list elements have to be of type Integer
. However, as you will recall from the discussions on Type basics II, there are many different types with the Num typeclass. As an exercise of sorts, you could figure out what the type signatures of such functions would be if we made them polymorphic, allowing for the list elements to have any type in the class Num
. To check your signatures, just omit them temporarily, load the functions into GHCi, use :t and let type inference guide you.
Rebuilding lists
We'll start by writing and analysing a function that doubles every element from a list of integers:
doubleList :: [Integer] > [Integer] doubleList [] = [] doubleList (n:ns) = (2 * n) : doubleList ns
Here, the base case is the empty list; and it evaluates to an empty list. Otherwise, doubleList builds up a new list by using (:). The first element of this new list is twice the head of the argument, and the rest of the result is obtained by recursively calling doubleList on the tail of the argument. If the tail happens to be an empty list, the base case will be invoked and recursion stops.^{[1]}
By understanding the recursive definition, we can picture what actually happens when we evaluate an expression such as
doubleList [1,2,3,4]
We can work it out longhand by substituting the argument into the function definition, just like schoolbook algebra:
doubleList 1:[2,3,4] = (1*2) : doubleList (2 : [3,4]) = (1*2) : (2*2) : doubleList (3 : [4]) = (1*2) : (2*2) : (3*2) : doubleList (4 : []) = (1*2) : (2*2) : (3*2) : (4*2) : doubleList [] = (1*2) : (2*2) : (3*2) : (4*2) : [] = 2 : 4 : 6 : 8 : [] = [2, 4, 6, 8]
Thus, we rebuilt the original list replacing every element by its double.
In this longhand evaluation exercise, the moment at which we choose to evaluate the multiplications does not affect the result. We could just as well have done them immediately after each recursive call of doubleList.^{[2]}
This flexibility on evaluation order is reflected in some important properties of Haskell. As a pure functional programming language, it is mostly left to the compiler to decide when to actually evaluate things. As a lazy evaluation language, evaluation is usually deferred until the value is really needed, which may even be never in some cases.^{[3]} From the programmer's point of view, evaluation order rarely matters.^{[4]}
Generalizing
Suppose that we are solving a problem for which we need not only a function to double a list but also one that tripled it. In principle, we could follow the same strategy and define:
tripleList :: [Integer] > [Integer] tripleList [] = [] tripleList (n:ns) = (3 * n) : tripleList ns
Both doubleList
and tripleList
have very limited applicability. Every time we needed multiplying the elements of a list by 4, 8, 17 etc. we would need to write a new listmultiplying function, and all of them would do nearly the same thing. An obvious improvement would be generalizing our function to allow multiplication by any number. Doing so requires a function that takes an Integer
multiplicand as well as a list of Integer
s. Here is a way to define it:
multiplyList :: Integer > [Integer] > [Integer] multiplyList _ [] = [] multiplyList m (n:ns) = (m * n) : multiplyList m ns
This example deploys _
as a "don't care" pattern. The multiplicand is not used for the base case, so instead of giving it a name (like m
, n
or ns
) it is explicitly ignored.
multiplyList
solves our current problem for any integer number:
Prelude> multiplyList 17 [1,2,3,4] [17,34,51,68]
Exercises 

Write the following functions and test them out. Don't forget the type signatures.
take , drop , and sum . 
Generalizing even further
We just wrote a function which can multiply the elements of a list by any Integer
. But even though multiplyList
is much more flexible than doubleList
, it's still limited. Initially, we had a function constrained to multiplying the elements by 2
, and we had to hardcode a new function to use a different number. With multiplyList
, we could still complain about being constrained to apply multiplication to the list elements. What if we wanted to instead add to each element or to compute the square of each element? We would be back rewriting the recursive function for each case.
A key functionality of Haskell will save the day. Since the solution can be quite surprising, we will approach it in a somewhat roundabout way. Consider the type signature of multiplyList
:
multiplyList :: Integer > [Integer] > [Integer]
The first thing to know is that the >
arrow in type signatures is right associative. That means we can read this signature as:
multiplyList :: Integer > ([Integer] > [Integer])
How should we understand that? It tells us that multiplyList
is a function that takes one Integer
argument and evaluates to another function, which in turn takes a list of Integer
s and returns another list of Integer
s.
Consider our earlier doubleList function redefined in terms of multiplyList
:
doubleList :: [Integer] > [Integer] doubleList xs = multiplyList 2 xs
A practical consequence of what we have just said is that we can, metaphorically speaking, cancel out the `xs`:
doubleList = multiplyList 2
This definition style (with no argument variables) is called "pointfree" style. The expressions here are perfectly wellformed and stands on their own, so writing the second argument of multiplyList
(which is the same as the only argument of doubleList
) is strictly unnecessary. Applying only one argument to multiplyList
doesn't fail to evaluate, it just gives us just a more specific function of type [Integer] > [Integer]
instead of finishing with a final [Integer]
value.
The trickery above illustrates that functions in Haskell behave much like any other value. Functions that return other functions, and functions can stand alone as objects without mentioning their arguments. It's as though functions were just a normal constants. Could we use functions themselves as arguments even? Well, that's the key to our dilemma with multiplyList
. We need a function that takes not only multiplication but any other appropriate function and applies the given function to the elements of a list:
applyToIntegers :: (Integer > Integer) > [Integer] > [Integer] applyToIntegers _ [] = [] applyToIntegers f (n:ns) = (f n) : applyToIntegers f ns
With applyToIntegers
, we can take any Integer > Integer
function and apply it to the elements of a list of Integer
s. We can, of course, use this generalized function to redefine multiplyList
. Specifically, we just use the (*)
function as the first argument for applyToIntegers:
multiplyList :: Integer > [Integer] > [Integer] multiplyList x = applyToIntegers ((*) x)
If all this abstraction is confusing you, consider a concrete example: When we multiply 5 * 7 in Haskell, the (*)
function doesn't just take two arguments at once, it actually first takes the 5 and returns a new 5* function; and that new function then takes one argument and multiplies whatever that is by 5. So, we then give the 7 to the 5* function, and that returns us our final evaluated number (35 in this example).
So, all functions in Haskell really take only one argument. However, as we know how many intermediate functions will have to be generated before our final result is returned, we can treat our functions as if they took many arguments. The number of arguments we generally talk about functions taking is actually the number of functions of one argument between the first argument and the final, nonfunctional result value.
The process of creating intermediate functions when feeding arguments into a complex function is called currying (named after Haskell Curry, who is also the namesake of the Haskell programming language).
The map
function
While applyToIntegers
has type (Integer > Integer) > [Integer] > [Integer]
, there is nothing specific to integers in its algorithm. Therefore, we could define versions such as applyToChars
, applyToStrings
and applyToLists
just by changing the type signature. That would be horribly wasteful, though: we did not climb all the way up to this point just to need a different function for each type! Furthermore, nothing prevents us from changing the signature to, for instance, (Integer > String) > [Integer] > [String]
; thus giving a function that takes a function Integer > String
and returns a function [Integer] > [String]
which applies the function originally passed as argument to each element of an Integer
list.
The final step of generalization, then, is to make a fully polymorphic version of applyToIntegers
, with signature (a > b) > [a] > [b]
. Such a function already exists in Prelude: it is called map and defined as:
map :: (a > b) > [a] > [b] map _ [] = [] map f (x:xs) = (f x) : map f xs
Using it, we can effortlessly implement functions as different as...
multiplyList :: Integer > [Integer] > [Integer] multiplyList x = map ((*) x)
... and...
heads :: [[a]] > [a] heads = map head
Prelude> heads [[1,2,3,4],[4,3,2,1],[5,10,15]] [1,4,5]
map
is the ideal general solution for applying a function to each element of a list. Our original doubleList
problem was just a very specific version of map
. Functions like map
which take other functions as arguments are called higherorder functions, and they are extremely useful. In particular, we will meet some other important higherorder functions used for list processing in the next chapter.
Exercises 


Tips and Tricks
Before we carry on with more list processing, let us make a few miscellaneous useful observations about lists in Haskell.
Dot Dot Notation
Haskell has a convenient shorthand for writing ordered lists of regularlyspaced integers. Some examples to illustrate it:
Code Result   [1..10] [1,2,3,4,5,6,7,8,9,10] [2,4..10] [2,4,6,8,10] [5,4..1] [5,4,3,2,1] [1,3..10] [1,3,5,7,9]
The same notation can be used with characters as well, and even with floating point numbers  though the latter is not necessarily a good idea due to rounding errors. Try this:
[0,0.1 .. 1]
Note
The ..
notation only works with sequences with fixed differences between consecutive elements. For instance, you cannot write...
[0,1,1,2,3,5,8..100]
... and expect to magically get back the rest of the Fibonacci series.^{[5]}
Infinite Lists
One of the most mindbending things about Haskell lists is that they are allowed to be infinite. For example, the following generates the infinite list of integers starting with 1:
[1..]
(If you try this in GHCi, remember you can stop an evaluation with Ctrlc).
The same effect could be achieved with a recursive function:
intsFrom n = n : intsFrom (n + 1)  note there is no base case! positiveInts = intsFrom 1
This works because Haskell uses lazy evaluation: it never actually evaluates more than it needs at any given moment. In most cases an infinite list can be treated just like an ordinary one. The program will only go into an infinite loop when evaluation would actually require all the values in the list. Examples of this include sorting or printing the entire list. However:
evens = doubleList [1..]
will define "evens" to be the infinite list [2,4,6,8..]. You can pass "evens" into other functions, and this will work as long as you only need to evaluate part of the list for your final result.
Infinite lists are quite useful in Haskell. Often it's more convenient to define an infinite list and then take the first few items than to create a finite list. Functions that process two lists in parallel generally stop with the shortest, so making the second one infinite avoids having to find the length of the first. An infinite list is often a handy alternative to the traditional endless loop at the top level of an interactive program.
A note about head
and tail
Given the choice of using either the ( : )
pattern or head
/tail
to split lists, pattern matching is almost always preferable. While it may be tempting to use head
and tail
due to simplicity and terseness, it is all too easy to forget that they fail on empty lists  and runtime crashes are never a good thing. While the Prelude function null :: [a] > Bool
provides a sane way of checking for empty lists without pattern matching (it returns True
for empty lists and False
otherwise), matching an empty list tends to be cleaner and clearer than the corresponding ifthenelse expression.
Exercises 


Notes
 ↑ Had we forgotten the base case, once the recursion got to an empty list the (x:xs) pattern match would fail, and we would get an error.
 ↑ As long as none of the calculations result in an error or nontermination, which are not problems in this case.
 ↑ The compiler is still free to evaluate things sooner if it will improve efficiency.
 ↑ One exception is the case of infinite lists (!) which we will consider in a short while.
 ↑ http://en.wikipedia.org/wiki/Fibonacci_number
List processing
Folds
A fold is a higher order function that, like map, takes a function and a list. However, instead of applying the function element by element, the fold uses it to combine the list elements into a result value.
Let's start looking at a few concrete examples. A function like sum might be implemented as follows:
Example: sum
sum :: [Integer] > Integer sum [] = 0 sum (x:xs) = x + sum xs
or product:
Example: product
product :: [Integer] > Integer product [] = 1 product (x:xs) = x * product xs
or concat, which takes a list of lists and joins (concatenates) them into one:
Example: concat
concat :: [[a]] > [a] concat [] = [] concat (x:xs) = x ++ concat xs
There is a certain pattern of recursion common to all of these examples. This pattern is known as a fold, possibly from the idea that a list is being "folded up" into a single value, or that a function is being "folded between" the elements of the list.
The Standard Prelude defines four fold
functions: foldr
, foldl
, foldr1
and foldl1
.
foldr
The rightassociative foldr
folds up a list from the right to left. As it proceeds, foldr uses the given function to combine each of the element with the running value called the accumulator. When calling foldr, the initial value of the accumulator is set as an argument.
foldr :: (a > b > b) > b > [a] > b foldr f acc [] = acc foldr f acc (x:xs) = f x (foldr f acc xs)
The first argument is a function with two arguments, the second is a "zero" value for the accumulator, and the third is the list to be folded.
In sum
, f
is (+)
, and acc
is 0
, and in concat
, f
is (++)
and acc
is []
. In many cases, like all of our examples so far, the function passed to a fold will have both its arguments be of the same type, but this is not necessarily the case in general.
What foldr f acc xs does is to replace each cons (:) in the xs
list with the function f
, and the empty list at the end with acc
.
a : b : c : []
becomes
f a (f b (f c acc))
Note how the parentheses nest around the right end of the list.
An elegant visualisation is given by picturing the list data structure as a tree:
: f / \ / \ a : foldr f acc a f / \ > / \ b : b f / \ / \ c [] c acc
We can see here that foldr (:) [] would return the list completely unchanged. That sort of function that has no effect is called an identity function. You should start building a habit of looking for identity functions in different cases, and we'll discuss them more later when we learn about monoids.
foldl
The leftassociative foldl processes the list in the opposite direction, starting at the left side with the first element.
foldl :: (a > b > a) > a > [b] > a foldl f acc [] = acc foldl f acc (x:xs) = foldl f (f acc x) xs
So brackets in the resulting expression accumulate around the left end of the list. Our list above, after being transformed by foldl f acc becomes:
f (f (f acc a) b) c
The corresponding trees look like:
: f / \ / \ a : foldl f acc f c / \ > / \ b : f b / \ / \ c [] acc a
Because all folds include both left and right elements, beginners can get confused by the names. You could think of foldr as short for foldrighttoleft and foldl as foldlefttoright. The names refer to where the fold starts.
Note
Technical Note: foldl is tailrecursive, that is, it recurses immediately, calling itself. For this reason the compiler will optimise it to a simple loop, which is a good thing performancewise. However, Haskell is a lazy language, and so the calls to f will be left unevaluated by default, thus building up an unevaluated expression in memory that includes the entire length of the list. To avoid running out of memory, there is a version of foldl called foldl' that is strict in that it forces the evaluation of f immediately at each step.
An apostrophe at the end of a function name is pronounced "tick" as in "foldLtick". A tick is a valid character in Haskell identifiers. foldl' can be found in the Data.List
library module (which can be imported by adding import Data.List to the beginning of a source file). As a rule of thumb, you should use foldr on lists that might be infinite or where the fold is building up a data structure and use foldl' if the list is known to be finite and comes down to a single value. There is almost never a good reason to use foldl
(without the tick), though it might just work if the lists fed to it are not too long.
foldr1 and foldl1
As previously noted, the type declaration for foldr makes it quite possible for the list elements and result to be of different types. For example, "read" is a function that takes a string and converts it into some type (the type system is smart enough to figure out which one). In this case we convert it into a float.
Example: The list elements and results can have different types
addStr :: String > Float > Float addStr str x = read str + x sumStr :: [String] > Float sumStr = foldr addStr 0.0
If you substitute the types Float and String for the type variables a
and b
in the type of foldr you will see that this is type correct.
There is also a variant called foldr1 ("fold  R  one") which dispenses with an explicit zero by taking the last element of the list instead:
foldr1 :: (a > a > a) > [a] > a foldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 f xs) foldr1 _ [] = error "Prelude.foldr1: empty list"
And foldl1 as well:
foldl1 :: (a > a > a) > [a] > a foldl1 f (x:xs) = foldl f x xs foldl1 _ [] = error "Prelude.foldl1: empty list"
Note: Just like for foldl, the Data.List library includes foldl1' as a strict version of foldl1.
With foldl1 and foldr1, all the types have to be the same and an empty list is an error. These variants are useful when there is no obvious candidate for the initial accumulator value and we are sure that the list is not going to be empty. When in doubt, stick with foldr or foldl'.
folds and laziness
One reason that rightassociative folds are more natural to use in Haskell than leftassociative ones is that right folds can operate on infinite lists. A fold that returns an infinite list is perfectly usable in a larger context that doesn't need to access the entire infinite result. In that case, foldr can move along as much as is needed and the compiler will not do any extra. However, a left fold necessarily calls itself recursively until it reaches the end of the input list (because the recursive call is not made in an argument to f). Needless to say, no end will be reached if an input list to foldl is infinite.
As a toy example, consider a function echoes
that takes a list of integers and produces a list such that wherever the number n occurs in the input list, it is replicated n times in the output list. To create our echoes function, we will use the prelude function replicate
in which replicate n x is a list of length n with x the value of every element.
We can write echoes as a foldr quite handily:
echoes = foldr (\ x xs > (replicate x x) ++ xs) []
Note: This definition is very compact thanks to the \ x xs >
syntax, which allows us to define an anonymous function called a "lambda function". Instead of defining a function somewhere else and passing it to foldr we provided the definition in situ. x
and xs
being the arguments and the righthand side of the definition being what is after the >
. For a more indepth discussion of lambda functions see Haskell/More on Functions.
or, equally handily, as a foldl:
echoes = foldl (\xs x > xs ++ (replicate x x)) []
but only the foldr version works on an infinite list like [1..]
. Try it! (If you try this in GHCi, remember you can stop an evaluation with Ctrlc, but you have to be quick and keep an eye on the system monitor or your memory will be consumed in no time and your system will hang.)
As a final example, another thing that you might notice is that map
itself can be implemented as a fold:
map f = foldr (\x xs > f x : xs) []
Folding takes a little time to get used to, but it is a fundamental pattern in functional programming and eventually becomes very natural. Any time you want to traverse a list and build up a result from its members, you likely want a fold.
Exercises 


Scans
A "scan" is much like a cross between a map
and a fold. Folding a list accumulates a single return value, whereas mapping puts each item through a function with no accumulation. A scan does both: it accumulates a value like a fold, but instead of returning a final value it returns a list of all the intermediate values.
The Standard Prelude contains four scan functions:
scanl :: (a > b > a) > a > [b] > [a]
This accumulates the list from the left, and the second argument becomes the first item in the resulting list. So scanl (+) 0 [1,2,3] = [0,1,3,6]
.
scanl1 :: (a > a > a) > [a] > [a]
This is the same as scanl
, but uses the first item of the list as a zero parameter. It is what you would typically use if the input and output items are the same type. Notice the difference in the type signatures. scanl1 (+) [1,2,3] = [1,3,6]
.
scanr :: (a > b > b) > b > [a] > [b] scanr1 :: (a > a > a) > [a] > [a]
These two functions are the exact counterparts of scanl
and scanl1
. They accumulate the totals from the right. So:
scanr (+) 0 [1,2,3] = [6,5,3,0] scanr1 (+) [1,2,3] = [6,5,3]
Exercises 


filter
A very common operation performed on lists is filtering, which means generating a new list composed only of elements of the first list that meet a certain condition. One simple example of that would be taking a list of integers and making from it a list which only retains its even numbers.
retainEven :: [Int] > [Int] retainEven [] = [] retainEven (n:ns) =  mod n 2 computes the remainder for the integer division of n by 2, so if it is zero the number is even if (mod n 2) == 0 then n : (retainEven ns) else retainEven ns
That works fine, but it is a slightly verbose solution. It would be nice to have a more concise and general way to write the filter function. This is already provided by Prelude as filter with the following type signature:
filter :: (a > Bool) > [a] > [a]
So, a (a > Bool) function tests an elements for the condition, there is a list to be filtered, and it returns the filtered list. In order to write retainEven using filter, we need to state the condition as an auxiliary (a > Bool) function, like this one:
isEven :: Int > Bool isEven n = (mod n 2) == 0
And then retainEven becomes simply:
retainEven ns = filter isEven ns
We used ns instead of xs just because it is sensible to indicate that we know these are numbers and not just anything, but we can ignore that and use a more terse pointfree definition:
retainEven = filter isEven
This is just like what we demonstrated before for map and the folds. Like filter, those take another function as argument; and using them pointfree emphasizes this "functionsoffunctions" aspect.
List comprehensions
A a powerful, concise, and expressive syntactic tool for list processing is the list comprehension. Among other things, list comprehensions can be syntactic sugar for filtering. Instead of using the Prelude filter, we could write retainEven like this:
retainEven es = [n  n < es, isEven n]
This compact syntax may look a bit intimidating at first, but it is simple to break down. One interpretation is:
 (Starting from the middle) Take the list es and draw (the "<") each of its elements as a value n.
 (After the comma) For each drawn n test the boolean condition
isEven n
.  (Before the vertical bar) If (and only if) the boolean condition is satisfied, append n to the new list being created (note the square brackets around the whole expression).
Thus, if es
is equal to [1,2,3,4], then we would get back the list [2,4]. 1 and 3 were not drawn because (isEven n) == False
.
The power of list comprehensions comes from being easily extensible. Firstly, we can use as many tests as we wish (even zero!). Multiple conditions are written as a commaseparated list of expressions (which should evaluate to a Boolean, of course). For a simple example, suppose we want to modify retainEven so that only numbers larger than 100 are retained:
retainLargeEvens :: [Int] > [Int] retainLargeEvens es = [n  n < es, isEven n, n > 100]
Furthermore, we are not limited to using n as the element to be appended when generating a new list. Instead, we could place any expression before the vertical bar (if it is compatible with the type of the list, of course). For instance, if we wanted to subtract one from every even number, all it would take is:
evensMinusOne es = [n  1  n < es, isEven n]
In effect, that means the list comprehension syntax incorporates the functionality of map as well as of filter. Now that is concise (and still readable too)!
To further sweeten things, the left arrow notation in list comprehensions can be combined with pattern matching. For example, suppose we had a list of (Int, Int)
tuples and we would like to construct a list with the first element of every tuple whose second element is even. Using list comprehensions, we might write it as follows:
firstForEvenSeconds :: [(Int, Int)] > [Int] firstForEvenSeconds ps = [fst p  p < ps, isEven (snd p)]  here, p is for pairs.
Patterns can make it much more readable:
firstForEvenSeconds ps = [x  (x, y) < ps, isEven y]
As in other cases, arbitrary expressions may be used before the . If we wanted a list with the double of those first elements:
doubleOfFirstForEvenSeconds :: [(Int, Int)] > [Int] doubleOfFirstForEvenSeconds ps = [2 * x  (x, y) < ps, isEven y]
Not counting spaces, that function code is shorter than its descriptive name!
There are even more possible tricks:
allPairs :: [(Int, Int)] allPairs = [(x, y)  x < [1..4], y < [5..8]]
This comprehension draws from two lists, and generates all possible (x, y)
pairs with the first element in [1..4]
and the second in [5..8]
. In the final list of pairs, the first elements will be those generated with the first element of the first list (here, 1
), then those with the second element of the first list, and so on. In this example, the full list is (linebreaks added for clarity):
Prelude> [(x, y)  x < [1..4], y < [5..8]] [(1,5),(1,6),(1,7),(1,8), (2,5),(2,6),(2,7),(2,8), (3,5),(3,6),(3,7),(3,8), (4,5),(4,6),(4,7),(4,8)]
Note that we didn't do any filtering here; but we could easily add a condition to restrict the combinations that go into the final list:
somePairs = [(x, y)  x < [1..4], y < [5..8], x + y > 8]
This list only has the pairs with the sum of elements larger than 8; starting with (1,8)
, then (2,7)
and so forth.
Exercises 


Type declarations
You're not restricted to working with just the types provided by default with the language. There are many benefits to defining your own types:
 Code can be written in terms of the problem being solved, making programs easier to design, write and understand.
 Related pieces of data can be brought together in ways more convenient and meaningful than simply putting and getting values from lists or tuples.
 Pattern matching and the type system can be used to their fullest extent by making them work with your custom types.
Haskell has three basic ways to declare a new type:
 The data declaration, which defines new data types.
 The type declaration for type synonyms.
 The newtype declaration, which is a cross between the other two.
In this chapter, we will discuss data
. We'll also mention type
, which is a convenience feature. We will explain newtype
later on, but don't worry too much about it; it exists mainly for optimisation.
data
and constructor functions
data is used to define new data types using existing ones as building blocks. Here's a data structure for elements in a simple list of anniversaries:
data Anniversary = Birthday String Int Int Int  name, year, month, day  Wedding String String Int Int Int  spouse name 1, spouse name 2, year, month, day
This declares a new data type Anniversary, which can be either a Birthday or a Wedding. A Birthday contains one string and three integers and a Wedding contains two strings and three integers. The definitions of the two possibilities are separated by the vertical bar. The comments explain to readers of the code about the intended use of these new types. Moreover, with the declaration we also get two constructor functions for Anniversary; appropriately enough, they are called Birthday and Wedding. These functions provide a way to build a new Anniversary.
Types defined by data declarations are often referred to as algebraic data types, which is something we will address further in later chapters.
As usual with Haskell, the case of the first letter is important: type names and constructor functions must start with capital letters. Other than this syntactic detail, constructor functions work pretty much like the "conventional" functions we met so far. In fact, if you use :t in GHCi to query the type of, say, Birthday, you'll get:
*Main> :t Birthday Birthday :: String > Int > Int > Int > Anniversary
Meaning it's just a function which takes one String and three Int as arguments and evaluates to an Anniversary. This anniversary will contain the four arguments we passed as specified by the Birthday constructor.
Calling constructors is no different from calling other functions. For example, suppose we have John Smith born on 3rd July 1968:
johnSmith :: Anniversary johnSmith = Birthday "John Smith" 1968 7 3
He married Jane Smith on 4th March 1987:
smithWedding :: Anniversary smithWedding = Wedding "John Smith" "Jane Smith" 1987 3 4
These two anniversaries can, for instance, be put in a list:
anniversariesOfJohnSmith :: [Anniversary] anniversariesOfJohnSmith = [johnSmith, smithWedding]
Or you could just as easily have called the constructors straight away when building the list (although the resulting code looks a bit cluttered).
anniversariesOfJohnSmith = [Birthday "John Smith" 1968 7 3, Wedding "John Smith" "Jane Smith" 1987 3 4]
Deconstructing types
To use our new data types, we must have a way to access their contents. For instance, one very basic operation with the anniversaries defined above would be extracting the names and dates they contain as a String. So we need a showAnniversary function (for the sake of code clarity, we used an auxiliary showDate function but let's ignore it for a moment):
showDate :: Int > Int > Int > String showDate y m d = show y ++ "" ++ show m ++ "" ++ show d showAnniversary :: Anniversary > String showAnniversary (Birthday name year month day) = name ++ " born " ++ showDate year month day showAnniversary (Wedding name1 name2 year month day) = name1 ++ " married " ++ name2 ++ " on " ++ showDate year month day
This example shows how we can deconstruct the values built in our data types. showAnniversary takes a single argument of type Anniversary. Instead of just providing a name for the argument on the left side of the definition, however, we specify one of the constructor functions and give names to each argument of the constructor (which correspond to the contents of the Anniversary). A more formal way of describing this "giving names" process is to say we are binding variables. "Binding" is being used in the sense of assigning a variable to each of the values so that we can refer to them on the right side of the function definition.
To handle both "Birthday" and "Wedding" Anniversaries, we needed to provide two function definitions, one for each constructor. When showAnniversary is called, if the argument is a Birthday Anniversary, the first definition is used and the variables name, month, date and year are bound to its contents. If the argument is a Wedding Anniversary, then the second definition is used and the variables are bound in the same way. This process of using a different version of the function depending on the type of constructor is pretty much like what happens when we use a case statement or define a function piecewise.
Note that the parentheses around the constructor name and the bound variables are mandatory; otherwise the compiler or interpreter would not take them as a single argument. Also, it is important to have it absolutely clear that the expression inside the parentheses is not a call to the constructor function, even though it may look just like one.
Exercises 

Note: The solution of this exercise is given near the end of the chapter, so we recommend that you attempt it before getting there.

type
for making type synonyms
As mentioned in the introduction of this module, code clarity is one of the motivations for using custom types. In that spirit, it could be nice to make it clear that the Strings in the Anniversary type are being used as names while still being able to manipulate them like ordinary Strings. This calls for a type declaration:
type Name = String
The code above says that a Name is now a synonym for a String. Any function that takes a String will now take a Name as well (and viceversa: functions that take Name will accept any String). The right hand side of a type declaration can be a more complex type as well. For example, String itself is defined in the standard libraries as
type String = [Char]
We can do something similar for the list of anniversaries we made use of:
type AnniversaryBook = [Anniversary]
Since type synonyms are mostly just a convenience. They help make the roles of types clearer or provide an alias to such things as complicated list or tuple types. It is largely a matter of personal discretion to decide how type synonyms should be deployed. Abuse of synonyms could make code confusing (for instance, picture a long program using multiple names for common types like Int or String simultaneously).
Incorporating the suggested type synonyms and the Date type we proposed in the exercise(*) of the previous section the code we've written so far looks like this:
((*) last chance to try that exercise without looking at the spoilers.)
type Name = String data Anniversary = Birthday Name Date  Wedding Name Name Date data Date = Date Int Int Int  Year, Month, Day johnSmith :: Anniversary johnSmith = Birthday "John Smith" (Date 1968 7 3) smithWedding :: Anniversary smithWedding = Wedding "John Smith" "Jane Smith" (Date 1987 3 4) type AnniversaryBook = [Anniversary] anniversariesOfJohnSmith :: AnniversaryBook anniversariesOfJohnSmith = [johnSmith, smithWedding] showDate :: Date > String showDate (Date y m d) = show y ++ "" ++ show m ++ "" ++ show d showAnniversary :: Anniversary > String showAnniversary (Birthday name date) = name ++ " born " ++ showDate date showAnniversary (Wedding name1 name2 date) = name1 ++ " married " ++ name2 ++ " on " ++ showDate date
Even in a simple example like this one, there is a noticeable gain in simplicity and clarity compared to the same task using only Ints, Strings, and corresponding lists.
Note that the Date type has a constructor function which is called Date as well. That is perfectly valid and indeed giving the constructor the same name of the type when there is just one constructor is good practice, as a simple way of making the role of the function obvious.
Note
After these initial examples, the mechanics of using constructor functions may look a bit unwieldy, particularly if you're familiar with analogous features in other languages. There are syntactical constructs that make dealing with constructors more convenient. These will be dealt with later on, when we return to the topic of constructors and data types to explore them in detail.
Pattern matching
In the previous modules, we introduced and made occasional reference to pattern matching. Now that we have developed some familiarity with the language, it is time to take a proper, deeper look. We will kickstart the discussion with a condensed description, which we will expand upon throughout the chapter:
In pattern matching, we attempt to match values against patterns and, if so desired, bind variables to successful matches.
Note
Pattern matching on what?
Some languages like Perl and Python use the term pattern matching for matching regular expressions against strings. The pattern matching we refer to in Haskell is something completely different. In fact, you're probably best off forgetting what you know about pattern matching for now.^{[1]} Haskell pattern matching is used in the same way as in other MLlike languages: to deconstruct values according to their type specification.
Analysing pattern matching
Pattern matching is virtually everywhere. For example, consider this definition of map
:
map _ [] = [] map f (x:xs) = f x : map f xs
At surface level, there are four different patterns involved, two per equation.
f
is a pattern which matches anything at all, and binds thef
variable to whatever is matched.(x:xs)
is a pattern that matches a nonempty list which is formed by something (which gets bound to thex
variable) which was cons'd (by the(:)
function) onto something else (which gets bound toxs
).[]
is a pattern that matches the empty list. It doesn't bind any variables._
is the pattern which matches anything at all, but doesn't do any binding.
In the (x:xs)
pattern, x
and xs
can be seen as subpatterns used to match the parts of the list. Just like f
, they match anything  though it is evident that if there is a successful match and x
has type a
, xs
will have type [a]
. Finally, these considerations imply that xs
will also match an empty list, and so a oneelement list matches (x:xs)
.
From the above dissection, we can say pattern matching gives us a way to:
 recognize values. For instance, when
map
is called and the second argument matches[]
the first equation formap
is used instead of the second one.  bind variables to the recognized values. In this case, the variables
f
,x
, andxs
are assigned to the values passed as arguments tomap
when the second equation is used, and so we can use these values through the variables in the righthand side of=
. As_
and[]
show, binding is not an essential part of pattern matching, but just a side effect of using variable names as patterns.  break down values into parts, as the
(x:xs)
pattern does by binding two variables to parts (head and tail) of a matched argument (the nonempty list).
The connection with constructors
Despite the detailed analysis above, it may seem a little too magical how we break down a list as if we were undoing the effects of the (:)
operator. Be careful: this process will not work with any arbitrary operator. For example, one might think of defining a function which uses (++)
to chop off the first three elements of a list:
dropThree ([x,y,z] ++ xs) = xs
But that will not work. The function (++)
is not allowed in patterns. In fact, most other functions that act on lists are similarly prohibited from pattern matching. Which functions, then, are allowed?
In one word, constructors – the functions used to build values of algebraic data types. Let us consider a random example:
data Foo = Bar  Baz Int
Here Bar
and Baz
are constructors for the type Foo
. You can use them for pattern matching Foo
values and bind variables to the Int
value contained in a Foo
constructed with Baz
:
f :: Foo > Int f Bar = 1 f (Baz x) = x  1
This is exactly like showAnniversary
and showDate
in the Type declarations module. For instance:
data Date = Date Int Int Int  Year, Month, Day showDate :: Date > String showDate (Date y m d) = show y ++ "" ++ show m ++ "" ++ show d
The (Date y m d)
pattern in the lefthand side of the showDate
definition matches a Date
(built with the Date
constructor) and binds the variables y
, m
and d
to the contents of the Date
value.
Why does it work with lists?
As for lists, they are no different from data
defined algebraic data types as far as pattern matching is concerned. It works as if lists were defined with this data
declaration (note that the following isn't actually valid syntax: lists are actually too deeply ingrained into Haskell to be defined like this):
data [a] = []  a : [a]
So the empty list, []
and the (:)
function are constructors of the list datatype, and so you can pattern match with them. []
takes no arguments, and therefore no variables can be bound when it is used for pattern matching. (:)
takes two arguments, the list head and tail, which may then have variables bound to them when the pattern is recognized.
Prelude> :t [] [] :: [a] Prelude> :t (:) (:) :: a > [a] > [a]
Furthermore, since [x, y, z]
is just syntactic sugar for x:y:z:[]
, we can achieve something like dropThree
using pattern matching alone:
dropThree :: [a] > [a] dropThree (_:_:_:xs) = xs dropThree _ = []
The first pattern will match any list with at least three elements. The catchall second definition provides a reasonable default^{[2]} when lists fail to match the main pattern, and thus prevents runtime crashes due to pattern match failure.
Note
From the fact that we could write a dropThree
function with bare pattern matching it doesn't follow that we should do so! Even though the solution is simple, it is still a waste of effort to code something this specific when we could just use Prelude and settle it with drop 3 xs
instead. Mirroring what was said before about baking bare recursive functions, we might say: don't get too excited about pattern matching either...
Tuple constructors
Analogous considerations are valid for tuples. Our access to their components via pattern matching...
fstPlusSnd :: (Num a) => (a, a) > a fstPlusSnd (x, y) = x + y norm3D :: (Floating a) => (a, a, a) > a norm3D (x, y, z) = sqrt (x^2 + y^2 + z^2)
... is granted by the existence of tuple constructors. For pairs, the constructor is the comma operator, (,)
; for larger tuples there are (,,)
; (,,,)
and so on. These operators are slightly unusual in that we can't use them infix in the regular way; so 5 , 3
is not a valid way to write (5, 3)
. All of them, however, can be used prefix, which is occasionally useful.
Prelude> (,) 5 3 (5,3) Prelude> (,,,) "George" "John" "Paul" "Ringo" ("George","John","Paul","Ringo")
Matching literal values
As discussed earlier in the book, a simple piecewise function definition like this one
f :: Int > Int f 0 = 1 f 1 = 5 f 2 = 2 f _ = 1
is performing pattern matching as well, matching the argument of f
with the Int
literals 0, 1 and 2, and finally with _
. In general, numeric and character literals can be used in pattern matching on their own^{[3]} as well as together with constructor patterns. For instance, this function
g :: [Int] > Bool g (0:[]) = False g (0:xs) = True g _ = False
will evaluate to False for the [0] list, to True if the list has 0 as first element and a nonempty tail and to False in all other cases. Also, lists with literal elements like [1,2,3], or even "abc" (which is equivalent to ['a','b','c']) can be used for pattern matching as well, since these forms are only syntactic sugar for the (:) constructor.
The above considerations are only valid for literal values, so the following will not work:
k = 1 again, this won't work as expected h :: Int > Bool h k = True h _ = False
Exercises 


Syntax tricks
Aspatterns
Sometimes, when matching a pattern with a value, it may be useful to bind a name to the whole value being matched. Aspatterns allow exactly this: they are of the form var@pattern
and have the additional effect to bind the name var
to the whole value being matched by pattern
. For instance, here is a toy variation on the map theme:
contrivedMap :: ([a] > a > b) > [a] > [b] contrivedMap f [] = [] contrivedMap f list@(x:xs) = f list x : contrivedMap f xs
contrivedMap
passes to the parameter function f
not only x
but also the undivided list used as argument of each recursive call. Writing it without aspatterns would have been a bit clunky because we would have to either use head
or needlessly reconstruct the original value of list
, i.e. actually evaluate x:xs
on the right side:
contrivedMap :: ([a] > a > b) > [a] > [b] contrivedMap f [] = [] contrivedMap f (x:xs) = f (x:xs) x : contrivedMap f xs
Exercises 

Implement scanr , as in the exercise in List processing, but this time using an aspattern. 
Introduction to records
For constructors with many elements, records provide a way of naming values in a datatype using the following syntax:
data Foo2 = Bar2  Baz2 {bazNumber::Int, bazName::String}
Using records allows doing matching and binding only for the variables relevant to the function we're writing, making code much clearer:
h :: Foo2 > Int h Baz2 {bazName=name} = length name h Bar2 {} = 0
Also, the {}
pattern can be used for matching a constructor regardless of the datatype elements even if you don't use records in the data
declaration:
data Foo = Bar  Baz Int g :: Foo > Bool g Bar {} = True g Baz {} = False
The function g
does not have to be changed if we modify the number or the type of elements of the constructors Bar
or Baz
.
There are further advantages to using record syntax which we will cover records in more detail in the Named fields section of the More on datatypes chapter.
Where we can use pattern matching
The short answer is that wherever you can bind variables, you can pattern match. Let us have a glance at such places we have seen before; a few more will be introduced in the following chapters.
Equations
The most obvious use case is the lefthand side of function definition equations, which were the subject of our examples so far.
map _ [] = [] map f (x:xs) = f x : map f xs
In the map
definition we're doing pattern matching on the left hand side of both equations, and also binding variables on the second one.
let expressions and where clauses
Both let
and where
are ways of doing local variable bindings. As such, you can also use pattern matching in them. A simple example:
y = let (x:_) = map (*2) [1,2,3] in x + 5
Or, equivalently,
y = x + 5 where (x:_) = map (*2) [1,2,3]
Here, x
will be bound to the first element of map ((*) 2) [1,2,3]
. y
, therefore, will evaluate to .
List comprehensions
After the 
in list comprehensions you can pattern match. This is actually extremely useful, and adds a lot to the expressiveness of comprehensions. Let's see how that works with a slightly more sophisticated example. Prelude provides a Maybe
type which has the following constructors:
data Maybe a = Nothing  Just a
It is typically used to hold values resulting from an operation which may or may not succeed; if the operation succeeds, the Just
constructor is used and the value is passed to it; otherwise Nothing
is used.^{[4]} The utility function catMaybes
(which is available from Data.Maybe library module) takes a list of Maybes (which may contain both "Just" and "Nothing" Maybes), and retrieves the contained values by filtering out the Nothing
values and getting rid of the Just
wrappers of the Just x
. Writing it with list comprehensions is very straightforward:
catMaybes :: [Maybe a] > [a] catMaybes ms = [ x  Just x < ms ]
Another nice thing about using a list comprehension for this task is that if the pattern match fails (that is, it meets a Nothing) it just moves on to the next element in ms
, thus avoiding the need of explicitly handling constructors we are not interested in with alternate function definitions.^{[5]}
do blocks
Within a do
block like the ones we used in the Simple input and output chapter, we can pattern match with the lefthand side of the left arrow variable bindings:
putFirstChar = do (c:_) < getLine putStrLn [c]
Furthermore, the let
bindings in do
blocks are, as far as pattern matching is concerned, just the same as the "real" let expressions.
Notes
 ↑ If you came here looking for regex pattern matching, you might be interested in looking at the Haskell Text.Regex library wrapper.
 ↑ Reasonable for this particular task, and only because it makes sense to expect that
dropThree
will give[]
when applied to a list of, say, two elements. With a different problem, it might not be reasonable to return any list if the first match failed. In a later chapter, we will consider one simple way of dealing with such cases.  ↑ As perhaps could be expected, this kind of matching with literals is not constructorbased. Rather, there is an equality comparison behind the scenes
 ↑ The canonical example of such an operation is looking up values in a dictionary  which might just be a
[(a, b)]
list with the tuples being keyvalue pairs, or a more sophisticated implementation. In any case, if we, given an arbitrary key, try to retrieve a value there is no guarantee we will actually find a value associated to the key.  ↑ The reason why it works this way instead of crashing out on a pattern matching failure has to do with the real nature of list comprehensions: They are actually wrappers for the list monad. We will eventually explain what that means when we discuss monads.
Control structures
Haskell offers several ways of expressing a choice between different values. We explored some of them in the Haskell Basics chapters. This section will bring together what we have seen thus far, discuss some finer points, and introduce a new control structure.
if and guards revisited
We have already met these constructs. The syntax for if
expressions is:
if <condition> then <truevalue> else <falsevalue>
<condition> is an expression which evaluates to a boolean. If the <condition> is True then the <truevalue> is returned, otherwise the <falsevalue> is returned. Note that in Haskell if is an expression (which is converted to a value) and not a statement (which is executed) as in many imperative languages.^{[1]} As a consequence, the else is mandatory in Haskell. Since if is an expression, it must evaluate to a result whether the condition is true or false, and the else ensures this. Furthermore, <truevalue> and <falsevalue> must evaluate to the same type, which will be the type of the whole if expression.
When if
expressions are split across multiple lines, they are usually indented by aligning else
s with then
s, rather than with if
s. A common style looks like this:
describeLetter :: Char > String describeLetter c = if c >= 'a' && c <= 'z' then "Lower case" else if c >= 'A' && c <= 'Z' then "Upper case" else "Not an ASCII letter"
Guards and toplevel if
expressions are mostly interchangeable. With guards, the example above is a little neater:
describeLetter :: Char > String describeLetter c  c >= 'a' && c <= 'z' = "Lower case"  c >= 'A' && c <= 'Z' = "Upper case"  otherwise = "Not an ASCII letter"
Remember that otherwise
is just an alias to True
, and thus the last guard is a catchall, playing the role of the final else
of the if
expression.
Guards are evaluated in the order they appear. Consider a set up like the following:
f (pattern1)  predicate1 = w  predicate2 = x f (pattern2)  predicate3 = y  predicate4 = z
Here, the argument of f
will be patternmatched against pattern1. If it succeeds, then we proceed to the first set of guards: if predicate1 evaluates to True
, then w
is returned. If not, then predicate2 is evaluated; and if it is true x
is returned. Again, if not, then we proceed to the next case and try to match the argument against pattern2, repeating the guards procedure with predicate3 and predicate4. (Of course, if neither pattern matches or neither predicate is true for the matching pattern there will be a runtime error. Regardless of the chosen control structure, it is important to ensure all cases are covered.)
Embedding if expressions
A handy consequence of if
constructs being expressions is that they can be placed anywhere a Haskell expression could be, allowing us to write code like this:
g x y = (if x == 0 then 1 else sin x / x) * y
Note that we wrote the if
expression without line breaks for maximum terseness. Unlike if
expressions, guard blocks are not expressions; and so a let
or a where
definition is the closest we can get to this style when using them. Needless to say, more complicated oneline if
expressions would be hard to read, making let
and where
attractive options in such cases.
case expressions
One control structure we haven't talked about yet are case
expressions. They are to piecewise function definitions what if
expressions are to guards. Take this simple piecewise definition:
f 0 = 18 f 1 = 15 f 2 = 12 f x = 12  x
It is equivalent to  and, indeed, syntactic sugar for:
f x = case x of 0 > 18 1 > 15 2 > 12 _ > 12  x
Whatever definition we pick, the same happens when f
is called: The argument x
is matched against all of the patterns in order; and on the first match the expression on the righthand side of the corresponding equal sign (in the piecewise version) or arrow (in the case
version) is evaluated. Note that in this case
expression there is no need to write x
in the pattern; the wildcard pattern _
gives the same effect.^{[2]}
Indentation is important when using case
. The cases must be indented further to the right than the beginning of the line containing the of
keyword, and all cases must have the same indentation. For the sake of illustration, here are two other valid layouts for a case
expression:
f x = case x of 0 > 18 1 > 15 2 > 12 _ > 12  x
f x = case x of 0 > 18 1 > 15 2 > 12 _ > 12  x
Since the left hand side of any case branch is just a pattern, it can also be used for binding, exactly like in piecewise function definitions:^{[3]}
describeString :: String > String describeString str = case str of (x:xs) > "The first character of the string is: " ++ [x] ++ "; and " ++ "there are " ++ show (length xs) ++ " more characters in it." [] > "This is an empty string."
This function describes some properties of str using a humanreadable string. Using case syntax to bind variables to the head and tail of our list is convenient here, but you could also do this with an ifstatement (with a condition of null str
to pick the empty string case).
Finally, just like if
expressions (and unlike piecewise definitions), case
expressions can be embedded anywhere another expression would fit:
data Colour = Black  White  RGB Int Int Int describeBlackOrWhite :: Colour > String describeBlackOrWhite c = "This colour is" ++ case c of Black > " black" White > " white" RGB 0 0 0 > " black" RGB 255 255 255 > " white" _ > "... uh... something else" ++ ", yeah?"
The case block above fits in as any string would. Writing describeBlackOrWhite
this way makes let
/where
unnecessary (although the resulting definition is not as readable).
Exercises 

Use a case statement to implement a fakeIf function which could be used as a replacement to the familiar if expressions. 
Controlling actions, revisited
In the final part of this chapter, we will introduce a few extra points about control structures while revisiting the discussions in the "Simple input and output" chapter. There, in the Controlling actions section, we used the following function to show how to execute actions conditionally within a do
block using if
expressions:
doGuessing num = do putStrLn "Enter your guess:" guess < getLine if (read guess) < num then do putStrLn "Too low!" doGuessing num else if (read guess) > num then do putStrLn "Too high!" doGuessing num else do putStrLn "You Win!"
We can write the same doGuessing
function using a case statement. To do this, we first introduce the Prelude function compare
which takes two values of the same type (in the Ord
class) and returns a value of type Ordering
— namely one of GT
, LT
, EQ
, depending on whether the first is greater than, less than, or equal to the second.
doGuessing num = do putStrLn "Enter your guess:" guess < getLine case compare (read guess) num of LT > do putStrLn "Too low!" doGuessing num GT > do putStrLn "Too high!" doGuessing num EQ > putStrLn "You Win!"
The dos after the >
s are necessary on the first two options, because we are sequencing actions within each case.
A note about return
Now, we are going to dispel a possible source of confusion. In a typical imperative language (C, for example) an implementation of doGuessing
might look like the following (if you don't know C, don't worry with the details, just follow the ifelse chain):
void doGuessing(int num) { printf("Enter your guess:"); int guess = atoi(readLine()); if (guess == num) { printf("You win!\n"); return (); } // we won't get here if guess == num if (guess < num) { printf("Too low!\n"); doGuessing(num); } else { printf("Too high!\n"); doGuessing(num); } }
This doGuessing
first tests the equality case, which does not lead to a new call of doGuessing
, and the if
has no accompanying else
. If the guess was right, a return
statement is used to exit the function at once, skipping the other cases. Now, going back to Haskell, action sequencing in do
blocks looks a lot like imperative code, and furthermore there actually is a return
in Prelude. Then, knowing that case
statements (unlike if
statements) do not force us to cover all cases, one might be tempted to write a literal translation of the C code above (try running it if you are curious)...
doGuessing num = do putStrLn "Enter your guess:" guess < getLine case compare (read guess) num of EQ > do putStrLn "You win!" return ()  we don't expect to get here if guess == num if (read guess < num) then do print "Too low!"; doGuessing num else do print "Too high!"; doGuessing num
... but it won't work! If you guess correctly, the function will first print "You win!," but it will not exit at the return ()
. Instead, the program will continue to the if
expression and check whether guess
is less than num
. Of course it is not, so the else branch is taken, and it will print "Too high!" and then ask you to guess again. Things aren't any better with an incorrect guess: it will try to evaluate the case statement and get either LT
or GT
as the result of the compare
. In either case, it won't have a pattern that matches, and the program will fail immediately with an exception (as usual, the incomplete case
alone should be enough to raise suspicion).
The problem here is that return
is not at all equivalent to the C (or Java etc.) statement with the same name. For our immediate purposes, we can say that return
is a function.^{[4]} The return ()
in particular evaluates to an action which does nothing. return
does not affect the control flow at all. In the correct guess case, the case statement evaluates to return ()
, an action of type IO ()
, and execution just follows along normally.
The bottom line is that while actions and do
blocks resemble imperative code, they must be dealt with on their own terms  Haskell terms.
Exercises 

main = do x < getX putStrLn x getX = do return "My ShangriLa" return "beneath" return "the summer moon" return "I will" return "return" return "again" 
Notes
 ↑ If you have programmed in C or Java, you will recognize Haskell's if/then/else as an equivalent to the ternary conditional operator
?:
.  ↑ To see why this is so, consider our discussion of matching and binding in the Pattern matching section
 ↑ Thus,
case
statements are a lot more versatile than most of the superficially similar switch/case statements in imperative languages which are typically restricted to equality tests on integral primitive types.  ↑ Superfluous note: somewhat closer to a proper explanation, we might say
return
is a function which takes a value and makes it into an action which, when evaluated, gives the original value. Areturn "strawberry"
within one of thedo
blocks we are dealing with would have typeIO String
 the same type asgetLine
. Do not worry if that doesn't make sense for now; you will understand whatreturn
really does when we actually start discussing monads further ahead on the book.
More on functions
Here are several nice features that make using functions easier.
let and where revisited
As discussed in earlier chapters, let
and where
are useful in local function definitions. Here, sumStr
calls addStr
function:
addStr :: Float > String > Float addStr x str = x + read str sumStr :: [String] > Float sumStr = foldl addStr 0.0
But what if we never need addStr
anywhere else? Then we could rewrite sumStr
using local bindings. We can do that either with a let binding...
sumStr = let addStr x str = x + read str in foldl addStr 0.0
... or with a where
clause...
sumStr = foldl addStr 0.0 where addStr x str = x + read str
... and the difference appears to be just a question of style: Do we prefer the bindings to come before or after the rest of the definition?
However, there is another important difference between let
and where
. The let...in construct is an expression just like if/then/else. In contrast, where
clauses are like guards and so are not expressions. Thus, let
bindings can be used within complex expressions:
f x = if x > 0 then (let lsq = (log x) ^ 2 in tan lsq) * sin x else 0
The expression within the outer parentheses is selfcontained, and evaluates to the tangent of the square of the logarithm of x
. Note that the scope of lsq
does not extend beyond the parentheses; so changing the thenbranch to
then (let lsq = (log x) ^ 2 in tan lsq) * (sin x + lsq)
does not work without dropping the parentheses around the let
.
Despite not being full expressions, where
clauses can be incorporated into case
expressions:
describeColour c = "This colour " ++ case c of Black > "is black" White > "is white" RGB red green blue > " has an average of the components of " ++ show av where av = (red + green + blue) `div` 3 ++ ", yeah?"
In this example, the indentation of the where clause sets the scope of the av variable so that it only exists as far as the RGB red green blue case is concerned. Placing it at the same indentation of the cases would make it available for all cases. Here is an example with guards:
doStuff :: Int > String doStuff x  x < 3 = report "less than three"  otherwise = report "normal" where report y = "the input is " ++ y
Note that since there is one equals sign for each guard there is no place we could put a let
expression which would be in scope of all guards in the manner of the where
clause. So this is a situation in which where
is particularly convenient.
Anonymous Functions  lambdas
Why create a formal name for a function like addStr
when it only exists within another function's definition, never to be used again? Instead, we can make it an anonymous function also known as a lambda function
. Then, sumStr
could be defined like this:
sumStr = foldl (\ x str > x + read str) 0.0
The expression in the parentheses is a lambda function. The backslash is used as the nearest ASCII equivalent to the Greek letter lambda (λ). This lambda function takes two arguments, x
and str
, and it evaluates to "x + read str". So, the sumStr
presented just above is precisely the same as the one that used addStr
in a let binding.
Lambdas are handy for writing oneoff functions to be used with maps, folds and their siblings, especially where the function in question is simple (beware of cramming complicated expressions in a lambda — it can hurt readability).
Since variables are being bound in a lambda expression (to the arguments, just like in a regular function definition), pattern matching can be used in them as well. A trivial example would be redefining tail
with a lambda:
tail' = (\ (_:xs) > xs)
Note: Since lambdas are a special character in Haskell, the \
on its own will be treated as the function and whatever nonspace character is next will be the variable for the first argument. It is still good form to put a space between the lambda and the argument as in normal function syntax (especially to make things clearer when a lambda takes more than one argument).
Operators
In Haskell, any function that takes two arguments and has a name consisting entirely of nonalphanumeric characters is considered an operator. The most common examples are the arithmetical ones like addition (+) and subtraction (). Unlike other functions, operators are normally used infix (written between the two arguments). All operators can also be surrounded with parentheses and then used prefix like other functions:
 these are the same: 2 + 4 (+) 2 4
We can define new operators in the usual way as other functions — just don't use any alphanumeric characters in their names. For example, here's the setdifference definition from Data.List
:
(\\) :: (Eq a) => [a] > [a] > [a] xs \\ ys = foldl (\zs y > delete y zs) xs ys
As the example above shows, operators can be defined infix as well. The same definition written as prefix also works:
(\\) xs ys = foldl (\zs y > delete y zs) xs ys
Note that the type declarations for operators have no infix version and must be written with the parentheses.
Sections
Sections are a nifty piece of syntactical sugar that can be used with operators. An operator within parentheses and flanked by one of its arguments...
(2+) 4 (+4) 2
... is a new function in its own right. (2+)
, for instance, has the type (Num a) => a > a
. We can pass sections to other functions, e.g. map (+2) [1..4] == [3..6]
. For another example, we can add an extra flourish to the multiplyList
function we wrote back in More about lists:
multiplyList :: Integer > [Integer] > [Integer] multiplyList m = map (m*)
If you have a "normal" prefix function and want to use it as an operator, simply surround it with backticks:
1 `elem` [1..4]
This is called making the function infix. It's normally done for readability purposes: 1 `elem` [1..4]
reads better than elem 1 [1..4]
. You can also define functions infix:
elem :: (Eq a) => a > [a] > Bool x `elem` xs = any (==x) xs
But once again notice that the type signature stays with the prefix style.
Sections even work with infix functions:
(1 `elem`) [1..4] (`elem` [1..4]) 1
Of course, remember that you can only make binary functions (that is, those that take two arguments) infix.
Exercises 


Higher order functions and Currying
At the heart of functional programming is the idea that functions are just like any other value. The power of functional style comes from handling functions themselves as regular values, i.e. by passing functions to other functions and returning them from functions. A function that takes another function (or several functions) as an argument is called a higherorder function. They can be found pretty much anywhere in a Haskell program; and indeed we have already met some of them, such as map
and the various folds. We saw commonplace examples of higherorder functions when discussing map
in More about lists. Now, we are going to explore some common ways of writing code that manipulates functions.
A sorting algorithm
For a concrete example, we will consider the task of sorting a list. Quicksort is a wellknown recursive sorting algorithm. To apply its sorting strategy to a list, we first choose one element and then divide the rest of the list into (A) those elements that should go before the chosen element, (B) those elements equal to the chosen one, and (C) those that should go after. Then, we apply the same algorithm to the unsorted (A) and (C) lists. After enough recursive sorting, we concatenate everything back together and have a final sorted list. That strategy can be translated into a Haskell implementation in a very simple way.
 Type signature: any list with elements in the Ord class can be sorted. quickSort :: (Ord a) => [a] > [a]  Base case:  If the list is empty, there is nothing to do. quickSort [] = []  The recursive case:  We pick the first element as our "pivot", the rest is to be sorted.  Note how the pivot itself ends up included in the middle part. quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more) where less = filter (< x) xs equal = filter (== x) xs more = filter (> x) xs
It should be pointed out that our quickSort
is rather naïve. A more efficient implementation would avoid the three passes through filter
at each recursive step and not use (++)
to build the sorted list. Furthermore, unlike our implementation, the original quicksort algorithm does the sorting inplace using mutability.^{[1]} We will ignore such concerns for now, as we are more interested in the usage patterns of sorting functions, rather than in exact implementation.
The Ord
class
Almost all the basic data types in Haskell are members of the Ord
class, which is for ordering tests what Eq
is for equality tests. The Ord
class defines which ordering is the "natural" one for a given type. It provides a function called compare
, with type:
compare :: (Ord a) => a > a > Ordering
compare
takes two values and compares them, returning an Ordering
value, which is LT
if the first value is less than the second, EQ
if it is equal and GT
if it is greater than. For an Ord
type, (<)
, (==)
from Eq
and (>)
can be seen as shortcuts to compare
that check for one of the three possibilities and return a Bool
to indicate whether the specified ordering is true according to the Ord
specification for that type. Note that each of the tests we use with filter
in the definition of quickSort
corresponds to one of the possible results of compare
, and so we might have written, for instance, less
as less = filter (\y > y `compare` x == LT) xs
.
Choosing how to compare
With quickSort
, sorting any list with elements in the Ord
class is easy. Suppose we have a list of String
and we want to sort them; we just apply quickSort
to the list. For the rest of this chapter, we will use a pseudodictionary of just a few words (but dictionaries with thousands of words would work just as well):
dictionary = ["I", "have", "a", "thing", "for", "Linux"]
quickSort dictionary
returns:
["I", "Linux", "a", "for", "have", "thing"]
As you can see, capitalization is considered for sorting by default. Haskell String
s are lists of Unicode characters. Unicode (and almost all other encodings of characters) specifies that the character code for capital letters are less than the lower case letters. So "Z" is less than "a".
To get a proper dictionarylike sorting, we need a case insensitive quickSort
. To achieve that, we can take a hint from the discussion of compare
just above. The recursive case of quickSort
can be rewritten as:
quickSort compare (x : xs) = (quickSort compare less) ++ (x : equal) ++ (quickSort compare more) where less = filter (\y > y `compare` x == LT) xs equal = filter (\y > y `compare` x == EQ) xs more = filter (\y > y `compare` x == GT) xs
While this version is less tidy than the original one, it makes it obvious that the the ordering of the elements hinges entirely on the compare
function. That means we only need to replace compare
with an (Ord a) => a > a > Ordering
function of our choice. Therefore, our updated quickSort'
is a higherorder function which takes a comparison function along with the list to sort.
quickSort' :: (Ord a) => (a > a > Ordering) > [a] > [a]  No matter how we compare two things the base case doesn't change,  so we use the _ "wildcard" to ignore the comparison function. quickSort' _ [] = []  c is our comparison function quickSort' c (x : xs) = (quickSort' c less) ++ (x : equal) ++ (quickSort' c more) where less = filter (\y > y `c` x == LT) xs equal = filter (\y > y `c` x == EQ) xs more = filter (\y > y `c` x == GT) xs
We can reuse our quickSort'
function to serve many different purposes.
If we wanted a descending order, we could just reverse our original sorted list with reverse (quickSort dictionary)
. Yet to actually do the initial sort descending, we could supply quickSort'
with a comparison function that returns the opposite of the usual Ordering
.
 the usual ordering uses the compare function from the Ord class usual = compare  the descending ordering, note we flip the order of the arguments to compare descending x y = compare y x  the caseinsensitive version is left as an exercise! insensitive = ...  How can we do caseinsensitive comparisons without making a big list of all possible cases?
Note
Data.List
offers a sort
function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort. Data.List
also includes sortBy
, which takes a custom comparison function just like our quickSort'
Exercises 

Write insensitive , such that quickSort' insensitive dictionary gives ["a", "for", "have", "I", "Linux", "thing"] . 
HigherOrder Functions and Types
The concept of currying (the generating of intermediate functions on the way toward a final result) was first introduced in the earlier chapter "More about lists". This is a good place to revisit how currying works.
Our quickSort'
has type (a > a > Ordering) > [a] > [a]
.
Most of the time, the type of a higherorder function provides a guideline about how to use it. A straightforward way of reading the type signature would be "quickSort'
takes, as its first argument, a function that gives an ordering of two a
s. Its second argument is a list of a
s. Finally, it returns a new list of a
s". This is enough to correctly guess that it uses the given ordering function to sort the list.
Note that the parentheses surrounding a > a > Ordering
are mandatory. They specify that a > a > Ordering
forms a single argument that happens to be a function.
Without the parentheses, we would get a > a > Ordering > [a] > [a]
which accepts four arguments (none of which are themselves functions) instead of the desired two, and that wouldn't work as desired.
Remember that the >
operator is rightassociative. Thus, our erroneous type signature a > a > Ordering > [a] > [a]
means the same thing as a > (a > (Ordering > ([a] > [a])))
.
Given that >
is rightassociative, the explicitly grouped version of the correct quickSort'
signature is actually (a > a > Ordering) > ([a] > [a])
. This makes perfect sense. Our original quickSort
lacking the adjustable comparison function argument was of type [a] > [a]
. It took a list and sorted it. Our new quickSort'
is simply a function that generates quickSort
style functions! If we plug in compare
for the (a > a > Ordering)
part, then we just return our original simple quickSort
function. If we use a different comparison function for the argument, we generate a different variety of a quickSort
function.
Of course, if we not only give a comparison function as an argument but also feed in an actual list to sort, then the final result is not the new quickSort
style function; instead, it continues on and passes the list to the new function and returns the sorted list as our final result.
Exercises 

(Challenging) The following exercise combines what you have learned about higher order functions, recursion and I/O. We are going to recreate what is known in imperative languages as a for loop. Implement a function for :: a > (a > Bool) > (a > a) > (a > IO ()) > IO () for i p f job =  ??? An example of how this function would be used might be for 1 (<10) (+1) print which prints the numbers 1 to 9 on the screen. The desired behaviour of
Some more challenging exercises you could try

Function manipulation
We will close the chapter by discussing a few examples of common and useful generalpurpose higherorder functions. Familiarity with these will greatly enhance your skill at both writing and reading Haskell code.
Flipping arguments
flip
is a handy little Prelude function. It takes a function of two arguments and returns a version of the same function with the arguments swapped.
flip :: (a > b > c) > b > a > c
flip
in use:
Prelude> (flip (/)) 3 1 0.3333333333333333 Prelude> (flip map) [1,2,3] (*2) [2,4,6]
We could have used flip to write a pointfree version of the descending
comparing function from the quickSort example:
descending = flip compare
flip
is particularly useful when we want to pass a function with two arguments of different types to another function and the arguments are in the wrong order with respect to the signature of the higherorder function.
Composition
The (.)
composition operator is another higherorder function. It has the signature:
(.) :: (b > c) > (a > b) > a > c
(.)
takes two functions as arguments and returns a new function which applies both the second argument and then the first.
Composition and higherorder functions provide a range of powerful tricks. For a tiny sample, first consider the inits
function, defined in the module Data.List
. Quoting the documentation, it "returns all initial segments of the argument, shortest first", so that:
Prelude Data.List> inits [1,2,3] [[],[1],[1,2],[1,2,3]]
We can provide a oneline implementation for inits
(written pointfree for extra dramatic effect) using only the following higherorder functions from Prelude: flip
, scanl
, (.)
and map
:
myInits :: [a] > [[a]] myInits = map reverse . scanl (flip (:)) []
Swallowing a definition so condensed may look daunting at first, so analyze it slowly, bit by bit, recalling what each function does and using the type signatures as a guide.
The definition of myInits
is super concise and clean with use of parentheses kept to a bare minimum. Naturally, if one goes overboard with composition by writing milelong (.)
chains, things will get confusing; but, when deployed reasonably, these pointfree styles shine. Furthermore, the implementation is quite "high level": we do not deal explicitly with details like pattern matching or recursion; the functions we deployed — both the higherorder ones and their functional arguments — take care of such plumbing.
Application
($)
is a curious higherorder operator. Its type is:
($) :: (a > b) > a > b
It takes a function as its first argument, and all it does is to apply the function to the second argument, so that, for instance, (head $ "abc") == (head "abc")
.
You might think that ($)
is completely useless! However, there are two interesting points about it. First, ($)
has very low precedence,^{[2]} unlike regular function application which has the highest precedence. In effect, that means we can avoid confusing nesting of parentheses by breaking precedence with $
. We write a nonpointfree version of myInits
without adding new parentheses:
myInits :: [a] > [[a]] myInits xs = map reverse . scanl (flip (:)) [] $ xs
Furthermore, as ($)
is just a function which happens to apply functions, and functions are just values, we can write intriguing expressions such as:
map ($ 2) [(2*), (4*), (8*)]
(Yes, that is a list of functions, and it is perfectly legal.)
uncurry
and curry
As the name suggests, uncurry
is a function that undoes currying; that is, it converts a function of two arguments into a function that takes a pair as its only argument.
uncurry :: (a > b > c) > (a, b) > c
Prelude> let addPair = uncurry (+) Prelude> addPair (2, 3) 5
One interesting use of uncurry
occasionally seen in the wild is in combination with ($)
, so that the first element of a pair is applied to the second.
Prelude> uncurry ($) (reverse, "stressed") "desserts"
There is also curry
, which is the opposite of uncurry
.
curry :: ((a, b) > c) > a > b > c
Prelude> curry addPair 2 3  addPair as in the earlier example. 5
Because most Haskell functions are already curried, curry
is nowhere near as common as uncurry
.
id
and const
Finally, we should mention two functions which, while not higherorder functions themselves, are most often used as arguments to higherorder functions. id
, the identity function, is a function with type a > a
that returns its argument unchanged.
Prelude> id "Hello" "Hello"
Similar in spirit to id
, const
is an a > b > a
function that works like this:
Prelude> const "Hello" "world" "Hello"
const
takes two arguments, discards the second and returns the first. Seen as a function of one argument, a > (b > a)
, it returns a constant function, which always returns the same value no matter what argument it is given.
id
and const
might appear worthless at first. However, when dealing with higherorder functions it is sometimes necessary to pass a dummy function, be it one that does nothing with its argument or one that always returns the same value. id
and const
give us convenient dummy functions for such cases.
Exercises 


Notes
 ↑ The "true", inplace quicksort can be done in Haskell, but it requires some rather advanced tools that we will not discuss in the Beginners' Track.
 ↑ As a reminder, precedence here is meant in the same sense that
*
has higher precedence (i.e. is evaluated first) than+
in mathematics.
Using GHCi effectively
GHCi assists in several ways toward more efficient work. Here, we will discuss some of the best practices for using GHCi.
User interface
Tab completion
As in many other terminal programs, you can enter some starting text in GHCi and then hit the Tab key to be presented with a list of all possibilities that start with what you've written so far. When there is only one possibility, using Tab will autocomplete the string. For example fol
<Tab> will append letter "d" (since nothing exists with "fol" other than items that start with "fold"). A second Tab will list the four functions included in Prelude: foldl
, foldl1
, foldr
, and foldr1
. More options may show if you have already imported additional modules.
Tab completion works also when you are loading a file with your program into GHCi. For example, after typing :l fi
<Tab>, you will be presented with all files that start with "fi" that are present in the current directory (the one you were in when you launched GHCi).
The same also applies when you are importing modules, after typing :m +Da
<Tab> or import Da
<Tab>, you will be presented with all modules that start with "Da" present in installed packages.
": commands"
On GHCi command line, commands for the interpreter start with the character ":" (colon).
:help
or:h
 prints a list of all available commands.:load
or:l
 loads a given file into GHCi (you must include the filename with the command).:reload
or:r
 reloads whatever file had been loaded most recently (useful after changes to the file).:type
or:t
 prints the type of a given expression included with the command:module
or:m
 loads a given module (include the module name with the command). You can also unload a module by adding a
symbol before the module name.:browse
 gives the type signatures for all functions available from a given module.
Here again, you can use Tab to see the list of commands, type :Tab to see all possible commands.
Timing Functions in GHCi
GHCi provides a basic way to measure how much time a function takes to run, which can be useful for to find out which version of a function runs fastest (such as when there are multiple ways to define something to get the same effective result).
 Type
:set +s
into the ghci command line.  run the function(s) you are testing. The time the function took to run will be displayed after GHCi outputs the results of the function.
Multiline Input
If you are trying to define a function that takes up multiple lines, or if you want to type a do block into ghci (without writing a file that you then import), there is an easy way to do this:
 Begin a new line with
:{
 Type in your code. Press enter when you need a new line.
 Type
:}
to end the multiline input.
For example:
*Main> :{ *Main let askname = do *Main putStrLn "What is your name?" *Main name < getLine *Main putStrLn $ "Hello " ++ name *Main :} *Main>
The same can be accomplished by using :set +m
command (allow multiline commands). In this case, an empty line will end the block.
In addition, line breaks in ghci commands can be separated by ;
, like this:
*Main> let askname1 = do ; putStrLn "what is your name?" ; name < getLine ; putStrLn $ "Hello " ++ name
Intermediate Haskell
Modules
Modules are the primary means of organizing Haskell code. We met them in passing when using import
statements to put library functions into scope. Beyond allowing us to make better use of libraries, knowledge of modules will help us to shape our own programs and create standalone programs which can be executed independently of GHCi (incidentally, that is the topic of the very next chapter, Standalone programs).
Modules
Haskell modules^{[1]} are a useful way to group a set of related functionalities into a single package and manage different functions that may have the same names. The module definition is the first thing that goes in your Haskell file.
A basic module definition looks like:
module YourModule where
Note that
 the name of the module begins with a capital letter;
 each file contains only one module.
The name of the file is the name of the module plus the .hs file extension. Any dots '.' in the module name are changed for directories.^{[2]} So the module YourModule would be in the file YourModule.hs while a module Foo.Bar would be in the file Foo/Bar.hs or Foo\Bar.hs. Since the module name must begin with a capital letter, the file name must also start with a capital letter.
Importing
Modules can themselves import functions from other modules. That is, in between the module declaration and the rest of your code, you may include some import declarations such as
import Data.Char (toLower, toUpper)  import only the functions toLower and toUpper from Data.Char import Data.List  import everything exported from Data.List import MyModule  import everything exported from MyModule
Imported datatypes are specified by their name, followed by a list of imported constructors in parenthesis. For example:
import Data.Tree (Tree(Node))  import only the Tree data type and its Node constructor from Data.Tree
What if you import some modules that have overlapping definitions? Or if you import a module but want to overwrite a function yourself? There are three ways to handle these cases: Qualified imports, hiding definitions, and renaming imports.
Qualified imports
Say MyModule and MyOtherModule both have a definition for remove_e, which removes all instances of e from a string. However, MyModule only removes lowercase e's, and MyOtherModule removes both upper and lower case. In this case the following code is ambiguous:
import MyModule import MyOtherModule  someFunction puts a c in front of the text, and removes all e's from the rest someFunction :: String > String someFunction text = 'c' : remove_e text
It isn't clear which remove_e is meant! To avoid this, use the qualified keyword:
import qualified MyModule import qualified MyOtherModule someFunction text = 'c' : MyModule.remove_e text  Will work, removes lower case e's someOtherFunction text = 'c' : MyOtherModule.remove_e text  Will work, removes all e's someIllegalFunction text = 'c' : remove_e text  Won't work as there is no remove_e defined
In the latter code snippet, no function named remove_e is available at all. When we do qualified imports, all the imported values include the module names as a prefix. Incidentally, you can also use the same prefixes even if you did a regular import (in our example, MyModule.remove_e works even if the "qualified" keyword isn't included).
Note
There is an ambiguity between a qualified name like MyModule.remove_e
and the function composition operator (.)
. Writing reverse.MyModule.remove_e
is bound to confuse your Haskell compiler. One solution is stylistic: always use spaces for function composition, for example, reverse . remove_e
or Just . remove_e
or even Just . MyModule.remove_e
Hiding definitions
Now suppose we want to import both MyModule and MyOtherModule, but we know for sure we want to remove all e's, not just the lower cased ones. It will become really tedious to add MyOtherModule before every call to remove_e. Can't we just exclude the remove_e from MyModule?
import MyModule hiding (remove_e) import MyOtherModule someFunction text = 'c' : remove_e text
This works because of the word hiding on the import line. Whatever follows the "hiding" keyword will not be imported. Hide multiple items by listing them with parentheses and commaseparation:
import MyModule hiding (remove_e, remove_f)
Note that algebraic datatypes and type synonyms cannot be hidden. These are always imported. If you have a datatype defined in multiple imported modules, you must use qualified names.
Renaming imports
This is not really a technique to allow for overwriting, but it is often used along with the qualified flag. Imagine:
import qualified MyModuleWithAVeryLongModuleName someFunction text = 'c' : MyModuleWithAVeryLongModuleName.remove_e $ text
Especially when using qualified, this gets irritating. We can improve things by using the as keyword:
import qualified MyModuleWithAVeryLongModuleName as Shorty someFunction text = 'c' : Shorty.remove_e $ text
This allows us to use Shorty instead of MyModuleWithAVeryLongModuleName as prefix for the imported functions. This renaming works with both qualified and regular importing.
As long as there are no conflicting items, we can import multiple modules and rename them the same:
import MyModule as My import MyCompletelyDifferentModule as My
In this case, both the functions in MyModule and the functions in MyCompletelyDifferentModule can be prefixed with My.
Combining renaming with limited import
Sometimes it is convenient to use the import directive twice for the same module. A typical scenario is as follows:
import qualified Data.Set as Set import Data.Set (Set, empty, insert)
This give access to all of the Data.Set module via the alias "Set", and also lets you access a few selected functions (empty, insert, and the constructor) without using the "Set" prefix.
Exporting
In the examples at the start of this article, the words "import everything exported from MyModule" were used.^{[3]} This raises a question. How can we decide which functions are exported and which stay "internal"? Here's how:
module MyModule (remove_e, add_two) where add_one blah = blah + 1 remove_e text = filter (/= 'e') text add_two blah = add_one . add_one $ blah
In this case, only remove_e and add_two are exported. While add_two is allowed to make use of add_one, functions in modules that import MyModule cannot use add_one directly, as it isn't exported.
Datatype export specifications are written similarly to import. You name the type, and follow with the list of constructors in parenthesis:
module MyModule2 (Tree(Branch, Leaf)) where data Tree a = Branch {left, right :: Tree a}  Leaf a
In this case, the module declaration could be rewritten "MyModule2 (Tree(..))", declaring that all constructors are exported.
Maintaining an export list is good practice not only because it reduces namespace pollution but also because it enables certain compiletime optimizations which are unavailable otherwise.
Notes
 ↑ See the Haskell report for more details on the module system.
 ↑ In Haskell98, the last standardised version of Haskell before Haskell 2010, the module system was fairly conservative, but recent common practice consists of employing a hierarchical module system, using periods to section off namespaces.
 ↑ A module may export functions that it imports. Mutually recursive modules are possible but need some special treatment.
Indentation
Haskell relies on indentation to reduce the verbosity of your code. Despite some complexity in practice, there are really only a couple fundamental layout rules.^{[1]}
The golden rule of indentation
Code which is part of some expression should be indented further in than the beginning of that expression (even if the expression is not the leftmost element of the line).
The easiest example is a 'let' binding group. The equations binding the variables are part of the 'let' expression, and so should be indented further in than the beginning of the binding group: the 'let' keyword. When you start the expression on a separate line, you only need to indent by one space (although more than one space is also acceptable and may be clearer).
let x = a y = b
You may also place the first clause alongside the 'let' as long as you indent the rest to line up:
wrong  wrong  right 

let x = a y = b 
let x = a y = b 
let x = a y = b 
This tends to trip up a lot of beginners: All grouped expressions must be exactly aligned. On the first line, Haskell counts everything to the left of the expression as indent, even though it is not whitespace.
Here are some more examples:
do foo bar baz do foo bar baz where x = a y = b case x of p > foo p' > baz
Note that with 'case' it is less common to place the first subsidiary expression on the same line as the 'case' keyword (although it would still be valid code). Hence, the subsidiary expressions in a case expression tend to be indented only one step further than the 'case' line. Also note how we lined up the arrows here: this is purely aesthetic and is not counted as different layout; only indentation (i.e. whitespace beginning on the farleft edge) makes a difference to the interpretation of the layout.
Things get more complicated when the beginning of the expression doesn't start at the lefthand edge. In this case, it's safe to just indent further than the line containing the expression's beginning. So,
myFunction firstArgument secondArgument = do  the 'do' doesn't start at the lefthand edge foo  so indent these commands more than the beginning of the line containing the 'do'. bar baz
Here are some alternative layouts which all work:
myFunction firstArgument secondArgument = do foo bar baz myFunction firstArgument secondArgument = do foo bar baz myFunction firstArgument secondArgument = do foo bar baz
Explicit characters in place of indentation
Indentation is actually optional if you instead use semicolons and curly braces for grouping and separation, as in "onedimensional" languages like C. Even though the consensus among Haskell programmers is that meaningful indentation leads to betterlooking code, understanding how to convert from one style to the other can help understand the indentation rules. The entire layout process can be summed up in three translation rules (plus a fourth one that doesn't come up very often):
 If you see one of the layout keywords, (
let
,where
,of
,do
), insert an open curly brace (right before the stuff that follows it)  If you see something indented to the SAME level, insert a semicolon
 If you see something indented LESS, insert a closing curly brace
 If you see something unexpected in a list, like
where
, insert a closing brace before instead of a semicolon.
For instance, this definition...
foo :: Double > Double foo x = let s = sin x c = cos x in 2 * s * c
...can be rewritten without caring about the indentation rules as:
foo :: Double > Double; foo x = let { s = sin x; c = cos x; } in 2 * s * c
One circumstance in which explicit braces and semicolons can be convenient is when writing oneliners in GHCi:
Prelude> let foo :: Double > Double; foo x = let { s = sin x; c = cos x } in 2 * s * c
Exercises 

Rewrite this snippet from the Control Structures chapter using explicit braces and semicolons: doGuessing num = do putStrLn "Enter your guess:" guess < getLine case compare (read guess) num of LT > do putStrLn "Too low!" doGuessing num GT > do putStrLn "Too high!" doGuessing num EQ > putStrLn "You Win!" 
Layout in action
wrong  wrong  right  right 

do first thing second thing third thing 
do first thing second thing third thing 
do first thing second thing third thing 
do first thing second thing third thing 
Indent to the first
Due to the "golden rule of indentation" described above, a curly brace within a do
block depends not on the do
itself but the thing that immediately follows it. For example, this weirdlooking block of code is totally acceptable:
do first thing second thing third thing
As a result, you could also write combined if/do combination like this:
Wrong  Right  Right 

if foo then do first thing second thing third thing else do something else 
if foo then do first thing second thing third thing else do something else 
if foo then do first thing second thing third thing else do something else 
It isn't about the do
, it's about lining up all the items that are at the same level within the do
.
Thus, all of the following are acceptable:
main = do first thing second thing
or
main = do first thing second thing
or
main = do first thing second thing
if
within do
This is a combination which trips up many Haskell programmers. Why does the following block of code not work?
sweet but wrong  unsweet and wrong 

 why is this bad? do first thing if condition then foo else bar third thing 
 still bad, just explicitly so do { first thing ; if condition ; then foo ; else bar ; third thing } 
Naturally, the Haskell compiler is confused because it thinks that you never finished writing your if
expression, before writing a new statement. The compiler sees that you have written something like if condition;
, which is bad because it is unfinished. In order to fix this, we need to indent the bottom parts of this if block so that then
and else
become part of the if
statement.
sweet and correct  unsweet and correct 

 whew, fixed it! do first thing if condition then foo else bar third thing 
 the fixed version without sugar do { first thing ; if condition then foo else bar ; third thing } 
Now, the do block sees the whole if statement as one item. When ifthenelse statements are not within do blocks, this specific indentation isn't technically necessary, but it never hurts, so it is a good habit to always indent ifthenelse in this way.
Exercises 

The ifwithindo issue has tripped up so many Haskellers that one programmer has posted a proposal to the Haskell prime initiative to add optional semicolons between if then else . How would that help? 
Issues with indentation are explained further in connection with showing how do
is syntactic sugar for the monadic operator (>>=)
. See Translating the bind operator and the associated footnote about indentation.
Notes
 ↑ See section 2.7 of The Haskell Report (lexemes) on layout.
More on datatypes
Enumerations
One special case of the data
declaration is the enumeration — a data type where none of the constructor functions have any arguments:
data Month = January  February  March  April  May  June  July  August  September  October  November  December
You can mix constructors that do and do not have arguments, but then the result is not called an enumeration. The following example is not an enumeration because the last constructor takes three arguments:
data Colour = Black  Red  Green  Blue  Cyan  Yellow  Magenta  White  RGB Int Int Int
As you will see further on when we discuss classes and derivation, there are practical reasons to distinguish between what is and isn't an enumeration.
Incidentally, the Bool
datatype is an enumeration:
data Bool = False  True deriving (Bounded, Enum, Eq, Ord, Read, Show)
Named Fields (Record Syntax)
Consider a datatype whose purpose is to hold configuration settings. Usually, when you extract members from this type, you really only care about one or two of the many settings. Moreover, if many of the settings have the same type, you might often find yourself wondering "wait, was this the fourth or fifth element?" One way to clarify is to write accessor functions. Consider the following madeup configuration type for a terminal program:
data Configuration = Configuration String  User name String  Local host String  Remote host Bool  Is guest? Bool  Is superuser? String  Current directory String  Home directory Integer  Time connected deriving (Eq, Show)
You could then write accessor functions, such as:
getUserName (Configuration un _ _ _ _ _ _ _) = un getLocalHost (Configuration _ lh _ _ _ _ _ _) = lh getRemoteHost (Configuration _ _ rh _ _ _ _ _) = rh getIsGuest (Configuration _ _ _ ig _ _ _ _) = ig  And so on...
You could also write update functions to update a single element. Of course, if you add or remove an element in the configuration later, all of these functions now have to take a different number of arguments. This is quite annoying and is an easy place for bugs to slip in. Thankfully, there's a solution: we simply give names to the fields in the datatype declaration, as follows:
data Configuration = Configuration { username :: String , localHost :: String , remoteHost :: String , isGuest :: Bool , isSuperuser :: Bool , currentDir :: String , homeDir :: String , timeConnected :: Integer }
This will automatically generate the following accessor functions for us:
username :: Configuration > String localHost :: Configuration > String  etc.
This also gives us a convenient update method. Here is a short example for a "post working directory" and "change directory" functions that work on Configuration
s:
changeDir :: Configuration > String > Configuration changeDir cfg newDir = if directoryExists newDir  make sure the directory exists then cfg { currentDir = newDir } else error "Directory does not exist" postWorkingDir :: Configuration > String postWorkingDir cfg = currentDir cfg
So, in general, to update the field x
in a datatype y
to z
, you write y { x = z }
. You can change more than one; each should be separated by commas, for instance, y {x = z, a = b, c = d }
.
Note
Those of you familiar with objectoriented languages might be tempted, after all of this talk about "accessor functions" and "update methods", to think of the y{x=z}
construct as a setter method, which modifies the value of x in a preexisting y. It is not like that – remember that in Haskell variables are immutable. Therefore, using the example above, if you do something like conf2 = changeDir conf1 "/opt/foo/bar"
conf2
will be defined as a Configuration
which is just like conf1
except for having "/opt/foo/bar"
as its currentDir
, but conf1
will remain unchanged.
It's only sugar
You can, of course, continue to pattern match against Configuration
s as you did before. The named fields are simply syntactic sugar; you can still write something like:
getUserName (Configuration un _ _ _ _ _ _ _) = un
But there is no need to do this.
Finally, you can pattern match against named fields as in:
getHostData (Configuration { localHost = lh, remoteHost = rh }) = (lh, rh)
This matches the variable lh
against the localHost
field in the Configuration
and the variable rh
against the remoteHost
field. These matches will succeed, of course. You could also constrain the matches by putting values instead of variable names in these positions, as you would for standard datatypes.
If you are using GHC, then, with the language extension NamedFieldPuns
, it is also possible to use this form:
getHostData (Configuration { localHost, remoteHost }) = (localHost, remoteHost)
It can be mixed with the normal form like this:
getHostData (Configuration { localHost, remoteHost = rh }) = (localHost, rh)
(To use this language extension, enter :set XNamedFieldPuns
in the interpreter, or use the {# LANGUAGE NamedFieldPuns #}
pragma at the beginning of a source file, or pass the XNamedFieldPuns
commandline flag to the compiler.)
You can create values of Configuration
in the old way as shown in the first definition below, or in the named field's type, as shown in the second definition:
initCFG = Configuration "nobody" "nowhere" "nowhere" False False "/" "/" 0 initCFG' = Configuration { username = "nobody" , localHost = "nowhere" , remoteHost = "nowhere" , isguest = False , issuperuser = False , currentdir = "/" , homedir = "/" , timeConnected = 0 }
The first way is much shorter, but the second is much clearer.
WARNING: The second style will allow you to write code that omits fields but will still compile, such as:
cfgFoo = Configuration { username = "Foo" } cfgBar = Configuraton { localHost = "Bar", remoteHost = "Baz" } cfgUndef = Configuration {}
Trying to evaluate the unspecified fields will then result in a runtime error!
Parameterized Types
Parameterized types are similar to "generic" or "template" types in other languages. A parameterized type takes one or more type parameters. For example, the Standard Prelude type Maybe
is defined as follows:
data Maybe a = Nothing  Just a
This says that the type Maybe
takes a type parameter a
. You can use this to declare, for example:
lookupBirthday :: [Anniversary] > String > Maybe Anniversary
The lookupBirthday
function takes a list of birthday records and a string and returns a Maybe Anniversary
. The usual interpretation of such a type is that if the name given through the string is found in the list of anniversaries the result will be Just
the corresponding record; otherwise, it will be Nothing
. Maybe
is the simplest and most common way of indicating failure in Haskell. It is also sometimes seen in the types of function arguments, as a way to make them optional (the intent being that passing Nothing
amounts to omitting the argument).
You can parameterize type
and newtype
declarations in exactly the same way. Furthermore you can combine parameterized types in arbitrary ways to construct new types.
More than one type parameter
We can also have more than one type parameter. An example of this is the Either
type:
data Either a b = Left a  Right b
For example:
pairOff :: Int > Either String Int pairOff people  people < 0 = Left "Can't pair off negative number of people."  people > 30 = Left "Too many people for this activity."  even people = Right (people `div` 2)  otherwise = Left "Can't pair off an odd number of people." groupPeople :: Int > String groupPeople people = case pairOff people of Right groups > "We have " ++ show groups ++ " group(s)." Left problem > "Problem! " ++ problem
In this example pairOff
indicates how many groups you would have if you paired off a certain number of people for your activity. It can also let you know if you have too many people for your activity or if somebody will be left out. So pairOff
will return either an Int representing the number of groups you will have, or a String describing the reason why you can't create your groups.
Kind Errors
The flexibility of Haskell parameterized types can lead to errors in type declarations that are somewhat like type errors, except that they occur in the type declarations rather than in the program proper. Errors in these "types of types" are known as "kind" errors. You don't program with kinds: the compiler infers them for itself. But if you get parameterized types wrong then the compiler will report a kind error.
Other data structures
In this chapter, we will work through examples of how use the techniques we have studied thus far can be used to deal with more complex data types. In particular, we will see examples of recursive data structures, which are data types that can contain values of the same type. Recursive data structures play a vital role in many programming techniques, and so even if you are not going to need defining a new one often (as opposed to using the ones available from the libraries) it is important to be aware of what they are and how they can be manipulated. Besides that, following closely the implementations in this chapter is a good exercise for your budding Haskell abilities.
Note
The Haskell library ecosystem provides a wealth of data structures (recursive and otherwise), covering a wide range of practical needs. Beyond lists, there are maps, sets, finite sequences and arrays, among many others. A good place to begin learning about the main ones is the Data structures primer in the Haskell in Practice track. We recommend you to at least skim it once you finish the next few Intermediate Haskell chapters.
Trees
One of the most important types of recursive data structures are trees. There are several different kinds of trees, so we will arbitrarily choose a simple one to use as an example. Here is its definition:
data Tree a = Leaf a  Branch (Tree a) (Tree a)
As you can see, it's parameterized; i.e. we can have trees of Int
s, trees of String
s, trees of Maybe Int
s, trees of (Int, String)
pairs and so forth. What makes this data type special is that Tree
appears in the definition of itself. A Tree a
is either a leaf, containing a value of type a
or a branch, from which hang two other trees of type Tree a
.
Lists as Trees
As we have seen in More about lists and List Processing, we break lists down into two cases: An empty list (denoted by []), and an element of the specified type plus another list (denoted by (x:xs)). That means the definition of the list data type might look like this:
 PseudoHaskell, will not actually work (because lists have special syntax). data [a] = []  (a:[a])
An equivalent definition you can actually play with is:
data List a = Nil  Cons a (List a)
Like trees, lists are also recursive. For lists, the constructor functions are []
and (:)
. They correspond to Leaf
and Branch
in the Tree
definition above. That implies we can use Leaf
and Branch
for pattern matching just as we did with the empty list and the (x:xs)
.
Maps and Folds
We already know about maps and folds for lists. Now, we can write map and fold functions for our new Tree
type. To recap:
data Tree a = Leaf a  Branch (Tree a) (Tree a) deriving (Show) data [a] = []  (:) a [a]  (:) a [a] is the same as (a:[a]) with prefix instead of infix notation.
Note
Deriving is explained later on in the section Class Declarations. For now, understand it as telling Haskell (and by extension your interpreter) how to display a Tree instance.
Map
Let's take a look at the definition of map
for lists:
map :: (a > b) > [a] > [b] map _ [] = [] map f (x:xs) = f x : map f xs
If we were to write treeMap
, what would its type be? Defining the function is easier if you have an idea of what its type should be.
We want treeMap
to work on a Tree
of some type and return another Tree
of some type by applying a function on each element of the tree.
treeMap :: (a > b) > Tree a > Tree b
This is just like the list example.
Now, when talking about a Tree
, each Leaf
only contains a single value, so all we have to do is apply the given function to that value and then return a Leaf
with the altered value:
treeMap :: (a > b) > Tree a > Tree b treeMap f (Leaf x) = Leaf (f x)
This looks a lot like the empty list case with map
. Now, if we have a Branch
, it will include two subtrees; what do we do with those? The listmap
uses a call to itself on the tail of the list, so we also shall do that with the two subtrees. The complete definition of treeMap
is as follows:
treeMap :: (a > b) > Tree a > Tree b treeMap f (Leaf x) = Leaf (f x) treeMap f (Branch left right) = Branch (treeMap f left) (treeMap f right)
We can make this a bit more readable by noting that treeMap f
is itself a function with type Tree a > Tree b
. This gives us the following revised definition:
treeMap :: (a > b) > Tree a > Tree b treeMap f = g where g (Leaf x) = Leaf (f x) g (Branch left right) = Branch (g left) (g right)
If you didn't follow that immediately, try rereading it. This use of pattern matching may seem weird at first, but it is essential to the use of datatypes. Remember that pattern matching happens on constructor functions.
When you're ready, read on for folds over Trees.
Fold
As with map, let's first review the definition of foldr
for lists:
foldr :: (a > b > b) > b > [a] > b foldr f acc [] = acc foldr f acc (x:xs) = f x (foldr f acc xs)
Recall that lists have two constructors:
(:) :: a > [a] > [a]  takes an element and combines it with the rest of the list [] :: [a]  the empty list takes zero arguments
Thus foldr
takes two arguments corresponding to the two constructors:
f :: a > b > b  a function takes two elements and operates on them to return a single result acc :: b  the accumulator defines what happens with the empty list
Let's take a moment to make this clear. If the initial foldr
is given an empty list, then the default accumulator is returned. For functions like (+)
, the initial accumulator will be 0. With a nonempty list, the value returned by each fold is used in the next fold. When the list runs out, we are back at the empty list, so foldr returns whatever is then the accumulator value from the last fold.
Like foldr
for lists, we want treeFold
to transform a tree of some type into a value of some other type; so in place of [a] > b
we will have Tree a > b
. How do we specify the transformation? First note that Tree a
has two constructors (just like lists have two constructors):
Branch :: Tree a > Tree a > Tree a Leaf :: a > Tree a
So treeFold
will have two arguments corresponding to the two constructors:
fbranch :: b > b > b fleaf :: a > b
Putting it all together we get the following type definition:
treeFold :: (b > b > b) > (a > b) > Tree a > b
That is, the first argument, of type (b > b > b)
, is a function specifying how to combine subtrees into a single result; the second argument, of type a > b
, is a function specifying what to do with leaves (which are the end of recursion, just like emptylist for lists); and the third argument, of type Tree a
, is the whole tree we want to fold.
As with treeMap
, we'll avoid repeating the arguments fbranch
and fleaf
by introducing a local function g
:
treeFold :: (b > b > b) > (a > b) > Tree a > b treeFold fbranch fleaf = g where  definition of g goes here
The argument fleaf
tells us what to do with Leaf
subtrees:
g (Leaf x) = fleaf x
The argument fbranch
tells us how to combine the results of "folding" two subtrees:
g (Branch left right) = fbranch (g left) (g right)
Our full definition becomes:
treeFold :: (b > b > b) > (a > b) > Tree a > b treeFold fbranch fleaf = g where g (Leaf x) = fleaf x g (Branch left right) = fbranch (g left) (g right)
For examples of how these work, copy the Tree
data definition and the treeMap
and treeFold
functions to a Haskell file, along with the following example Tree and example functions to fold over.
tree1 :: Tree Integer tree1 = Branch (Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Branch (Leaf 5) (Leaf 6)))) (Branch (Branch (Leaf 7) (Leaf 8)) (Leaf 9)) doubleTree = treeMap (*2)  doubles each value in tree sumTree = treeFold (+) id  sum of the leaf values in tree fringeTree = treeFold (++) (: [])  list of the leaves of tree
Then load it into GHCi and evaluate:
doubleTree tree1 sumTree tree1 fringeTree tree1
Other datatypes
Map and fold functions can be defined for any kind of data type. In order to generalize the strategy applied for lists and trees, in this final section we will work out a map and a fold for a very strange, intentionallycontrived datatype:
data Weird a b = First a  Second b  Third [(a,b)]  Fourth (Weird a b)
It can be a useful exercise to write the functions as you follow the examples, trying to keep the coding one step ahead of your reading.
General Map
The first important difference in working with this Weird
type is that it has two type parameters. For that reason, we will want the map function to take two functions as arguments, one to be applied on the elements of type a and another for the elements of type b. With that accounted for, we can write the type signature of weirdMap
:
weirdMap :: (a > c) > (b > d) > Weird a b > Weird c d
Next step is defining weirdMap
. The key point is that maps preserve the structure of a datatype, so the function must evaluate to a Weird
which uses the same constructor as the one used for the original Weird
. For that reason, we need one definition to handle each constructor, and these constructors are used as patterns for writing them. As before, to avoid repeating the weirdMap
argument list over and over again a where clause comes in handy. A sketch of the function is below:
weirdMap :: (a > c) > (b > d) > Weird a b > Weird c d weirdMap fa fb = g where g (First x) = More to follow g (Second y) = More to follow g (Third z) = More to follow g (Fourth w) = More to follow
The first two cases are fairly straightforward, as there is just a single element of a
or b
type inside the Weird
.
weirdMap :: (a > c) > (b > d) > Weird a b > Weird c d weirdMap fa fb = g where g (First x) = First (fa x) g (Second y) = Second (fb y) g (Third z) = More to follow g (Fourth w) = More to follow
Third
is trickier because it contains a list whose elements are themselves data structures (the tuples). So we need to navigate the nested data structures, apply fa
and fb
on all elements of type a
and b
and eventually (as a map must preserve structure) produce a list of tuples – [(c,d)]
– to be used with the constructor. The simplest approach might seem to be just breaking down the list inside the Weird
and playing with the patterns:
g (Third []) = Third [] g (Third ((x,y):zs)) = Third ( (fa x, fb y) : ( (\(Third z) > z) (g (Third zs)) ) )
This appears to be written as a typical recursive function for lists. We start by applying the functions of interest to the first element in order to obtain the head of the new list, (fa x, fb y)
. But what will we cons it to? As g
requires a Weird
argument, we need to make a Weird
using the list tail in order to make the recursive call. But then g
will give a Weird
and not a list, so we have to retrieve the modified list from that – that's the role of the lambda function. Finally, there is also the empty list base case to be defined as well.
After all of that, we are left with a messy function. Every recursive call of g
requires wrapping zs
into a Weird
, while what we really wanted to do was to build a list with (fa x, fb y)
and the modified xs
. The problem with this solution is that g
can (thanks to pattern matching) act directly on the list head but (due to its type signature) can't be called directly on the list tail. For that reason, it would be better to apply fa
and fb
without breaking down the list with pattern matching (as far as g
is directly concerned, at least). But there was a way to directly modify a list elementbyelement...
g (Third z) = Third ( map (\(x, y) > (fa x, fb y) ) z)
...our good old map
function, which modifies all tuples in the list z
using a lambda function. In fact, the first attempt at writing the definition looked just like an application of the list map except for the spurious Weird
packing and unpacking. We got rid of these by having the pattern splitting of z
done by map
, which works directly with regular lists. You could find it useful to expand the map definition inside g
to see the difference more clearerly. Finally, you may prefer to write this new version in an alternative and clean way using list comprehension syntax:
g (Third z) = Third [ (fa x, fb y)  (x,y) < z ]
Adding the Third
function, we only have the Fourth
left to define:
weirdMap :: (a > c) > (b > d) > Weird a b > Weird c d weirdMap fa fb = g where g (First x) = First (fa x) g (Second y) = Second (fb y) g (Third z) = Third ( map (\(x, y) > (fa x, fb y) ) z) g (Fourth w) = More to follow
All we need to do is apply g
recursively:
weirdMap :: (a > c) > (b > d) > Weird a b > Weird c d weirdMap fa fb = g where g (First x) = First (fa x) g (Second y) = Second (fb y) g (Third z) = Third ( map (\(x, y) > (fa x, fb y) ) z) g (Fourth w) = Fourth (g w)
General Fold
While we were able to define a map by specifying as arguments a function for every separate type, this isn't enough for a fold. For a fold, we'll need a function for every constructor function. With lists, the constructors are []
and (:)
. The acc
argument in the foldr
function corresponds to the []
constructor. The f
argument in the foldr
function corresponds to the (:)
constructor. The Weird
datatype has four constructors, so we need four functions – one for handling the internal structure of the datatype specified by each constructor. Next, we have an argument of the Weird a b
type, and finally we want the whole fold function to evaluate to a value of some other, arbitrary, type. Additionally, each individual function we pass to weirdFold
must evaluate to the same type weirdFold
does. That allows us to make a mock type signature and sketch the definition:
weirdFold :: (something1 > c) > (something2 > c) > (something3 > c) > (something4 > c) > Weird a b > c weirdFold f1 f2 f3 f4 = g where g (First x) = Something of type c here g (Second y) = Something of type c here g (Third z) = Something of type c here g (Fourth w) = Something of type c here
Now, we need to figure out to which types something1
, something2
, something3
and something4
correspond to. That is done by analyzing the constructors, since the functions must take as arguments the elements of the datatype (whose types are specified by the constructor type signature). Again, the types and definitions of the first two functions are easy enough. The third one isn't too difficult either because, for the purposes of folding the list of (a,b)
, tuples are no different from a simple type (unlike in the map example, the internal structure does not concern us now). The fourth constructor, however, is recursive, and we have to be careful. As with weirdMap
, we also need to recursively call the g
function. This brings us to the final definition:
weirdFold :: (a > c) > (b > c) > ([(a,b)] > c) > (c > c) > Weird a b > c weirdFold f1 f2 f3 f4 = g where g (First x) = f1 x g (Second y) = f2 y g (Third z) = f3 z g (Fourth w) = f4 (g w)
Note
If you were expecting very complex expressions in the weirdFold
above and are surprised by the immediacy of the solution, it might be helpful to have a look on what the common foldr
would look like if we wrote it in this style and didn't have the special squarebracket syntax of lists to distract us:
 List a is [a], Cons is (:) and Nil is [] data List a = Cons a (List a)  Nil listFoldr :: (a > b > b) > (b) > List a > b listFoldr fCons fNil = g where g (Cons x xs) = fCons x (g xs) g Nil = fNil
Now it is easier to see the parallels. The extra complications are that Cons
(that is, (:)
) takes two arguments (and, for that reason, so does fCons
) and is recursive, requiring a call to g
. Also, fNil
is of course not really a function, as it takes no arguments.
Folds on recursive datatypes
As far as folds are concerned, Weird
was a fairly nice datatype to deal with. Just one recursive constructor, which isn't even nested inside other structures. What would happen if we added a truly complicated fifth constructor?
Fifth [Weird a b] a (Weird a a, Maybe (Weird a b))
This is a valid and yet tricky question. In general, the following rules apply:
 A function to be supplied to a fold has the same number of arguments as the corresponding constructor.
 The type of the arguments of such a function match the types of the constructor arguments, except if the constructor is recursive (that is, takes an argument of its own type).
 If a constructor is recursive, any recursive argument of the constructor will correspond to an argument of the type the fold evaluates to.^{[1]}
 If a constructor is recursive, the complete fold function should be (recursively) applied to the recursive constructor arguments.
 If a recursive element appears inside another data structure, the appropriate map function for that data structure should be used to apply the fold function to it.
So f5
would have the type:
f5 :: [c] > a > (Weird a a, Maybe c) > c
as the type of Fifth
is:
Fifth :: [Weird a b] > a > (Weird a a, Maybe (Weird a b)) > Weird a b
The definition of g
for the Fifth
constructor will be:
g (Fifth list x (waa, mc)) = f5 (map g list) x (waa, maybeMap g mc) where maybeMap f Nothing = Nothing maybeMap f (Just w) = Just (f w)
Note that nothing strange happens with the Weird a a
part. No g
gets called. What's up? This is recursion, right? Well, not really. Weird a a
and Weird a b
are different types, so it isn't a real recursion. It isn't guaranteed that, for example, f2
will work with something of type 'a', where it expects a type 'b'. It can be true for some cases but is not reliable for every case.
Also look at the definition of maybeMap
. Verify that it is indeed a map function as:
 It preserves structure.
 Only types are changed.
A nice sounding word
The folds we have defined here are examples of catamorphisms. A catamorphism is a general way to collapse a data structure into a single value. There is deep theory associated with catamorphisms and related recursion schemes; however, we won't go through any of it now, as our main goal here was exercising the mechanics of data structure manipulation in Haskell with believable examples.
Notes
 ↑ This sort of recursiveness, in which the function used for folding can take the result of another fold as an argument, is what confers the folds of data structures such as lists and trees their "accumulating" functionality.
Classes and types
Back in Type basics II we had a brief encounter with type classes as the mechanism used with number types. As we hinted back then, however, classes have many other uses.
Broadly speaking, the point of type classes is to ensure that certain operations will be available for values of chosen types. For example, if we know a type belongs to (or, to use the jargon, instantiates) the class Fractional
, then we are guaranteed to, among other things, be able to perform real division with its values.^{[1]}
Classes and instances
Up to now we have seen how existing type classes appear in signatures such as:
(==) :: (Eq a) => a > a > Bool
Now it is time to switch perspectives. First, we quote the definition of the Eq
class from Prelude:
class Eq a where (==), (/=) :: a > a > Bool  Minimal complete definition:  (==) or (/=) x /= y = not (x == y) x == y = not (x /= y)
The definition states that if a type a
is to be made an instance of the class Eq
it must support the functions (==)
and (/=)
 the class methods  both of them having type a > a > Bool
. Additionally, the class provides default definitions for (==)
and (/=)
in terms of each other. As a consequence, there is no need for a type in Eq
to provide both definitions  given one of them, the other will be generated automatically.
With a class defined, we proceed to make existing types instances of it. Here is an arbitrary example of an algebraic data type made into an instance of Eq
by an instance declaration:
data Foo = Foo {x :: Integer, str :: String} instance Eq Foo where (Foo x1 str1) == (Foo x2 str2) = (x1 == x2) && (str1 == str2)
And now we can apply (==)
and (/=)
to Foo
values in the usual way:
*Main> Foo 3 "orange" == Foo 6 "apple" False *Main> Foo 3 "orange" /= Foo 6 "apple" True
A few important remarks:
 The class
Eq
is defined in the Standard Prelude. This code sample defines the typeFoo
and then declares it to be an instance ofEq
. The three definitions (class, data type, and instance) are completely separate and there is no rule about how they are grouped. This works both ways: you could just as easily create a new classBar
and then declare the type Integer to be an instance of it.
 Classes are not types, but categories of types; and so the instances of a class are types instead of values.^{[2]}
 The definition of
(==)
forFoo
relies on the fact that the values of its fields (namelyInteger
andString
) are also members ofEq
. In fact, almost all types in Haskell are members of Eq (the most notable exception being functions).
 Type synonyms defined with type keyword cannot be made instances of a class.
Deriving
Since equality tests between values are commonplace, in all likelihood most of the data types you create in any real program should be members of Eq. A lot of them will also be members of other Prelude classes such as Ord and Show. To avoid large amounts of boilerplate for every new type, Haskell has a convenient way to declare the "obvious" instance definitions using the keyword deriving. So, Foo would be written as:
data Foo = Foo {x :: Integer, str :: String} deriving (Eq, Ord, Show)
This makes Foo an instance of Eq with an automatically generated definition of == exactly equivalent to the one we just wrote, and also makes it an instance of Ord and Show for good measure.
You can only use deriving with a limited set of builtin classes, which are described very briefly below:
 Eq
 Equality operators == and /=
 Ord
 Comparison operators < <= > >=; min, max, and compare.
 Enum
 For enumerations only. Allows the use of list syntax such as [Blue .. Green].
 Bounded
 Also for enumerations, but can also be used on types that have only one constructor. Provides minBound and maxBound as the lowest and highest values that the type can take.
 Show
 Defines the function show, which converts a value into a string, and other related functions.
 Read
 Defines the function read, which parses a string into a value of the type, and other related functions.
The precise rules for deriving the relevant functions are given in the language report. However, they can generally be relied upon to be the "right thing" for most cases. The types of elements inside the data type must also be instances of the class you are deriving.
This provision of special "magic" function synthesis for a limited set of predefined classes goes against the general Haskell philosophy that "built in things are not special", but it does save a lot of typing. Besides that, deriving instances stops us from writing them in the wrong way (an example: an instance of Eq
such that x == y
would not be equal to y == x
would be flat out wrong). ^{[3]}
Class inheritance
Classes can inherit from other classes. For example, here is the main part of the definition of Ord in Prelude:
class (Eq a) => Ord a where compare :: a > a > Ordering (<), (<=), (>=), (>) :: a > a > Bool max, min :: a > a > a
The actual definition is rather longer and includes default implementations for most of the functions. The point here is that Ord inherits from Eq. This is indicated by the => notation in the first line, which mirrors the way classes appear in type signatures. Here, it means that for a type to be an instance of Ord it must also be an instance of Eq, and hence needs to implement the == and /= operations.^{[4]}
A class can inherit from several other classes: just put all the ancestor classes in the parentheses before the =>. Let us illustrate that with yet another Prelude quote:
class (Num a, Ord a) => Real a where   the rational equivalent of its real argument with full precision toRational :: a > Rational
Standard classes
This diagram, copied from the Haskell Report, shows the relationships between the classes and types in the Standard Prelude. The names in bold are the classes, while the nonbold text stands for the types that are instances of each class ((>) refers to functions and [], to lists). The arrows linking classes indicate the inheritance relationships, pointing to the inheriting class.
Type constraints
With all pieces in place, we can go full circle by returning to the very first example involving classes in this book:
(+) :: (Num a) => a > a > a
(Num a) =>
is a type constraint, which restricts the type a
to instances of the class Num
. In fact, (+)
is a method of Num
, along with quite a few other functions (notably, (*)
and ()
; but not (/)
).
You can put several limits into a type signature like this:
foo :: (Num a, Show a, Show b) => a > a > b > String foo x y t = show x ++ " plus " ++ show y ++ " is " ++ show (x+y) ++ ". " ++ show t
Here, the arguments x and y must be of the same type, and that type must be an instance of both Num and Show. Furthermore, the final argument t must be of some (possibly different) type that is also an instance of Show. This example also displays clearly how constraints propagate from the functions used in a definition (in this case, (+)
and show
) to the function being defined.
Other uses
Beyond simple type signatures, type constraints can be introduced in a number of other places:
instance
declarations (typical with parametrized types);
class
declarations (constraints can be introduced in the method signatures in the usual way for any type variable other than the one defining the class^{[5]});
data
declarations,^{[6]} where they act as constraints for the constructor signatures.
Note
Type constraints in data
declarations are less useful than it might seem at first. Consider:
data (Num a) => Foo a = F1 a  F2 a String
Here, Foo is a type with two constructors, both taking an argument of a type a
which must be in Num
. However, the (Num a) =>
constraint is only effective for the F1 and F2 constructors, and not for other functions involving Foo
. Therefore, in the following example...
fooSquared :: (Num a) => Foo a > Foo a fooSquared (F1 x) = F1 (x * x) fooSquared (F2 x s) = F2 (x * x) s
... even though the constructors ensure a
will be some type in Num
we can't avoid duplicating the constraint in the signature of fooSquared
.^{[7]}
A concerted example
To provide a better view of the interplay between types, classes, and constraints, we will present a very simple and somewhat contrived example. We will define a Located
class, a Movable
class which inherits from it, and a function with a Movable
constraint implemented using the methods of the parent class, i.e. Located
.
 Location, in two dimensions. class Located a where getLocation :: a > (Int, Int) class (Located a) => Movable a where setLocation :: (Int, Int) > a > a  An example type, with accompanying instances. data NamedPoint = NamedPoint { pointName :: String , pointX :: Int , pointY :: Int } deriving (Show) instance Located NamedPoint where getLocation p = (pointX p, pointY p) instance Movable NamedPoint where setLocation (x, y) p = p { pointX = x, pointY = y }  Moves a value of a Movable type by the specified displacement.  This works for any movable, including NamedPoint. move :: (Movable a) => (Int, Int) > a > a move (dx, dy) p = setLocation (x + dx, y + dy) p where (x, y) = getLocation p
A word of advice
Do not read too much into the Movable
example just above; it is merely a demonstration of classrelated language features. It would be a mistake to think that every single functionality which might be conceivably generalized, such as setLocation
, needs a type class of its own. In particular, if all your Located
instances should be able to be moved as well then Movable
is unnecessary  and if there is just one instance there is no need for type classes at all! Classes are best used when there are several types instantiating it (or if you expect others to write additional instances) and you do not want users to know or care about the differences between the types. An extreme example would be Show
: generalpurpose functionality implemented by an immense number of types, about which you do not need to know a thing about before calling show
. In the following chapters, we will explore a number of important type classes in the libraries; they provide good examples of the sort of functionality which fits comfortably into a class.
Notes
 ↑ To programmers coming from objectoriented languages: A class in Haskell in all likelihood is not what you expect  don't let the terms confuse you. While some of the uses of type classes resemble what is done with abstract classes or Java interfaces, there are fundamental differences which will become clear as we advance.
 ↑ This is a key difference from most OO languages, where a class is also itself a type.
 ↑ There are ways to make the magic apply to other classes. GHC extensions allow
deriving
for a few other common classes for which there is only one correct way of writing the instances, and the GHC generics machinery make it possible to generate instances automatically for custom classes.  ↑ If you check the full definition in the Prelude specification, the reason for that becomes clear: the default implementations involve applying
(==)
to the values being compared.  ↑ Constraints for the type defining the class should be set via class inheritance.
 ↑ And
newtype
declarations as well, but nottype
.  ↑ Extra note for the curious: This issue is related to some of the problems tackled by the advanced features discussed in the "Fun with types" chapter of the Advanced Track.
The Functor class
In this chapter, we will introduce the important Functor
type class.
Motivation
In Other data structures, we saw operations that apply to all elements of some grouped value. The prime example is map
which works on lists. Another example we worked through was the following Tree datatype:
data Tree a = Leaf a  Branch (Tree a) (Tree a) deriving (Show)
The map function we wrote for Tree was:
treeMap :: (a > b) > Tree a > Tree b treeMap f (Leaf x) = Leaf (f x) treeMap f (Branch left right) = Branch (treeMap f left) (treeMap f right)
As discussed before, we can conceivably define a mapstyle function for any arbitrary data structure.
When we first introduced map
in More about lists, we went through the process of taking a very specific function for list elements and generalizing to show how map
combines any appropriate function with all sorts of lists. Now, we will generalize still further. Instead of mapforlists and mapfortrees and other distinct maps, how about a general concept of maps for all sorts of mappable types?
Introducing Functor
Functor
is a Prelude class for types which can be mapped over. It has a single method, called fmap
. The class is defined as follows:
class Functor f where fmap :: (a > b) > f a > f b
The usage of the type variable f
can look a little strange at first. Here, f
is a parametrized data type; in the signature of fmap
, f
takes a
as a type parameter in one of its appearances and b
in the other. Let's consider an instance of Functor
: <By replacing f
with Maybe
we get the following signature for fmap
...
fmap :: (a > b) > Maybe a > Maybe b
... which fits the natural definition:
instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x)
(Incidentally, this definition is in Prelude; so, we didn't really need to have implemented maybeMap
for that example in the "Other data structures" chapter.)
The Functor
instance for lists (also in Prelude) is simple:
instance Functor [] where fmap = map
... and if we replace f
with []
in the fmap
signature, we get the familiar type of map
.
So, fmap
is a generalization of map
for any parametrized data type.^{[1]}
Naturally, we can provide Functor
instances for our own data types. In particular, treeMap
can be promptly relocated to an instance:
instance Functor Tree where fmap f (Leaf x) = Leaf (f x) fmap f (Branch left right) = Branch (fmap f left) (fmap f right)
Here's a quick demo of fmap
in action with the instances above (to reproduce it, you only need to load the data
and instance
declarations for Tree
; the others are already in Prelude):
*Main> fmap (2*) [1,2,3,4] [2,4,6,8] *Main> fmap (2*) (Just 1) Just 2 *Main> fmap (fmap (2*)) [Just 1, Just 2, Just 3, Nothing] [Just 2, Just 4, Just 6, Nothing] *Main> fmap (2*) (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))) Branch (Branch (Leaf 2) (Leaf 4)) (Branch (Leaf 6) (Leaf 8))
Note
Beyond the []
and Maybe
examples mentioned here, Prelude provides a number of other handy Functor
instances. The full list can be found in GHC's documentation for the Control.Monad module.
The functor laws
When providing a new instance of Functor
, you should ensure it satisfies the two functor laws. There is nothing mysterious about these laws; their role is to guarantee fmap
behaves sanely and actually performs a mapping operation (as opposed to some other nonsense).^{[2]} The first law is:
fmap id == id
id
is the identity function, which returns its argument unaltered. The first law states that mapping id
over a functor must return the functor unchanged.
Next, the second law:
fmap (f . g) == fmap f . fmap g
It states that it should not matter whether we map a composed function or first map one function and then the other (assuming the application order remains the same in both cases).
What did we gain?
At this point, we can ask what benefit we get from the extra layer of generalization brought by the Functor
class. There are two significant advantages:
 The availability of the
fmap
method relieves us from having to recall, read, and write a plethora of differently named mapping methods (maybeMap
,treeMap
,weirdMap
, ad infinitum). As a consequence, code becomes both cleaner and easier to understand. On spotting a use offmap
, we instantly have a general idea of what is going on.^{[3]}
 Using the type class system, we can write
fmap
based algorithms which work out of the box with any functor  be it[]
,Maybe
,Tree
or whichever you need. Indeed, a number of useful classes in the core libraries inherit fromFunctor
.^{[4]}.
Type classes make it possible to create general solutions to whole categories of problems. Depending on what you use Haskell for, you may not need to define new classes often, but you will certainly be using type classes all the time. Many of the most powerful features and sophisticated capabilities of Haskell rely on type classes (residing either in the standard libraries or elsewhere). From this point on, classes will be a prominent presence in our studies.
Notes
 ↑ Data structures provide the most intuitive examples; however, there are functors which cannot reasonably be seen as data structures. A commonplace metaphor consists in thinking of functors as containers; like all metaphors, however, it can be stretched only so far.
 ↑ The functor laws, and indeed the concept of a functor, are grounded on a branch of Mathematics called Category Theory which should not be a concern for you at this point. We will have opportunities to explore related topics in the Advanced Track of this book.
 ↑ This is analogous to the gain in clarity provided by replacing explicit recursive algorithms on lists with implementations based on higherorder functions.
 ↑ Note for the curious: For one example, have a peek at Applicative Functors in the Advanced Track (for the moment you can ignore the references to monads there).
Monads
Understanding monads
Monads are very useful in Haskell, but the concept is often difficult at first. Since they have so many applications, people often explain them from a particular point of view, and that can confuse your understanding of monads in their full glory.
Historically, monads were introduced into Haskell to perform input/output. A predetermined execution order is crucial for things like reading and writing files, and monadic operations follow an inherent sequence. We discussed sequencing and IO back in Simple input and output using the do
notation. Well, do
is actually just syntactic sugar over monads.
Monads are by no means limited to input and output. Monads support a whole range of things like exceptions, state, nondeterminism, continuations, coroutines, and more. In fact, thanks to the versatility of monads, none of these constructs needed to be built into Haskell as a language; instead, they are defined by the standard libraries.
Definition
A monad is defined by three things:
 a type constructor
m
;  a function
return
;^{[1]}  an operator
(>>=)
which is pronounced "bind".
The function and operator are methods of the Monad
type class and have types
return :: a > m a (>>=) :: m a > (a > m b) > m b
and are required to obey three laws that will be explained later on.
For a concrete example, take the Maybe
monad. The type constructor is m = Maybe
, while return
and (>>=)
are defined like this:
return :: a > Maybe a return x = Just x (>>=) :: Maybe a > (a > Maybe b) > Maybe b m >>= g = case m of Nothing > Nothing Just x > g x
Maybe
is the monad, and return
brings a value into it by wrapping it with Just
. As for (>>=)
, it takes a m :: Maybe a
value and a g :: a > Maybe b
function. If m
is Nothing
, there is nothing to do and the result is Nothing
. Otherwise, in the Just x
case, g
is applied to x
, the underlying value wrapped in Just
, to give a Maybe b
result, which might be Nothing
, depending on what g
does to x
. To sum it all up, if there is an underlying value in m
, we apply g
to it, which brings the underlying value back into the Maybe
monad.
The key first step to understand how return
and (>>=)
work is tracking which values and arguments are monadic and which ones aren't. As in so many other cases, type signatures are our guide to the process.
Motivation: Maybe
To see the usefulness of (>>=)
and the Maybe
monad, consider the following example: Imagine a family database that provides two functions
father :: Person > Maybe Person mother :: Person > Maybe Person
These look up the name of someone's father or mother. In case our database is missing some information, Maybe
allows us to return a Nothing
value instead of crashing the program.
Let's combine our functions to query various grandparents. For instance, the following function looks up the maternal grandfather:
maternalGrandfather :: Person > Maybe Person maternalGrandfather p = case mother p of Nothing > Nothing Just mom > father mom
Or consider a function that checks whether both grandfathers are in the database:
bothGrandfathers :: Person > Maybe (Person, Person) bothGrandfathers p = case father p of Nothing > Nothing Just dad > case father dad of Nothing > Nothing Just gf1 >  found first grandfather case mother p of Nothing > Nothing Just mom > case father mom of Nothing > Nothing Just gf2 >  found second grandfather Just (gf1, gf2)
What a mouthful! Every single query might fail by returning Nothing
and the whole function must fail with Nothing
if that happens.
Clearly there has to be a better way to write that instead of repeating the case of Nothing
again and again! Indeed, that's what the Maybe
monad is set out to do. For instance, the function retrieving the maternal grandfather has exactly the same structure as the (>>=)
operator, so we can rewrite it as:
maternalGrandfather p = mother p >>= father
With the help of lambda expressions and return
, we can rewrite the two grandfathers function as well:
bothGrandfathers p = father p >>= (\dad > father dad >>= (\gf1 > mother p >>=  this line works as "\_ > mother p", but naming gf1 allows later return (\mom > father mom >>= (\gf2 > return (gf1,gf2) ))))
While these nested lambda expressions may look confusing to you, the thing to take away here is that (>>=)
releases us from listing all the Nothing
s, shifting the focus back to the interesting part of the code.
To be a little more precise: The result of father p
is a monadic value (in this case, either Just dad
or Nothing
, depending on whether p
's dad is in the database). As the father
function takes a regular (nonmonadic value), the >>=
feeds p
's dad
to it as a nonmonadic value. The result of father dad
is then monadic again, and the process continues.
So, >>=
helps us pass nonmonadic values to functions without leaving a monad. In the case of the Maybe
monad, the monadic aspect is the qualifier that we don't know with certainty whether the value will be found.
Type class
In Haskell, the Monad
type class is used to implement monads. It is provided by the Control.Monad module and included in the Prelude. The class has the following methods:
class Monad m where return :: a > m a (>>=) :: m a > (a > m b) > m b (>>) :: m a > m b > m b fail :: String > m a
Aside from return and bind, notice the two additional functions (>>)
and fail
.
The operator (>>)
called "then" is a mere convenience and commonly implemented as
m >> n = m >>= \_ > n
>>
sequences two monadic actions when the second action does not involve the result of the first, which is common for monads like IO
.
printSomethingTwice :: String > IO () printSomethingTwice str = putStrLn str >> putStrLn str
The function fail
handles pattern match failures in do
notation. It's an unfortunate technical necessity and doesn't really have anything to do with monads. You are advised to not call fail
directly in your code.
Notions of Computation
We've seen how (>>=)
and return
are very handy for removing boilerplate code that crops up when using Maybe
. That, however, is not enough to justify why monads matter so much. We will continue our monad studies by rewriting the twograndfathers function using do
notation with explicit braces and semicolons. Depending on your experience with other programming languages, you may find this very suggestive:
bothGrandfathers p = do { dad < father p; gf1 < father dad; mom < mother p; gf2 < father mom; return (gf1, gf2); }
If this looks like a code snippet of an imperative programming language to you, that's because it is. In particular, this imperative language supports exceptions : father
and mother
are functions that might fail to produce results, i.e. raise an exception, and when that happens, the whole do
block will fail, i.e. terminate with an exception.
In other words, the expression father p
, which has type Maybe Person
, is interpreted as a statement of an imperative language that returns a Person
as result. This is true for all monads: a value of type M a
is interpreted as a statement of an imperative language that returns a value of type a
as result; and the semantics of this language are determined by the monad M
.^{[2]}
Under this interpretation, the bind operator (>>=)
is simply a function version of the semicolon. Just like a let
expression can be written as a function application,
let x = foo in x + 3 corresponds to (\x > x + 3) foo
an assignment and semicolon can be written as the bind operator:
x < foo; return (x + 3) corresponds to foo >>= (\x > return (x + 3))
The return
function lifts a value a
to M a
, a fullfledged statement of the imperative language corresponding to the monad M
.
Different semantics of the imperative language correspond to different monads. The following table shows the classic selection that every Haskell programmer should know. If the idea behind monads is still unclear to you, studying each of the examples in the following chapters will not only give you a wellrounded toolbox but also help you understand the common abstraction behind them.
Monad  Imperative Semantics  Wikibook chapter 

Maybe 
Exception (anonymous)  Haskell/Understanding monads/Maybe 
Error 
Exception (with error description)  Haskell/Understanding monads/Error 
State 
Global state  Haskell/Understanding monads/State 
IO 
Input/Output  Haskell/Understanding monads/IO 
[] (lists) 
Nondeterminism  Haskell/Understanding monads/List 
Reader 
Environment  Haskell/Understanding monads/Reader 
Writer 
Logger  Haskell/Understanding monads/Writer 
Furthermore, these different semantics need not occur in isolation. As we will see in a few chapters, it is possible to mix and match them by using monad transformers to combine the semantics of multiple monads in a single monad.
Monad Laws
In Haskell, every instance of the Monad
type class (and thus all implementations of (>>=)
and return
) must obey the following three laws:
m >>= return = m  right unit return x >>= f = f x  left unit (m >>= f) >>= g = m >>= (\x > f x >>= g)  associativity
Return as neutral element
The behavior of return
is specified by the left and right unit laws. They state that return
doesn't perform any computation, it just collects values. For instance,
maternalGrandfather p = do mom < mother p gf < father mom return gf
is exactly the same as
maternalGrandfather p = do mom < mother p father mom
by virtue of the right unit law.
Associativity of bind
The law of associativity makes sure that (like the semicolon) the bind operator (>>=)
only cares about the order of computations, not about their nesting; e.g. we could have written bothGrandfathers
like this (compare with our earliest version without do
):
bothGrandfathers p = (father p >>= father) >>= (\gf1 > (mother p >>= father) >>= (\gf2 > return (gf1,gf2) ))
The associativity of the then operator (>>)
is a special case:
(m >> n) >> o = m >> (n >> o)
Monadic composition
It is easier to picture the associativity of bind by recasting the law as
(f >=> g) >=> h = f >=> (g >=> h)
where (>=>)
is the monad composition operator, a close analogue of the function composition operator (.)
, only with flipped arguments. It is defined as:
(>=>) :: Monad m => (a > m b) > (b > m c) > a > m c f >=> g = \x > f x >>= g
We can also flip monad composition to go the other direction using (<=<)
. The operation order of (f . g)
is the same as (f' <=< g')
.^{[3]}
Monads and Category Theory
Monads originally come from a branch of mathematics called Category Theory. Fortunately, it is entirely unnecessary to understand category theory in order to understand and use monads in Haskell. The definition of monads in Category Theory actually uses a slightly different presentation. Translated into Haskell, this presentation gives an alternative yet equivalent definition of a monad which can give us some additional insight.^{[4]}
So far, we have defined monads in terms of (>>=)
and return
. The alternative definition, instead, starts with monads as functors with two additional combinators:
fmap :: (a > b) > M a > M b  functor return :: a > M a join :: M (M a) > M a
(Reminder: as discussed in the chapter on the functor class, a functor M
can be thought of as container, so that M a
"contains" values of type a
, with a corresponding mapping function, i.e. fmap
, that allows functions to be applied to values inside it.)
Under this interpretation, the functions behave as follows:
fmap
applies a given function to every element in a containerreturn
packages an element into a container,join
takes a container of containers and flattens it into a single container.
With these functions, the bind combinator can be defined as follows:
m >>= g = join (fmap g m)
Likewise, we could give a definition of fmap
and join
in terms of (>>=)
and return
:
fmap f x = x >>= (return . f) join x = x >>= id
Is my Monad a Functor?
At this point we might, with good reason, deduce that all monads are by definition functors as well. While according to category theory that is indeed the case, GHC does it differently because of historic accident in the designing of Haskell. While the Monad
and Functor
classes aren't connected in current versions, GHC 7.10 will finally fix this issue so that every Monad
instance will be connected to a matching Functor
instance and the corresponding fmap
. Meanwhile, Control.Monad
defines liftM
, a function with a strangely familiar type signature...
liftM :: (Monad m) => (a1 > r) > m a1 > m r
As you might suspect, liftM
is merely fmap
implemented with (>>=)
and return
, just as we have done above. For a properly implemented monad with a matching Functor
(that is, any sensible monad) liftM
and fmap
are interchangeable.
Notes
 ↑ This
return
function has nothing to do with thereturn
keyword found in imperative languages like C or Java; don't conflate these two.  ↑ By "semantics", we mean what the language allows you to say. In the case of
Maybe
, the semantics allow us to express failure, as statements may fail to produce a result, leading to the statements that follow it being skipped.  ↑ Of course, the functions in regular function composition are nonmonadic functions whereas monadic composition takes only monadic functions.
 ↑ Deep into the Advanced Track, we will cover the theoretical side of the story in the chapter on Category Theory.
The Maybe monad
We introduced monads using Maybe
as an example. The Maybe
monad represents computations which might "go wrong" by not returning a value. For reference, here are our definitions of return
and (>>=)
for Maybe
as we saw in the last chapter:^{[1]}
return :: a > Maybe a return x = Just x (>>=) :: Maybe a > (a > Maybe b) > Maybe b (>>=) m g = case m of Nothing > Nothing Just x > g x
Safe functions
The Maybe
datatype provides a way to make a safety wrapper around functions which can fail to work for a range of arguments. For example, head
and tail
only work with nonempty lists. Another typical case, which we will explore in this section, are mathematical functions like sqrt
and log
; (as far as real numbers are concerned) these are only defined for nonnegative arguments.
> log 1000 6.907755278982137 > log (1000) ''ERROR''  runtime error
To avoid this crash, a "safe" implementation of log could be:
safeLog :: (Floating a, Ord a) => a > Maybe a safeLog x  x > 0 = Just (log x)  otherwise = Nothing
> safeLog 1000 Just 6.907755278982137 > safeLog 1000 Nothing
We could write similar "safe functions" for all functions with limited domains such as division, squareroot, and inverse trigonometric functions (safeDiv
, safeSqrt
, safeArcSin
, etc. all of which would have the same type as safeLog
but definitions specific to their constraints)
If we wanted to combine these monadic functions, the cleanest approach is with monadic composition (which was mentioned briefly near the end of the last chapter) and pointfree style:
safeLogSqrt = safeLog <=< safeSqrt
Written in this way, safeLogSqrt
resembles a lot its unsafe, nonmonadic counterpart:
unsafeLogSqrt = log . sqrt
Lookup tables
A lookup table relates keys to values. You look up a value by knowing its key and using the lookup table. For example, you might have a phone book application with a lookup table where contact names are keys to corresponding phone numbers. An elementary way of implementing lookup tables in Haskell is to use a list of pairs: [(a, b)]
. Here a
is the type of the keys, and b
the type of the values.^{[2]} Here's how the phone book lookup table might look like:
phonebook :: [(String, String)] phonebook = [ ("Bob", "01788 665242"), ("Fred", "01624 556442"), ("Alice", "01889 985333"), ("Jane", "01732 187565") ]
The most common thing you might do with a lookup table is look up values. Everything is fine if we try to look up "Bob", "Fred", "Alice" or "Jane" in our phone book, but what if we were to look up "Zoe"? Zoe isn't in our phone book, so the lookup would fail. Hence, the Haskell function to look up a value from the table is a Maybe
computation (it is available from Prelude):
lookup :: Eq a => a  a key > [(a, b)]  the lookup table to use > Maybe b  the result of the lookup
Let us explore some of the results from lookup:
Prelude> lookup "Bob" phonebook Just "01788 665242" Prelude> lookup "Jane" phonebook Just "01732 187565" Prelude> lookup "Zoe" phonebook Nothing
Now let's expand this into using the full power of the monadic interface. Say, we're now working for the government, and once we have a phone number from our contact, we want to look up this phone number in a big, governmentsized lookup table to find out the registration number of their car. This, of course, will be another Maybe
computation. But if the person we're looking for isn't in our phone book; we certainly won't be able to look up their registration number in the governmental database. What we need is a function that will take the results from the first computation and put it into the second lookup only if we get a successful value in the first lookup. Of course, our final result should be Nothing
if we get Nothing
from the either of the lookups.
getRegistrationNumber :: String  their name > Maybe String  their registration number getRegistrationNumber name = lookup name phonebook >>= (\number > lookup number governmentDatabase)
If we then wanted to use the result from the governmental database lookup in a third lookup (say we want to look up their registration number to see if they owe any car tax), then we could extend our getRegistrationNumber
function:
getTaxOwed :: String  their name > Maybe Double  the amount of tax they owe getTaxOwed name = lookup name phonebook >>= (\number > lookup number governmentDatabase) >>= (\registration > lookup registration taxDatabase)
Or, using the do
block style:
getTaxOwed name = do number < lookup name phonebook registration < lookup number governmentDatabase lookup registration taxDatabase
Let's just pause here and think about what would happen if we got a Nothing
anywhere. By definition, when the first argument to >>=
is Nothing
, it just returns Nothing
while ignoring whatever function it is given. Thus, a Nothing
at any stage in the large computation will result in a Nothing
overall, regardless of the other functions. After the first Nothing
hits, all >>=
s will just pass it to each other, skipping the other function arguments. The technical description says that the structure of the Maybe
monad propagates failures.
Open monads
Another trait of the Maybe
monad is that it is "open": if we have a Just
value, we can see the contents and extract the associated values through pattern matching.
zeroAsDefault :: Maybe Int > Int zeroAsDefault mx = case mx of Nothing > 0 Just x > x
This usage pattern of replacing Nothing
with a default is captured by the fromMaybe
function in Data.Maybe
.
zeroAsDefault :: Maybe Int > Int zeroAsDefault mx = fromMaybe 0 mx
The maybe
Prelude function allows us to do it in a more general way, by supplying a function to modify the extracted value.
displayResult :: Maybe Int > String displayResult mx = maybe "There was no result" (("The result was " ++) . show) mx
Prelude> :t maybe maybe :: b > (a > b) > Maybe a > b Prelude> displayResult (Just 10) "The result was 10" Prelude> displayResult Nothing "There was no result"
This possibility makes sense for Maybe
, as it allows us to recover from failures. Not all monads are open in this way; often, they are designed to hide unnecessary details. return
and (>>=)
alone do not allow us to extract the underlying value from a monadic computation, and so it is perfectly possible to make a "noexit" monad, from which it is never possible to extract values. The most obvious example of that is the IO
monad.
Maybe and safety
We have seen how Maybe
can make code safer by providing a graceful way to deal with failure that does not involve runtime errors. Does that mean we should always use Maybe
for everything? Not really.
When you write a function, you are able to tell whether it might fail to produce a result during normal operation of the program,^{[3]} either because the functions you use might fail (as in the examples in this chapter) or because you know some of the argument or intermediate result values do not make sense (for instance, imagine a calculation that is only meaningful if its argument is less than 10). If that is the case, by all means use Maybe
to signal failure; it is far better than returning an arbitrary default value or throwing an error.
Now, adding Maybe
to a result type without a reason would only make the code more confusing and no safer. The type signature of a function with unnecessary Maybe would tell users of the code that the function could fail when it actually can't. Of course, that is not as bad a lie as the opposite one (that is, claiming that a function will not fail when it actually can), but we really want honest code in all cases. Furthermore, using Maybe
forces us to propagate failure (with fmap
or monadic code) and eventually handle the failure cases (using pattern matching, the maybe
function, or fromMaybe
from Data.Maybe
). If the function cannot actually fail, coding for failure is an unnecessary complication.
Notes
 ↑ The definitions in the actual instance in
Data.Maybe
are written a little differently, but are fully equivalent to these.  ↑ Check the chapter about maps in Haskell in Practice for a different, and potentially more useful, implementation.
 ↑ With "normal operation" we mean to exclude failure caused by uncontrollable circumstances in the real world, such as memory exhaustion or a dog chewing the printer cable.
The List monad
Lists are a fundamental part of Haskell, and we've used them extensively before getting to this chapter. The novel insight is that the list type is a monad too!
As monads, lists are used to model nondeterministic computations which may return an arbitrary number of results. There is a certain parallel with how Maybe
represented computations which could return zero or one value; but with lists, we can return zero, one, or many values (the number of values being reflected in the length of the list).
List instantiated as monad
The return
function for lists simply injects a value into a list:
return x = [x]
In other words, return
here makes a list containing one element, namely the single argument it took. The type of the list return is return :: a > [a]
, or, equivalently, return :: a > [] a
. The latter style of writing it makes it more obvious that we are replacing the generic type constructor in the signature of return
(which we had called M
in Understanding monads) by the list type constructor []
(which is distinct from but easy to confuse with the empty list!).
The binding operator is less trivial. We will begin by considering its type, which for the case of lists should be:
[a] > (a > [b]) > [b]
This is just what we'd expect: it pulls out the value from the list to give to a function that returns a new list.
The actual process here involves first map
ping a given function over a given list to get back a list of lists, i.e. type [[b]]
(of course, many functions which you might use in mapping do not return lists; but, as shown in the type signature above, monadic binding for lists only works with functions that return lists). To get back to a regular list, we then concatenate the elements of our list of lists to get a final result of type [b]
. Thus, we can define the list version of (>>=)
:
xs >>= f = concat (map f xs)
The bind operator is key to understanding how different monads do their jobs, and its definition indicates the chaining strategy for working with the monad.
For the list monad, nondeterminism is present because different functions may return any number of different results when mapped over lists.
Bunny invasion
It is easy to incorporate the familiar list processing functions in monadic code. Consider this example: rabbits raise an average of six kits in each litter, half of which will be female. Starting with a single mother, we can model the number of female kits in each successive generation (i.e. the number of new kits after the rabbits grow up and have their own litters):
Prelude> let generation = replicate 3 Prelude> ["bunny"] >>= generation ["bunny","bunny","bunny"] Prelude> ["bunny"] >>= generation >>= generation ["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]
In this silly example all elements are equal, but the same overall logic could be used to model radioactive decay, or chemical reactions, or any phenomena that produces a series of elements starting from a single one.
Board game example
Suppose we are modeling a turnbased board game and want to find all the possible ways the game could progress. We would need a function to calculate the list of options for the next turn, given a current board state:
nextConfigs :: Board > [Board] nextConfigs bd = undefined  details not important
To figure out all the possibilities after two turns, we would again apply our function to each of the elements of our new list of board states. Our function takes a single board state and returns a list of possible new states. Thus, we can use monadic binding to map the function over each element from the list:
nextConfigs bd >>= nextConfigs
In the same fashion, we could to bind the result back to the function yet again (ad infinitum) to generate the next turn's possibilities. Depending on the particular game's rules, we may reach board states that have no possible nextturns; in those cases, our function will return the empty list.^{[1]}
On a side note, we could translate several turns into a do
block (like we did for the grandparents example in Understanding monads):
threeTurns :: Board > [Board] threeTurns bd = do bd1 < nextConfigs bd  bd1 refers to a board configuration after 1 turn bd2 < nextConfigs bd1 nextConfigs bd2
If the above looks too magical, keep in mind that do
notation is syntactic sugar for (>>=)
operations. To the right of each leftarrow, there is a function with arguments that evaluate to a list; the variable to the left of the arrow stands for the list elements. After a leftarrow assignment line, there can be later lines that call the assigned variable as an argument for a function. This later function will be performed for each of the elements from within the list that came from the leftarrow line's function. This perelement process corresponds to the `map` in the definition of (>>=)
. A resulting list of lists (one per element of the original list) will be flattened into a single list (the `concat` in the definition of (>>=)
).
List comprehensions
The list monad works in a way that has uncanny similarity to list comprehensions. Let's slightly modify the do
block we just wrote for threeTurns
so that it ends with a return
...
threeTurns bd = do bd1 < nextConfigs bd bd2 < nextConfigs bd1 bd3 < nextConfigs bd2 return bd3
This mirrors exactly the following list comprehension:
threeTurns bd = [ bd3  bd1 < nextConfigs bd, bd2 < nextConfigs bd1, bd3 < nextConfigs bd2 ]
(In a list comprehension, it is perfectly legal to use the elements drawn from one list to define the following ones, like we did here.)
The resemblance is no coincidence: list comprehensions are, behind the scenes, defined in terms of concatMap
and concatMap f xs = concat (map f xs))
. That's just the list monad binding definition again! To summarize the nature of the list monad: binding for the list monad is a combination of concatenation and mapping, and so the combined function concatMap
is effectively the same as >>=
for lists (except for different syntactic order).
For the correspondence between list monad and list comprehension to be complete, we need a way to reproduce the filtering that list comprehensions can do. We will explain how that can be achieved a little later in the Additive monads chapter.
do
Notation
Using do
blocks as an alternative monad syntax was first introduced way back in the Simple input and output chapter. There, we used do
to sequence input/output operations, but we hadn't introduced monads yet. Now, we can see that IO
is yet another monad.
Since the following examples all involve IO
, we will refer to the computations/monadic values as actions (as we did in the earlier parts of the book). Of course, do
works with any monad; there is nothing specific about IO
in how it works.
Translating the then operator
The (>>)
(then) operator works almost identically in do
notation and in unsugared code. For example, suppose we have a chain of actions like the following one:
putStr "Hello" >> putStr " " >> putStr "world!" >> putStr "\n"
We can rewrite that in do
notation as follows:
do putStr "Hello" putStr " " putStr "world!" putStr "\n"
This sequence of instructions nearly matches that in any imperative language. In Haskell, we can chain any actions as long as all of them are in the same monad. In the context of the IO
monad, the actions include writing to a file, opening a network connection, or asking the user for input.
Here's the stepbystep translation of do
notation to unsugared Haskell code:
do action1
action2
action3
becomes
action1 >> do action2 action3
and so on, until the do
block is empty.
Translating the bind operator
The (>>=)
is a bit more difficult to translate from and to do
notation. (>>=)
passes a value, namely the result of an action or function, downstream in the binding sequence. do
notation assigns a variable name to the passed value using the <
.
do x1 < action1 x2 < action2 action3 x1 x2
x1
and x2
are the results of action1
and action2
. If, for instance, action1
is an IO Integer
then x1
will be bound to an Integer
). The stored values are passed as arguments to action3
, which returns a third action. The do
block is broadly equivalent to the following vanilla Haskell snippet:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
The second argument of (>>=)
is a function specifying what to do with the result of the action passed as first argument. Thus, chains of lambdas pass the results downstream. Remember that, without extra parentheses, a lambda extends all the way to the end of the expression. x1
is still in scope at the point we call action3
. We can rewrite the chain of lambdas more legibly by using separate lines and indentation:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
That shows the scope of each lambda function clearly. To group things more like the do
notation, we could show it like this:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
These presentation differences are only a matter of assisting readability.^{[2]}
The fail method
Above, we said the snippet with lambdas was "broadly equivalent" to the do
block. The translation is not exact because the do
notation adds special handling of pattern match failures. When placed at the left of either <
or >
, x1
and x2
are patterns being matched. Therefore, if action1
returned a Maybe Integer
we could write a do
block like this...
do Just x1 < action1 x2 < action2 action3 x1 x2
...and x1
be an Integer
. In such a case, what happens if action1
returns Nothing
? Ordinarily, the program would crash with an nonexhaustive patterns error, just like the one we get when calling head
on an empty list. With do
notation, however, failures are handled with the fail
method for the relevant monad. The do
block above translates to:
action1 >>= f where f (Just x1) = do x2 < action2 action3 x1 x2 f _ = fail "..."  A compilergenerated message.
What fail
actually does depends on the monad instance. Though it will often rethrow the pattern matching error, monads that incorporate some sort of error handling may deal with the failure in their own specific ways. For instance, Maybe
has fail _ = Nothing
; analogously, for the list monad fail _ = []
.^{[3]}
The fail
method is an artifact of do
notation. Rather than calling fail
directly, you should rely on automatic handling of pattern match failures whenever you are sure that fail
will do something sensible for the monad you are using.
Example: userinteractive program
Note
We are going to interact with the user, so we will use putStr
and getLine
alternately. To avoid unexpected results in the output, we must disable output buffering when importing System.IO
. To do this, put hSetBuffering stdout NoBuffering
at the top of your code. To handle this otherwise, you would explicitly flush the output buffer before each interaction with the user (namely a getLine
) using hFlush stdout
. If you are testing this code with ghci, you don't have such problems.
Consider this simple program that asks the user for their first and last names:
nameDo :: IO () nameDo = do putStr "What is your first name? " first < getLine putStr "And your last name? " last < getLine let full = first ++ " " ++ last putStrLn ("Pleased to meet you, " ++ full ++ "!")
A possible translation into vanilla monadic code:
nameLambda :: IO () nameLambda = putStr "What is your first name? " >> getLine >>= \ first > putStr "And your last name? " >> getLine >>= \ last > let full = first ++ " " ++ last in putStrLn ("Pleased to meet you, " ++ full ++ "!")
In cases like this, where we just want to chain several actions, the imperative style of do
notation feels natural and convenient. In comparison, monadic code with explicit binds and lambdas is something of an acquired taste.
Notice that example above includes a let
statement in the do
block. The desugared version is simply a regular let
expression where the in
part is whatever follows from the do
syntax.
Returning values
The last statement in do
notation is the overall result of the do
block. In the previous example, the result was of the type IO ()
, i.e. an empty value in the IO
monad.
Suppose that we want to rewrite the example but return an IO String
with the acquired name. All we need to do is add a return
:
nameReturn :: IO String nameReturn = do putStr "What is your first name? " first < getLine putStr "And your last name? " last < getLine let full = first ++ " " ++ last putStrLn ("Pleased to meet you, " ++ full ++ "!") return full
This example will "return" the full name as a string inside the IO
monad, which can then be utilized downstream elsewhere:
greetAndSeeYou :: IO () greetAndSeeYou = do name < nameReturn putStrLn ("See you, " ++ name ++ "!")
Here, nameReturn
will be run and the returned result (called "full" in the nameReturn
function) will be assigned to the variable "name" in our new function. The greeting part of nameReturn
will be printed to the screen because that is part of the calculation process. Then, the additional "see you" message will print as well, and the final returned value is back to being IO ()
.
If you know imperative languages like C, you might think return
in Haskell matches return
elsewhere. A small variation on the example will dispel that impression:
nameReturnAndCarryOn = do putStr "What is your first name? " first < getLine putStr "And your last name? " last < getLine let full = first++" "++last putStrLn ("Pleased to meet you, "++full++"!") return full putStrLn "I am not finished yet!"
The string in the extra line will be printed out because return
is not a final statement interrupting the flow (as it would be in C and other languages). Indeed, the type of nameReturnAndCarryOn
is IO ()
, — the type of the final putStrLn
action. After the function is called, the IO String
created by the return full
will disappear without a trace.
Just sugar
As a syntactical convenience, do
notation does not add anything essential, but it is often preferable for clarity and style. However, do
is never used for a single action. The Haskell "Hello world" is simply:
main = putStrLn "Hello world!"
Snippets like this one are totally redundant:
fooRedundant = do x < bar return x
Thanks to the monad laws, we can and should write simply:
foo = bar
A subtle but crucial point relates to function composition: As we already know, the greetAndSeeYou
action in the section just above could be rewritten as:
greetAndSeeYou :: IO () greetAndSeeYou = nameReturn >>= \ name > putStrLn ("See you, " ++ name ++ "!")
While you might find the lambda a little unsightly, suppose we had a printSeeYou
function defined elsewhere:
printSeeYou :: String > IO () printSeeYou name = putStrLn ("See you, " ++ name ++ "!")
Now, we can have a clean function definition with neither lambdas or do
:
greetAndSeeYou :: IO () greetAndSeeYou = nameReturn >>= printSeeYou
Or, if we had a nonmonadic seeYou
function:
seeYou :: String > String seeYou name = "See you, " ++ name ++ "!"
Then we can write:
 Reminder: liftM f m == m >>= return . f == fmap f m greetAndSeeYou :: IO () greetAndSeeYou = liftM seeYou nameReturn >>= putStrLn
Keep this last example with liftM
in mind; we will soon return to using nonmonadic functions in monadic code, and liftM
will be useful there.
Notes
 ↑ As an optional advanced exercise: research how we could do recursive binding to find all possible results for games that have a finite number of possibilities. Furthermore, consider how we might handle the empty list results when they are reached and still retain the list of possible final actual board states.
 ↑ Actually, the indentation isn't needed in this case. This is equally valid:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
Of course, we could use even more indentation if we wanted. Here's an extreme example:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
While that indention is certainly overkill, it could be worse:
action1 >>= \ x1 > action2 >>= \ x2 > action3 x1 x2
That is valid Haskell but is baffling to read; so please don't ever write like that. Write your code with consistent and meaningful groupings.
 ↑ This explains why, as we pointed out in the "Pattern matching" chapter, pattern matching failures in list comprehensions are silently ignored.
The IO monad
Haskell is a functional and lazy language. However, the real world effects of input/output operations can't be expressed through pure functions. Furthermore, in most cases I/O can't be done lazily. Since lazy computations are only performed when their values become necessary, unfettered lazy I/O would make the order of execution of the real world effects unpredictable. Haskell addresses these issues through the IO
monad.
Input/output and purity
Haskell functions are pure: when given the same arguments, they return the same results. Pure functions are reliable and predictable; they ease debugging and validation. Test cases can also be set up easily since we can be sure that nothing other than the arguments will influence a function's result. Being entirely contained within the program, the Haskell compiler can evaluate functions thoroughly in order to optimize the compiled code.
So, how do we manage actions like opening a network connection, writing a file, reading input from the outside world, or anything else that does something more than returning a calculated result? Well, the key is: these actions are not functions. The IO
monad is a means to represent actions as Haskell values, so that we can manipulate them with pure functions.
Combining functions and I/O actions
Let's combine functions with I/O to create a full program that will:
 Ask the user to insert a string
 Read their string
 Use
liftM
to apply a functionshout
that capitalizes all the letters from the string  Write the resulting string
module Main where import Data.Char (toUpper) import Control.Monad main = putStrLn "Write your string: " >> liftM shout getLine >>= putStrLn shout = map toUpper
We have a fullblown program, but we didn't include any type definitions. Which parts are functions and which are IO actions or other values? We can load our program in ghci and check the types:
main :: IO () putStrLn :: String > IO () "Write your string: " :: [Char] (>>) :: Monad m => m a > m b > m b liftM :: Monad m => (a1 > r) > m a1 > m r shout :: [Char] > [Char] getLine :: IO String (>>=) :: Monad m => m a > (a > m b) > m b
Whew, that a lot of information there. We've seen all of this before, but let's review.
main
is IO ()
. That's not a function. Functions are of types a > b
. Our entire program is an IO action.
putStrLn
is a function, but it results in an IO action. The "Write your string: " text is a String
(remember, that's just a synonym for [Char]
). It is used as an argument for putStrLn
and is incorporated into the IO action that results. So, putStrLn
is a function, but putStrLn x
evaluates to an IO action. The ()
part of the IO type indicates that nothing is available to be passed on to any later functions or actions.
That last part is key. We sometimes say informally that an IO action "returns" something; however, taking that too literally leads to confusion. It is clear what we mean when we talk about functions returning results, but IO actions are not functions. Let's skip down to getLine
— an IO action that does provide a value. getLine
is not a function that returns a String
because getLine
isn't a function. Rather, getLine
is an IO action which, when evaluated, will materialize a String
, which can then be passed to later functions through, for instance, fmap
/liftM
and (>>=)
.
When we use getLine
to get a String
, the value is monadic because it is wrapped in IO
functor. We cannot pass the value directly to a function that takes plain (nonmonadic, or nonfunctorial) values. liftM
does the work of taking a nonmonadic function while passing in and returning monadic values.
As we've seen already, (>>=)
does the work of passing a monadic value into a function that takes a nonmonadic value and returns a monadic value. It may seem inefficient for liftM
to take the nonmonadic result of its given function and return a monadic value only for (>>=)
to then pass the underlying nonmonadic value to the next function. It is precisely this sort of chaining, however, that creates the reliable sequencing that make monads so effective at integrating pure functions with IO actions.
do notation review
Given the emphasis on sequencing, the do
notation can be especially appealing with the IO
monad. Our program
putStrLn "Write your string: " >> liftM shout getLine >>= putStrLn
could be written as:
do putStrLn "Write your string: " string < getLine putStrLn (shout string)
The universe as part of our program
One way of viewing the IO
monad is to consider IO a
as a computation which provides a value of type a
while changing the state of the world by doing input and output. Obviously, you cannot literally set the state of the world; it is hidden from you, as the IO
functor is abstract (that is, you cannot dig into it to see the underlying values; it is closed in a way opposite to that in which Maybe
can be said to be open). Seen this way, IO
is roughly analogous to the State
monad, which we will meet shortly. With State
, however, the state being changed is made of normal Haskell values, and so we can manipulate it directly with pure functions.
Understand that this idea of the universe as an object affected and affecting Haskell values through IO
is only a metaphor; a loose interpretation at best. The more mundane fact is that IO
simply brings some very baselevel operations into the Haskell language.^{[1]} Remember that Haskell is an abstraction, and that Haskell programs must be compiled to machine code in order to actually run. The actual workings of IO happen at a lower level of abstraction, and are wired into the very definition of the Haskell language.^{[2]}
Pure and impure
Consider the following snippet:
speakTo :: (String > String) > IO String speakTo fSentence = liftM fSentence getLine  Usage example. sayHello :: IO String sayHello = speakTo (\name > "Hello, " ++ name ++ "!")
In most other programming languages, which do not have separate types for I/O actions, speakTo
would have a type akin to:
speakTo :: (String > String) > String
With such a type, however, speakTo
would not be a function at all! Functions produce the same results when given the same arguments; the String
delivered by speakTo
, however, also depends on whatever is typed at the terminal prompt. In Haskell, we avoid that pitfall by returning an IO String
, which is not a String
but a promise that some String
will be delivered by carrying out certain instructions involving I/O (in this case, the I/O consists of getting a line of input from the terminal). Though the String
can be different each time speakTo
is evaluated, the I/O instructions are always the same.
When we say Haskell is a purely functional language, we mean that all of its functions are really functions, which is not the case in most other languages. To be precise, Haskell expressions are always referentially transparent; that is, you can always replace an expression (such as speakTo
) with its value (in this case, \fSentence > liftM fSentence getLine
) without changing the behaviour of the program. The String
delivered by getLine
, in contrast, is opaque; its value is not specified and can't be discovered in advance by the program. If speakTo
had the problematic type we mentioned above, sayHello
would be a String
; however, replacing it by any specific string would break the program.
In spite of Haskell being purely functional, IO
actions can be said to be impure because their impact on the outside world are side effects (as opposed to the regular effects that are entirely contained within Haskell). Programming languages that lack purity may have sideeffects in many other places connected with various calculations. Purely functional languages, however, assure that even expressions with impure values are referentially transparent. That means we can talk about, reason about and handle impurity in a purely functional way, using purely functional machinery such as functors and monads. While IO
actions are impure, all of the Haskell functions that manipulate them remain pure.
Functional purity, coupled to the fact that I/O shows up in types, benefit Haskell programmers in various ways. The guarantees about referential transparency increase a lot the potential for compiler optimizations. IO
values being distinguishable through types alone make it possible to immediately tell where we are engaging with side effects or opaque values. As IO
itself is just another functor, we maintain to the fullest extent the predictability and ease of reasoning associated with pure functions.
Functional and imperative
When we introduced monads, we said that a monadic expression can be interpreted as a statement of an imperative language. That interpretation is immediately compelling for IO
, as the language around IO actions looks a lot like a conventional imperative language. It must be clear, however, that we are talking about an interpretation. We are not saying that monads or do
notation turn Haskell into an imperative language. The point is merely that you can view and understand monadic code in terms of imperative statements. The semantics may be imperative, but the implementation of monads and (>>=)
is still purely functional. To make this distinction clear, let's look at a little illustration:
int x; scanf("%d", &x); printf("%d\n", x);
This is a snippet of C, a typical imperative language. In it, we declare a variable x
, read its value from user input with scanf
and then print it with printf
. We can, within an IO
do block, write a Haskell snippet that performs the same function and looks quite similar:
x < readLn print x
Semantically, the snippets are nearly equivalent.^{[3]} In the C code, however, the statements directly correspond to instructions to be carried out by the program. The Haskell snippet, on the other hand, is desugared to:
readLn >>= \x > print x
The desugared version has no statements, only functions being applied. We tell the program the order of the operations indirectly as a simple consequence of data dependencies: when we chain monadic computations with (>>=)
, we get the later results by applying functions to the results of the earlier ones. It just happens that, for instance, evaluating print x
leads to a string to be printed in the terminal.
When using monads, Haskell allows us to write code with imperative semantics while keeping the advantages of functional programming.
I/O in the libraries
So far the only I/O primitives we have used were putStrLn
and getLine
and small variations thereof. The standard libraries, however, offer many other useful functions and actions involving IO
. We present some of the most important ones in the IO chapter in Haskell in Practice, including the basic functionality needed for reading from and writing to files.
Monadic control structures
Given that monads allow us to express sequential execution of actions in a wholly general way, could we use them to implement common iterative patterns, such as loops? In this section, we will present a few of the functions from the standard libraries which allow us to do precisely that. While the examples are presented here applied to IO
, keep in mind that the following ideas apply to every monad.
Remember, there is nothing magical about monadic values; we can manipulate them just like any other values in Haskell. Knowing that, we might think to try the following function to get five lines of user input:
fiveGetLines = replicate 5 getLine
That won't do, however (try it in GHCi!). The problem is that replicate
produces, in this case, a list of actions, while we want an action which returns a list (that is, IO [String]
rather than [IO String]
). What we need is a fold to run down the list of actions, executing them and combining the results into a single list. As it happens, there is a Prelude function which does that: sequence
.
sequence :: (Monad m) => [m a] > m [a]
And so, we get the desired action with:
fiveGetLines = sequence $ replicate 5 getLine
replicate
and sequence
form an appealing combination; so Control.Monad offers a replicateM
function for repeating an action an arbitrary number of times. Control.Monad
provides a number of other convenience functions in the same spirit  monadic zips, folds, and so forth.
fiveGetLinesAlt = replicateM 5 getLine
A particularly important combination is map
and sequence
. Together, they allow us to make actions from a list of values, run them sequentially, and collect the results. mapM
, a Prelude function, captures this pattern:
mapM :: (Monad m) => (a > m b) > [a] > m [b]
We also have variants of the above functions with a trailing underscore in the name, such as sequence_
, mapM_
and replicateM_
. These discard any final values and so are appropriate when you are only interested in performing actions. Compared with their underscoreless counterparts, these functions are like the distinction between (>>)
and (>>=)
. mapM_
for instance has the following type:
mapM_ :: (Monad m) => (a > m b) > [a] > m ()
Finally, it is worth mentioning that Control.Monad
also provides forM
and forM_
, which are flipped versions of mapM
and mapM_
. forM_
happens to be the idiomatic Haskell counterpart to the imperative foreach loop; and the type signature suggests that neatly:
forM_ :: (Monad m) => [a] > (a > m b) > m ()
Exercises 


Notes
 ↑ The technical term is "primitive", as in primitive operations.
 ↑ The same can be said about all higherlevel programming languages, of course. Incidentally, Haskell's IO operations can actually be extended via the Foreign Function Interface (FFI) which can make calls to C libraries. As C can use inline assembly code, Haskell has can indirectly engage with anything a computer can do. Still, Haskell functions manipulate such outside operations only indirectly as values in
IO
functors.  ↑ One difference is that
x
is a mutable variable in C, and so it is possible to declare it in one statement and set its value in the next; Haskell never allows such mutability. If we wanted to imitate the C code even more closely, we could have used anIORef
, which is a cell that contains a value which can be destructively updated. For obvious reasons,IORef
s can only be used within theIO
monad.
The State monad
If you have programmed in any other language before, you likely wrote some functions that "kept state". For those new to the concept, a state is one or more variables that are required to perform some computation but are not among the arguments of the relevant function. Objectoriented languages, like C++, suggest extensive use of state variables within objects in the form of member variables. Programs written in procedural languages, like C, typically use variables declared outside the current scope to keep track of state.
In Haskell, however, such techniques cannot be applied in a straightforward way; they require mutable variables, and that clashes with Haskell's functional purity. We can usually keep track of state by passing parameters from function to function or by pattern matching of various sorts, but in some cases it is appropriate to find a more general or convenient solution. We will consider the common example of how the State
monad can assist us in generating pseudorandom numbers.
PseudoRandom Numbers
Generating actual random numbers is a very complicated subject. Computer programming almost always sticks to pseudorandom numbers. They are called "pseudo" because they are not truly random. Starting from an initial state (commonly called the seed), pseudorandom number generators produce a sequence of numbers that have the appearance of being random.
Every time a pseudorandom number is requested, a global state is updated.^{[1]} Sequences of pseudorandom numbers can be replicated exactly if the initial seed and the algorithm is known.
Implementation in Haskell
Producing a pseudorandom number in most programming languages is very simple: there is usually a function, such as C or C++'s rand()
, that provides a pseudorandom value (or a truly random one, depending on the implementation). Haskell has a similar one in the System.Random
module:
> :m System.Random > :t randomIO randomIO :: Random a => IO a > randomIO 1557093684
This function references a mutable state that is held outside Haskell and interacted with via IO
, so values obtained using randomIO
will be different every time.
Example: Rolling Dice
Suppose we are coding a game in which at some point we need an element of chance. In reallife games that is often obtained by means of dice. So, let's create a dicethrowing function in Haskell.
We'll use the function randomR
to specify an interval from which the pseudorandom values will be taken; in the case of a die, it is randomR (1,6)
. To make sure we get new values each time we roll, we'll use the IO
version of randomR
:
import Control.Monad import System.Random rollDiceIO :: IO (Int, Int) rollDiceIO = liftM2 (,) (randomRIO (1,6)) (randomRIO (1,6))
That function rolls two dice. Here, liftM2
is used to make the nonmonadic twoargument function (,)
work within a monad. The (,)
is the noninfix version of the tuple constructor. Thus, the two die rolls will be returned (in IO
) as a tuple.
Exercises 


Getting Rid of the IO
Monad
A disadvantage of randomIO
is that it requires us to utilize the IO
monad and store our state outside the program where we can't control what happens to it. We would prefer to only use IO when we really have a good reason to interact with the outside world.
To avoid the IO Monad, we can build a local generator. From the System.Random
module, we can use the random
and mkStdGen
functions to generate tuples containing a pseudorandom number together with a new generator to use the next time the function is called.
> :m System.Random > let generator = mkStdGen 0  "0" is our seed > generator 1 1 > random generator :: (Int, StdGen) (2092838931,1601120196 1655838864)
Now, we've avoided the IO Monad, but there are new problems. First and foremost, if we want to use generator
to get random numbers, the obvious definition...
> let randInt = fst . random $ generator :: Int > randInt 2092838931
...is useless; it will always give back the same value, 2092838931
, every time (because the same generator is always used). To solve this, we can take the second member of the tuple (i.e. the new generator) and feed it to a new call to random
:
> let (randInt, generator') = random generator :: (Int, StdGen) > randInt  Same value 2092838931 > random generator' :: (Int, StdGen)  Using new generator' returned from “random generator” (2143208520,439883729 1872071452)
Of course, this is clumsy and tedious. We need to keep creating new functions for new calls, and we're stuck with the fuss of having to carefully pass the generator around.
Dice without IO
We can redo our dice throw with our new approach:
> randomR (1,6) (mkStdGen 0) (6, 40014 40692)
This tuple combines the result of throwing a single die with a new generator number. A simple implementation for throwing two dice is then:
clumsyRollDice :: (Int, Int) clumsyRollDice = (n, m) where (n, g) = randomR (1,6) (mkStdGen 0) (m, _) = randomR (1,6) g
Exercises 


The implementation of clumsyRollDice
works as a oneoff, but we have to manually write the passing of generator g
from one where
clause to the other. This approach will become increasingly cumbersome if we want to produce larger sets of pseudorandom numbers. It is also errorprone: what if we pass one of the middle generators to the wrong line in the where
clause?
What we really need is a way to automate the extraction of the second member of the tuple (i.e. the new generator) and feed it to a new call to random
. This is where the State
monad comes into the picture.
Introducing State
Note
In this chapter we will use the state monad provided by the module Control.Monad.Trans.State
of the transformers
package. By reading Haskell code in the wild, you will soon meet Control.Monad.State
, a module of the closely related mtl
package. The differences between these two modules need not concern us at the moment; everything we discuss here also applies to the mtl
variant.
The Haskell type State
describes functions that consume a state and produce a tuple that contains a result along with the new state after the result has been extracted.
The state function is wrapped by a data type definition which comes along with a runState
accessor so that pattern matching becomes unnecessary. For our current purposes, consider the definition equivalent to:^{[2]}
newtype State s a = State { runState :: s > (a, s) }
Here, s
is the type of the state, and a
the type of the produced result. Calling our type State
is arguably a bit of a misnomer because the wrapped value is not the state itself but a state processor.
newtype
Notice that we defined the data type with the newtype
keyword, rather than the usual data
. newtype
can be used only for types with just one constructor and just one field. It ensures that the trivial wrapping and unwrapping of the single field is eliminated by the compiler. For that reason, simple wrapper types such as State
are usually defined with newtype
. Would defining a synonym with type
be enough in such cases? Not really, because type
does not allow us to define instances for the new data type, which is what we are about to do...
Instantiating the Monad
In contrast to the monads we have met thus far, State
has two type parameters. To define a Monad, we need to combine State
with a second parameter.
instance Monad (State s) where
So, there are many different State
monads including State String
, State Int
, State SomeLargeDataStructure
, and so on…
The return
function is implemented as:
return :: a > State s a return x = State ( \ st > (x, st) )
In words, giving a value to return
produces a function wrapped in the State
constructor. The function takes a state value, and returns it unchanged as the second member of a tuple, together with the specified result value.
Binding is a bit intricate:
(>>=) :: State s a > (a > State s b) > State s b processor >>= processorGenerator = State $ \ st > let (x, st') = runState processor st in runState (processorGenerator x) st'
(>>=)
is given a state processor and a function that can generate another processor using the result of the first one. The two processors are combined to obtain a function that takes the initial state, and returns the second result and state (i.e. after the second function has processed them).
The diagram shows this schematically, for a slightly different, but equivalent form of the ">>=" (bind) function, given below (where wpA and wpAB are wrapped versions of pA and pAB).
 pAB = s1 > pA > (v2,s2) > pB > (v3,s3) wpA >>= f = wpAB where wpAB = State $ \s1 > let pA = runState wpA (v2, s2) = pA s1 pB = runState $ f v2 (v3,s3) = pB s2 in (v3,s3)
Setting and Accessing the State
The monad instantiation allows us to manipulate various state processors, but you may at this point wonder where exactly the original state comes from in the first place. State s
is also an instance of the MonadState
class, which provides two additional functions:
put newState = State $ \_ > ((), newState)
Given a state, this function will generate a state processor. The processor's input will be disregarded, and the output will be a tuple carrying the state we provided. Since we do not care about the result (we are discarding the input, after all), the first element of the tuple will be "null".^{[3]}
The specular operation reads the state. This is accomplished by get
:
get = State $ \st > (st, st)
The resulting state processor produces the input st
in both positions of the output tuple (i.e. both as a result and as a state) so that it may be bound to other processors.
Getting Values and State
From the definition of State
, we know that runState
is an accessor to apply to a State a b
value to get the stateprocessing function. That function, given an initial state, will return the extracted value and the new state.
Other similar functions are evalState
and execState
. Given a State a b
and an initial state, the function evalState
will return the extracted value only, whereas execState
will return only the new state.
evalState :: State s a > s > a evalState processor st = fst ( runState processor st ) execState :: State s a > s > s execState processor st = snd ( runState processor st )
Dice and state
Let's use the State monad for our dice throw examples.
To avoid the confusion with "State" and "state processor", we'll use a type synonym:
import Control.Monad.Trans.State import System.Random type GeneratorState = State StdGen
So, GeneratorState Int
is in essence a StdGen > (Int, StdGen)
function and is a processor of the generator state. The generator state itself is produced by the mkStdGen
function. Note that GeneratorState
does not specify what type of values we are going to extract, only the type of the state.
We can now produce a function that, given a StdGen
generator, outputs a number between 1 and 6.
rollDie :: GeneratorState Int rollDie = do generator < get let (value, newGenerator) = randomR (1,6) generator put newGenerator return value
Let's go through each of the steps:
 First, we take out the pseudorandom generator with
<
in conjunction withget
.get
overwrites the monadic value (The 'a' in 'm a') with the state, binding the generator to the state. (If in doubt, recall the definition ofget
and>>=
above).  Then, we use the
randomR
function to produce an integer between 1 and 6 using the generator we took; we also store the new generator graciously returned byrandomR
.  We then set the state to be the
newGenerator
using theput
function, so that the next call will use a different pseudorandom generator;  Finally, we inject the result into the
GeneratorState
monad usingreturn
.
We can finally use our monadic die:
> evalState rollDie (mkStdGen 0) 6
Why have we involved monads and built such an intricate framework only to do exactly what fst $ randomR (1,6)
already does? Well, consider the following function:
rollDice :: GeneratorState (Int, Int) rollDice = liftM2 (,) rollDie rollDie
We obtain a function producing two pseudorandom numbers in a tuple. Note that these are in general different:
> evalState rollDice (mkStdGen 666) (6,1)
Under the hood, the monads are passing state to each other. It was previously very clunky using randomR (1,6)
because we had to pass state manually. Now, the monad is taking care of that for us. Assuming we know how to use the lifting functions, constructing intricate combinations of pseudorandom numbers (tuples, lists, whatever) has suddenly become much easier.
Exercises 


Pseudorandom values of different types
Until now, we considered only Int
as the type of the produced pseudorandom number. However, already when we defined the GeneratorState
monad, we saw that it did not specify anything about the type of the returned value. In fact, there is one implicit assumption: that we can produce values of such a type with a call to random
.
The Random
class (capitalized) includes default implementations for functions generating Int
, Char
, Integer
, Bool
, Double
and Float
, so you can immediately generate any of those.
Because GeneratorState
is "agnostic" in regard to the type of the pseudorandom value it produces, we can write a similarly "agnostic" function (analogous to rollDie
) that provides a pseudorandom value of unspecified type (as long as it is an instance of Random
):
getRandom :: Random a => GeneratorState a getRandom = do generator < get let (value, newGenerator) = random generator put newGenerator return value
Compared to rollDie
, this function does not specify the Int
type in its signature and uses random
instead of randomR
; otherwise, it is just the same. getRandom
can be used for any instance of Random
:
> evalState getRandom (mkStdGen 0) :: Bool True > evalState getRandom (mkStdGen 0) :: Char '\64685' > evalState getRandom (mkStdGen 0) :: Double 0.9872770354820595 > evalState getRandom (mkStdGen 0) :: Integer 2092838931
Indeed, it becomes quite easy to conjure all these at once:
allTypes :: GeneratorState (Int, Float, Char, Integer, Double, Bool, Int) allTypes = liftM (,,,,,,) getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom `ap` getRandom
Here we are forced to used the ap
function, defined in Control.Monad
, since there exists no liftM7
(the standard libraries only go to liftM5
). As you can see, ap
fits multiple computations into an application of the (lifted) nelementtuple constructor (in this case the 7item (,,,,,,)
). To understand ap
further, look at its signature:
ap :: (Monad m) => m (a > b) > m a > m b
Remember then that type a
in Haskell can be a function as well as a value, and compare to:
>:type liftM (,,,,,,) getRandom liftM (,,,,,) getRandom :: (Random a1) => State StdGen (b > c > d > e > f > (a1, b, c, d, e, f))
The monad m
is obviously State StdGen
(which we "nicknamed" GeneratorState
), while ap
's first argument is function b > c > d > e > f > (a1, b, c, d, e, f)
. Applying ap
over and over (in this case 6 times), we finally get to the point where b
is an actual value (in our case, a 7element tuple), not another function. To sum it up, ap
applies a functioninamonad to a monadic value (compare with liftM
, which applies a function not in a monad to a monadic value).
So much for understanding the implementation. Function allTypes
provides pseudorandom values for all default instances of Random
; an additional Int
is inserted at the end to prove that the generator is not the same, as the two Int
s will be different.
> evalState allTypes (mkStdGen 0) (2092838931,9.953678e4,'\825586',868192881,0.4188001483955421,False,316817438)
Exercises 


Notes
 ↑ There are also other ways to seed a pseudorandom number generator without using a global state for the program. For example, a program could have an algorithm that starts with a seed from checking the current date and time (assuming the computer's clock is functioning, this will never be a repeated value).
 ↑ The subtle issue with our approach is that the
transformers
package implements theState
type in a somewhat different way. The differences do not affect how we use or understandState
; as a consequence of them, however,Control.Monad.Trans.State
does not export aState
constructor. Rather, there is astate
function,state :: (s > (a, s)) > State s a
which does the same job. As for why the implementation is not the obvious one we presented above, we will get back to that a few chapters down the road.
 ↑ The technical term for the type of
()
is unit.
Additive monads (MonadPlus)
In our studies so far, we saw that the Maybe and list monads both represent the number of results a computation can have. That is, you use Maybe when you want to indicate that a computation can fail somehow (i.e. it can have 0 results or 1 result), and you use the list monad when you want to indicate a computation could have many valid answers ranging from 0 results to many results.
Given two computations in one of these monads, it might be interesting to amalgamate all valid solutions into a single result. For example, within the list Monad, we can concatenate two lists of valid solutions.
Definition
MonadPlus
defines two methods. mzero
is the monadic value standing for zero results; while mplus
is a binary function which combines two computations.
class Monad m => MonadPlus m where mzero :: m a mplus :: m a > m a > m a
Here are the two instance declarations for Maybe
and the list monad:
instance MonadPlus [] where mzero = [] mplus = (++) instance MonadPlus Maybe where mzero = Nothing Nothing `mplus` Nothing = Nothing  0 solutions + 0 solutions = 0 solutions Just x `mplus` Nothing = Just x  1 solution + 0 solutions = 1 solution Nothing `mplus` Just x = Just x  0 solutions + 1 solution = 1 solution Just x `mplus` Just y = Just x  1 solution + 1 solution = 2 solutions,  but Maybe can only have up to one solution,  so we disregard the second one.
Also, if you import Control.Monad.Error, then (Either e)
becomes an instance:
instance (Error e) => MonadPlus (Either e) where mzero = Left noMsg Left _ `mplus` n = n Right x `mplus` _ = Right x
Like Maybe
, (Either e)
represents computations that can fail. Unlike Maybe
, (Either e)
allows the failing computations to include an error "message" (which is usually a String). Typically, Left s
means a failed computation carrying an error message s
, and Right x
means a successful computation with result x
.
Example: parallel parsing
Traditional input parsing involves functions which consume an input one character at a time. That is, a parsing function takes an input string and chops off (i.e. 'consumes') characters from the front if they satisfy certain criteria. For example, you could write a function which consumes one uppercase character. If the characters on the front of the string don't satisfy the given criteria, the parser has failed; so such functions are candidates for Maybe.
Let's use mplus
to run two parsers in parallel. That is, we use the result of the first one if it succeeds, and otherwise, we use the result of the second. If both fail, then our whole parser returns Nothing
.
In the example below, we consume a digit in the input and return the digit that was parsed.
digit :: Int > String > Maybe Int digit i s  i > 9  i < 0 = Nothing  otherwise = do let (c:_) = s if [c] == show i then Just i else Nothing
Our guards assure that the Int
we are checking for is a single digit. Otherwise, we are just checking that the first character of our String matches the digit we are checking for. If it passes, we return the digit wrapped in a Just
. The doblock assures that any failed pattern match will result in returning Nothing
.
We can use our digit
function with <mplus> to parse Strings of binary digits:
binChar :: String > Maybe Int binChar s = digit 0 s `mplus` digit 1 s
Parser libraries often make use of MonadPlus
in this way. If you are curious, check the (+++)
operator in Text.ParserCombinators.ReadP, or (<>)
in Text.ParserCombinators.Parsec.Prim.
The MonadPlus laws
Instances of MonadPlus are required to fulfill several rules, just as instances of Monad are required to fulfill the three monad laws. Unfortunately, the MonadPlus laws aren't fully agreed on. The most common approach says that mzero and mplus form a monoid. By that, we mean:
 mzero is a neutral element mzero `mplus` m = m m `mplus` mzero = m  mplus is associative  (but not all instances obey this law because it makes some infinite structures impossible) m `mplus` (n `mplus` o) = (m `mplus` n) `mplus` o
There is nothing fancy about "forming a monoid": in the above, "neutral element" and "associative" here is just like how addition of integer numbers is said to be associative and to have zero as neutral element. In fact, this analogy is the source of the names mzero
and mplus
.
The Haddock documentation for Control.Monad quotes additional laws:
mzero >>= f = mzero m >> mzero = mzero
And the HaskellWiki page cites another (with controversy):
(m `mplus` n) >>= k = (m >>= k) `mplus` (n >>= k)
There are even more sets of laws available. Sometimes monads like IO are used as a MonadPlus. Consult All About Monads and the Haskell Wiki page on MonadPlus for more information about such issues.
Useful functions
Beyond the basic mplus
and mzero
, there are two other generalpurpose functions involving MonadPlus
:
msum
A common task when working with MonadPlus: take a list of monadic values, e.g. [Maybe a]
or [[a]]
, and fold it down with mplus
. msum
fulfills this role:
msum :: MonadPlus m => [m a] > m a msum = foldr mplus mzero
In a sense, msum
generalizes the listspecific concat
operation. Indeed, the two are equivalent when working on lists. For Maybe, msum
finds the first Just x
in the list and returns Nothing
if there aren't any.
guard
When discussing the list monad we noted how similar it was to list comprehensions, but we didn't discuss how to mirror list comprehension filtering. The guard
function allows us to do exactly that.
Consider the following comprehension which retrieves all pythagorean triples (i.e. trios of integer numbers which work as the lengths of the sides for a right triangle). First we'll examine the bruteforce approach. We'll use a boolean condition for filtering; namely, Pythagoras' theorem:
pythags = [ (x, y, z)  z < [1..], x < [1..z], y < [x..z], x^2 + y^2 == z^2 ]
The translation of the comprehension above to the list monad is:
pythags = do z < [1..] x < [1..z] y < [x..z] guard (x^2 + y^2 == z^2) return (x, y, z)
The guard
function works like this:
guard :: MonadPlus m => Bool > m () guard True = return () guard _ = mzero
Concretely, guard
will reduce a doblock to mzero
if its predicate is False
. Given the first law stated in the 'MonadPlus laws' section above, an mzero
on the lefthand side of an >>=
operation will produce mzero
again. As doblocks are decomposed to lots of expressions joined up by (>>=)
, an mzero
at any point will cause the entire doblock to become mzero
.
To further illustrate, we will examine guard
in the special case of the list monad, extending on the pythags
function above. First, here is guard
defined for the list monad:
guard :: Bool > [()] guard True = [()] guard _ = []
Basically, guard
blocks off a route. In pythags
, we want to block off all the routes (or combinations of x
, y
and z
) where x^2 + y^2 == z^2
is False
. Let's look at the expansion of the above do
block to see how it works:
pythags = [1..] >>= \z > [1..z] >>= \x > [x..z] >>= \y > guard (x^2 + y^2 == z^2) >>= \_ > return (x, y, z)
Replacing >>=
and return
with their definitions for the list monad (and using some letbindings to keep it readable), we obtain:
pythags = let ret x y z = [(x, y, z)] gd z x y = concatMap (\_ > ret x y z) (guard $ x^2 + y^2 == z^2) doY z x = concatMap (gd z x) [x..z] doX z = concatMap (doY z ) [1..z] doZ = concatMap (doX ) [1..] in doZ
Remember that guard
returns the empty list in the case of its argument being False
. Mapping across the empty list produces the empty list, no matter what function you pass in. So the empty list produced by the call to guard
in the binding of gd
will cause gd
to be the empty list, and therefore ret
to be the empty list.
To understand why this matters, think about listcomputations as a tree. With our Pythagorean triple algorithm, we need a branch starting from the top for every choice of z
, then a branch from each of these branches for every value of x
, then from each of these, a branch for every value of y
. So the tree looks like this:
start ____________________________________________ ...    x 1 2 3 _______________ ... _______________ ... _______________ ...          y 1 2 3 2 3 4 3 4 5 ___...___...___... ___...___...___...___...___...___...                            z 1 2 3 2 3 4 3 4 5 2 3 4 3 4 5 4 5 6 3 4 5 4 5 6 5 6 7
Each combination of x, y and z represents a route through the tree. Once all the functions have been applied, each branch is concatenated together, starting from the bottom. Any route where our predicate doesn't hold evaluates to an empty list, and so has no impact on this concat operation.
Exercises 


Relationship with monoids
When discussing the MonadPlus laws, we alluded to the mathematical concept of monoids. It turns out that there is a Monoid
class in Haskell, defined in Data.Monoid. A fuller presentation of will be given in a later chapter. For now, a minimal definition of Monoid
implements two methods; namely, a neutral element (or 'zero') and an associative binary operation (or 'plus').
class Monoid m where mempty :: m mappend :: m > m > m
For example, lists form a simple monoid:
instance Monoid [a] where mempty = [] mappend = (++)
Sounds familiar, doesn't it? In spite of the uncanny resemblance to MonadPlus
, there is a subtle yet key difference. Note the usage of [a]
instead of []
in the instance declaration. Monoids are not necessarily "containers" of anything or parametrically polymorphic. For instance, the integer numbers on form a monoid under addition with 0 as neutral element.
In any case, MonadPlus
instances look very similar to monoids, as both feature concepts of zero and plus. Indeed, we could even make MonadPlus
a subclass of Monoid
if it were worth the trouble:
instance MonadPlus m => Monoid (m a) where mempty = mzero mappend = mplus
Note
Due to the "free" type variable a
in the instance definition, the snippet above is not valid Haskell 98. If you want to test it, you will have to enable the GHC language extension FlexibleInstances:
 If you are testing with GHCi, start it with the command line option XFlexibleInstances.
 Alternatively, if you are running a compiled program, add
{# LANGUAGE FlexibleInstances #}
to the top of your source file.
Again, Monoid
s and MonadPlus
work at different levels. As noted before, there is no requirement for monoids to be parameterized in relation to "contained" or related type. More formally, monoids have kind *, but instances of MonadPlus
(which are monads) have kind * > *.
Notes
Monadic parser combinators
Monads provide a clean means of embedding a domain specific parsing language directly into Haskell without the need for external tools or code generators.
 Practical Monads: Parsing Monads which shows an example using Parsec, a popular, efficient monadic recursive descent parser library