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
- Lists II (map)
- Lists III (folds, comprehensions)
- 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
- Prologue: IO, an applicative functor
- Understanding monads
- Maybe:List
do
notation- IO:State
- Alternative and MonadPlus
- Monad transformers
Advanced Haskell
- Monoids
- Applicative functors
- Foldable
- Traversable
- Arrow tutorial
- Understanding arrows
- Continuation passing style
- Zippers
- Lenses
- Comonads
- Value recursion (MonadFix)
- Effectful streaming
- Mutable objects
- Concurrency
- Template Haskell
- Type Families
Fun with Types
- Polymorphism
- Existentially quantified types
- Advanced type classes
- Phantom types
- Generalised algebraic data-types (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
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 elementary 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 code from the executable after it's compiled).
To get started, visit haskell.org/downloads for the latest instructions. The current recommended way is to use GHCup. Use it to install the latest recommended version of GHC, cabal
(not stack
), and the Haskell language server. You should use cabal
to install any Haskell library you need. We will cover using cabal
in depth in Haskell/Packaging
Note
Linux users:
It is heavily, heavily discouraged to install anything pertaining to Haskell using your system's package repositories and package manager (unless you're using Fedora or NixOS). Specifically distributions like Arch Linux and Debian manage Haskell packages very badly, and will lead to a bad experience with the tooling. Use GHCup and Cabal as noted above.
To just test some Haskell basics without downloading and installing, there is a playground which includes a few packages by default. Most instructions here on the Wikibook will also work on the playground, though it doesn't accept user input.
First code
After installation, we will do our first Haskell coding with 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
ghci
.
You should get output that looks something like the following:
GHCi, version 8.10.7: http://www.haskell.org/ghc/ :? for help Prelude>
The first bit is GHCi's version, and tells your how to get help in GHCi. The Prelude>
bit is known as the prompt. This is where you enter commands, and GHCi will respond with their results. The prompt also tells you that the current loaded module is Prelude
, which gives you access to most of the built-in functions.
Now let's try some basic arithmetic:
Prelude> 2 + 2 4 Prelude> 5 + 4 * 3 17 Prelude> 2 ^ 5 32
These operators match most other programming languages: +
is addition, *
is multiplication, and ^
is exponentiation (raising to the power of, or ). As shown in the second example, Haskell follows standard order of math operations (e.g. multiplication before addition).
Now you know how to use Haskell as a calculator. Actually, Haskell is always a calculator — just 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).
To leave GHCi once you are done, use :quit
(or just :q
):
Prelude> :quit Leaving GHCi.
GHCi is a powerful development environment. As we progress, we will learn how to load files with source code into GHCi and evaluate different parts of them.
Assuming 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 where we will introduce some of the basic concepts of Haskell and make our first Haskell functions.
Variables and functions
All the examples in this chapter can be saved into a Haskell source file and then evaluated by loading that file into GHCi. Do not include the "Prelude>" prompts part of any example. When that prompt is shown, it means you can type the following code into an environment like GHCi. Otherwise, you should put the code in a file and run it.
Variables
In the last chapter, we used GHCi as a calculator. Of course, that's only practical for short calculations. For longer calculations and for writing Haskell programs, we want to keep track of intermediate results.
We can store intermediate results by assigning them names. These names are called variables. When a program runs, each variable is substituted for the value to which it refers. For instance, consider the following calculation:
Prelude> 3.141592653 * 5^2 78.539816325
That is the approximate area of a circle with radius 5
, according to the formula . Of course, it is cumbersome to type in the digits of , or even to remember more than the first few. Programming helps us avoid mindless repetition and rote memorization by delegating these tasks to a machine. That way, our minds stay 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
Beyond momentary operations in GHCi, you will save your code in Haskell source files (basically plain text) with the extension .hs
. Work with these files using a text editor appropriate for coding (see the Wikipedia article on text editors). Proper source code editors will provide syntax highlighting, which colors the code in relevant ways to make reading and understanding easier. Vim and Emacs are popular choices among Haskell programmers.
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 the value 5.0
.
Note: make sure that there are no spaces at the beginning of the line because Haskell is sensitive to whitespace.
Next, with your terminal at the HaskellWikibook directory, 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.
Note that :load
can be abbreviated as :l
(as in :l Varfun.hs
).
If GHCi gives an error like Could not find module 'Varfun.hs'
, you are probably running GHCi in the wrong directory or saved your file in the wrong directory. You can use the :cd
command to change directories within GHCi (for instance, :cd HaskellWikibook
).
With the file loaded, GHCi's prompt changes from "Prelude" to "*Main". You can now use the newly defined variable r
in your calculations:
*Main> r 5.0 *Main> pi * r^2 78.53981633974483
So, we calculated the area of a circle with radius of 5.0 using the well-known formula . This worked because we defined r
in our Varfun.hs file and pi
comes from the standard Haskell libraries.
Next, we'll make the area formula easier to quickly access by defining a variable name for it. Change the contents of the source file to:
r = 5.0
area = pi * r ^ 2
Save the file. Then, assuming you kept GHCi running with the file still loaded, type :reload
(or abbreviate version :r
):
*Main> :reload Compiling Main ( Varfun.hs, interpreted ) Ok, modules loaded: Main. *Main>
Now we have two variables r
and area
:
*Main> area 78.53981633974483 *Main> area / r 15.707963267948966
Note
The let
keyword (a word with a special meaning) lets us define variables directly at the GHCi prompt without a source file. This looks like:
Prelude> let area = pi * 5 ^ 2
Although sometimes convenient, assigning variables entirely in GHCi this way is impractical for any complex tasks. We will usually want to use saved source files.
Comments
Besides the working code itself, source files may contain text comments. In Haskell there are two types of comment. The first starts with --
and continues until the end of the line:
x = 5 -- x is 5.
y = 6 -- y is 6.
-- z = 7 -- z is not defined.
In this case, x
and y
are defined in actual Haskell code, but z
is not.
The second type of comment is denoted by an enclosing {- ... -}
and can span multiple lines:
answer = 2 * {-
block comment, crossing lines and...
-} 3 {- inline comment. -} * 7
By combining single- and multi-line commenting, it is possible to toggle between executed and commented-out code by adding or removing a single }
character, respectively:
{--
foo :: String
foo = "bar"
--}
vs.
{--}
foo :: String
foo = "bar"
--}
We use comments for explaining parts of a program or making other notes in context. Beware of comment overuse as too many comments can make programs harder to read. Also, we must carefully update comments whenever we change the corresponding code. Outdated comments can cause significant confusion.
Variables in imperative languages
Readers familiar with imperative programming will notice that variables in Haskell seem quite different from variables in languages like C. If you have no programming experience, you could skip this section, but it will help you understand the general situation when encountering the many cases (most Haskell textbooks, for example) where people discuss Haskell in reference to other programming languages.
Imperative programming treats variables as changeable locations in a computer's memory. That approach connects to the basic operating principles of computers. Imperative programs explicitly tell the computer what to do. Higher-level imperative languages are quite removed from direct computer assembly code instructions, but they retain the same step-by-step way of thinking. In contrast, functional programming offers a way to think in higher-level mathematical terms, defining how variables relate to one another, leaving the compiler to translate these to the step-by-step instructions that the computer can process.
Let's look at an example. The following code does not work in Haskell:
r = 5
r = 2
An imperative programmer may read this as first setting r = 5
and then changing it to r = 2
. In Haskell, however, the compiler will respond to the code above with an error: "multiple declarations of r
". Within a given scope, a variable in Haskell gets defined only once and cannot change.
The variables in Haskell seem almost invariable, but they work like variables in mathematics. In a math classroom, you never see a variable change its value within a single problem.
In precise terms, Haskell variables are immutable. They vary only based on the data we enter into a program. We can't define r
two ways in the same code, but we could change the value by changing the file. Let's update our code from above:
r = 2.0
area = pi * r ^ 2
Of course, that works just fine. We can change r
in the one place where it is defined, and that will automatically update the value of all the rest of the code that uses the r
variable.
Real-world Haskell programs work by leaving some variables unspecified in the code. The values then get defined when the program gets data from an external file, a database, or user input. For now, however, we will stick to defining variables internally. We will cover interaction with external data in later chapters.
Here's one more example of a major difference from imperative languages:
r = r + 1
Instead of "incrementing the variable r
" (i.e. updating the value in memory), this Haskell code is a recursive definition of r
(i.e. defining it in terms of itself). We will explain recursion in detail later on. For this specific case, if r
had been defined with any value beforehand, then r = r + 1
in Haskell would bring an error message. r = r + 1
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
|
In Haskell, there is no notion of "x
being declared before y
" or the other way around. Of course, using y
will still require a value for x
, but this is unimportant until you need a specific numeric value.
Functions
Changing our program every time we want to calculate the area of new circle is both tedious and limited to one circle at a time. We could calculate two circles by duplicating all the code using new variables r2
and area2
for the second circle:[1]
r = 5
area = pi * r ^ 2
r2 = 3
area2 = pi * r2 ^ 2
Of course, to eliminate this mindless repetition, we would prefer to have simply one function for area and then apply it to different radii.
A function takes an argument value (or parameter) and gives a result value (essentially the same as in mathematical functions). Defining functions in Haskell is like defining a variable, except that we take note of the function argument that we put on the left hand side of the equals sign. For instance, the following defines a function area
which depends on an argument named r
:
area r = pi * r ^ 2
Look closely at the syntax: the function name comes first (area
in our example), 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 above 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 any circle.
Our function here is defined mathematically as
In mathematics, the argument is enclosed between parentheses, as in or . Many programming languages likewise surround arguments with parentheses, as in max(2, 3)
. But Haskell omits parentheses around a list of arguments (as well as commas between them): max 2 3
.
We still use parentheses for grouping expressions (any code that gives a value) that must 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
Note that 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
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 remains. For example, the evaluation of area 5
proceeds as follows:
area 5 => { replace the left-hand side area r = ... by the right-hand 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 left-hand side of its definition by its right-hand side. When using GHCi, the results of a function call will then show on the screen.
Some more functions:
double x = 2 * x
quadruple x = double (double x)
square x = x * x
half x = x / 2
Exercises |
---|
|
Multiple parameters
Functions can also take more than one argument. For example, a function for calculating the area of a rectangle given its length and 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 -- error
That would apply a function named double
to the two arguments double
and x
. Note that functions can be arguments to other functions (you will see why later). To make this example work, we need to put parentheses around the argument:
quadruple x = double (double x)
Arguments are always passed in the order given. For example:
minus x y = x - y
*Main> minus 10 5 5 *Main> minus 5 10 -5
Here, minus 10 5
evaluates to 10 - 5
, but minus 5 10
evaluates to 5 - 10
because the order changes.
Exercises |
---|
|
On combining functions
Of course, 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.
Exercises |
---|
|
Local definitions
where
clauses
When defining a function, we sometimes want 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 does not work...
heron a b c = sqrt (s * (s - a) * (s - b) * (s - c))
s = (a + b + c) / 2 -- a, b, and c are not defined here
... because the variables a
, b
, c
are only available in the right-hand side of the function heron
, but the definition of s
as written here is not part of the right-hand side of heron
. To make it part of the right-hand side, we 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 top-level 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?
Consider the following GHCi sequence:
Prelude> let r = 0 Prelude> let area r = pi * r ^ 2 Prelude> area 5 78.53981633974483
It would have been an unpleasant surprise to return 0
for the area because of the earlier 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 may seem confusing, but consider how many people have the name John, and yet for any context with only one John, we can talk about "John" with no confusion. Programming has a notion similar to context, called scope.
We will not explain the technicalities behind scope right 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. That said, appropriately unique names for variables do make the code easier for human readers to understand.
Summary
- Variables store values (which can be any arbitrary Haskell expression).
- Variables do not change within a scope.
- Functions help you write reusable code.
- Functions can accept more than one parameter.
We also learned about non-code text comments within a source file.
Notes
- ↑ As this example shows, the names of variables may contain numbers as well as letters. Variables in Haskell must begin with a lowercase letter but may then have any string consisting of letter, numbers, underscore (_) or tick (').
Truth values
Equality and other comparisons
In the last chapter, we used the equals sign to define variables and functions in Haskell as in the following code:
r = 5
That means that the evaluation of the program replaces all occurrences of r
with 5
(within the scope of the definition). Similarly, evaluating the code
f x = x + 3
replaces all occurrences of f
followed by a number (f
's argument) with that number plus three.
Mathematics also uses the equals sign in an important and subtly different way. For instance, consider this simple problem:
Example: Solve the following equation:
Our interest here isn't about representing the value as , or vice-versa. Instead, we read the equation as a proposition 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, elementary algebra tells us that (i.e. 2 is the number that will make the equation true, giving ).
Comparing values to see if they are equal is also useful in programming. In Haskell, such tests look just like an equation. Since the equals sign is already used for defining things, Haskell uses a double equals sign, ==
instead. Enter our proposition above in GHCi:
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. Next, we will use our own functions in these tests. Let's try the function f
we mentioned at the start of the chapter:
Prelude> let f x = x + 3 Prelude> f 2 == 5 True
This works as expected because f 2
evaluates to 2 + 3
.
We can also 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). These tests work comparably to ==
(equal to). For example, 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
What is actually going on when GHCi determines whether these arithmetical propositions are true or false? 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
Whereas the "4" returned earlier is a number which represents some kind of count, quantity, etc., "True" is a value that stands for the truth of a proposition. Such values are called truth values, or boolean values.[1] Naturally, only two possible boolean values exist: True
and False
.
Introduction to types
True
and False
are real values, not just an analogy. Boolean values have the same status as numerical values in Haskell, and you can manipulate them in similar ways. One trivial example:
Prelude> True == True True Prelude> True == False False
True
is indeed equal to True
, and True
is not equal to False
. Now: 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 an equation for ‘it’: it = 2 == True
Error! The question just does not make sense. We cannot compare a number with a non-number or a boolean with a non-boolean. Haskell incorporates that notion, and the ugly error message complains about this. Ignoring much of the clutter, the 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 failed.
So, values have types, and these types define limits to what we can or cannot do with the values. True
and False
are values of type Bool
. The 2
is complicated because there are many different types of numbers, so we will defer that explanation until later. Overall, types provide great power because they regulate the behavior of values with rules that 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
An equality test like 2 == 2
is an expression just like 2 + 2
; it evaluates to a value in pretty much the same way. The ugly error message we got on the previous example even says so:
In the expression: 2 == True
When we type 2 == 2
in the prompt and GHCi "answers" True
, it is simply evaluating an expression. In fact, ==
is itself a function which takes two arguments (which are the left side and the right side of the equality test), but the syntax is notable: Haskell allows two-argument functions to be written as infix operators placed between their arguments. When the function name uses only non-alphanumeric characters, this infix approach is the common use case. 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
Thus, we see how (==)
works as a function similarly to areaRect
from the previous module. The same considerations apply to the other relational operators we mentioned (<
, >
, <=
, >=
) and to the arithmetical operators (+
, *
, etc.) – all are functions that take two arguments and are normally written as infix operators.
In general, we can say that tangible things in Haskell are either values or functions.
Boolean operations
Haskell provides three basic functions for further manipulation of truth values as in logic propositions:
(&&)
performs the and operation. Given two boolean values, it evaluates toTrue
if both the first and the second areTrue
, and toFalse
otherwise.
Prelude> (3 < 8) && (False == False) True Prelude> (&&) (6 <= 5) (1 == 1) False
(||)
performs the or operation. Given two boolean values, it evaluates toTrue
if at least one of them isTrue
and toFalse
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 convertsTrue
toFalse
and vice-versa.
Prelude> not (5 * 2 == 10) False
Haskell libraries already include the relational operator function (/=)
for not equal to, but we could easily implement it ourselves as:
x /= y = not (x == y)
Note that we can 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
Haskell programs often use boolean operators in convenient and abbreviated syntax. When the same logic is written in alternative styles, we call this syntactic sugar because it sweetens the code from the human perspective. We'll start with guards, a feature that relies on boolean values and allows us to write simple but powerful functions.
Let's implement the absolute value function. The absolute value of a real number is the number with its sign discarded; 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. To express this decision process in Haskell using guards, the implementation could look like this:[2]
Example: The absolute value function.
absolute x
| x < 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,
absolute
, and saying it will take a single argument, which we will namex
.
- Instead of just following with the
=
and the right-hand side of the definition, we enter the two alternatives placed below on separate lines.[3] These alternatives are the guards proper. Note that the whitespace (the indentation of the second and third lines) 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 function only uses the equals sign and the right-hand side from a line if the predicate evaluates toTrue
.
- The
otherwise
case is used when none of the preceding predicates evaluate toTrue
. In this case, ifx
is not smaller than zero, it must be greater than or equal to zero, so the final predicate could have just as easily beenx >= 0
; butotherwise
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 catch-all guard. As evaluation of the guard predicates is sequential, the otherwise
predicate will only be reached if none of the previous cases evaluate 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
In the first guard
| x < 0 = -x
we used the minus sign to negate x
. It is worth noting that this way of expressing sign inversion is a special case of sorts, in that the -
is not a function that takes one argument and evaluates to 0 - x
, but merely a syntactical abbreviation. While very handy, this abbreviation 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 negative-four without using any parentheses for grouping).
That being so, when testing absolute
with negative numbers you should call it like this:
Prelude> absolute (-10) 10
where
and Guards
where
clauses work well along with guards. For instance, consider a function which computes the number of unique (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.
- ↑ This function is already provided by Haskell with the name
abs
, so in a real-world situation you don't need to provide an implementation yourself. - ↑ We could have joined the lines and written everything in a single line, but it would be 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 | Address | Telephone number |
Sherlock | Holmes | 221B Baker Street London | 743756 |
Bob | Jones | 99 Long Road Street Villestown | 655523 |
The fields in each entry contain values. Sherlock is a value as is 99 Long Road Street Villestown as well as 655523. Let's classify the values in this example in terms of types. "First Name" and "Last Name" contain text, so we say that the values are of type String.
At first glance, we might classify address as a String. However, the semantics behind an innocent address are quite complex. Many human conventions dictate how we interpret addresses. 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. Each part of the address has its own meaning.
In principle, we can indeed say that 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 characters (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.
We might also apply this rationale to the telephone numbers. We could specify 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 Numbers is that doing arithmetic 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. Also, each digit comprising a telephone number is important; we cannot accept losing some of them by rounding or even by omitting leading zeros.
Why types are useful
How does it help us program well to describe and categorize things? Once we define a type, we can specify what we can or cannot do with it. That makes it far easier to manage larger programs and avoid errors.
Using the interactive :type
command
Let's explore how types work using GHCi. The type of any expression can be checked with :type
(or shortened to :t
) command. Try this 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
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. Note that boolean values are not just for value comparisons. Bool
captures the semantics of a yes/no answer, so it can 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"). Now, single quotation marks only work for individual characters, so if we need to enter longer 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 the square brackets. [Char]
means a number of characters chained together, forming a list of characters. Haskell considers all Strings to be lists of characters. Lists in general are important entities in Haskell, and we will cover them in more detail in a little while.
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.[1] 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 vice-versa). 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 the type of value it evaluates to.
Example: chr
and ord
Text presents a problem to computers. At its lowest level, a computer only knows binary 1s and 0s. To represent 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 takes care of the conversion to binary numbers without our intervention.
The easiest way to convert 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 what something called the ASCII standard is: take 128 commonly-used characters and number them (ASCII doesn't actually start with 'a', but the general idea is the same). Of course, it would be quite a chore 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
[2]:
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
, refers to integer numbers, and is one of quite a few different types of numbers.[3] 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. 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
What would be the type of a function that takes more than one argument?
Example: A function with more than one argument
xor p q = (p || q) && not (p && q)
(xor
is the exclusive-or 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.[4] 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, buttons, application windows, moving the mouse around, etc. One function 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:[5]
Example: openWindow
openWindow :: WindowTitle -> WindowSize -> Window
You don't know these types, but 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 earlier, the two arrows mean that 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.
So, even if you have never seen a function before or don't know how it actually works, a type signature can give you a general idea of what the function does. Make a habit of 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 but also develop a useful kind of intuition about functions in Haskell.
Exercises |
---|
What are the types of the following functions? For any functions 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. Consider the 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. For maximum clarity, type signatures go above the corresponding function definition.
The signatures we add in this way serve a dual role: they clarify the type of the functions both to human readers and to the compiler/interpreter.
Type inference
If type signatures tell the interpreter (or compiler) about the function type, how did we write our earliest Haskell code without type signatures? Well, 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 starts with the types of things it knows and then works out the types of the rest of the values. Consider 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,[6] 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 why write type signatures if they will be inferred anyway? In some cases, the compiler lacks information to infer the type, and so the signature becomes obligatory. In some other cases, we can use a type signature to influence to a certain extent the final type of a function or value. These cases needn't concern us for now, but we have a few other reasons to include type signatures:
- 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, commenting your code helps, but having the types clearly stated helps 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 compile-time, 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
A somewhat more realistic example will help us understand better how signatures can help documentation. 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 like that in 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
. 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. Paired with sensible function names, we have enough information 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 above 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. This helps reduce bugs in your programs. To take a very trivial example:
Example: A non-typechecking program
"hello" + " world" -- type error
That line will cause a program to fail when compiling. You can't add two strings together. In all likelihood, the programmer intended to use the similar-looking concatenation operator, which can be used to join two strings together into a single one:
Example: Our erroneous program, fixed
"hello" ++ " world" -- "hello world"
An easy typo to make, but Haskell catches the error when you tried to compile. You don't have to wait until you run the program for the bug to become apparent.
Updating a program commonly involves changes to types. If a change is unintended, or has unforeseen consequences, then it will show up when compiling. Haskell programmers often remark that once they have fixed all the type errors, and their programs compile, that they tend to "just work". The behavior may not always match the intention, but the program won't crash. Haskell has far fewer run-time errors (where your program goes wrong when you run it rather than when you compile) than other languages.
Notes
- ↑ 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 higher-order functions.
- ↑ This has been somewhat simplified to fit our purposes. Don't worry, the essence of the function is there.
- ↑ As 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 that.
Lists and tuples
Haskell uses two fundamental structures for managing several values: lists and tuples. They both work by grouping multiple values into a single combined value.
Lists
Let's build some lists in GHCi:
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 mixed-type 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 pronounced "cons". The process of building up a list this way is often referred to as consing. This terminology comes from LISP programmers who invented the verb "to cons" (a mnemonic for "constructor") to refer to this specific task of prepending an element to a list.
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
), you get back 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, Haskell builds all lists this way by consing all elements to the empty list, []
. The commas-and-brackets notation are just syntactic sugar. 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 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 familiar-looking type error message. It 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.[1]
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 |
---|
|
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 commas-and-brackets notation.
Prelude> "hey" == ['h','e','y'] True Prelude> "hey" == 'h':'e':'y':[] True
Using double-quoted strings is just more syntactic sugar.
Lists of lists
Lists can contain anything — 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 tricky sometimes because a list of things does not have the same type as a thing all by itself. The type Int
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 allow us to express some kinds of complicated, structured data (two-dimensional matrices, for example). They are also one of the places where the Haskell type system truly shines. Human programmers (including this wikibook co-author) get confused all the time when working with lists of lists, and having restrictions on types often helps in wading through the potential mess.
Tuples
A different notion of many
Tuples offer another way of storing multiple values in a single value. Tuples and lists have two key differences:
- 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 number of times we made calls. In such a case the three values won't have the same type, since the name and the phone number are strings, but contact counter will be a number, so lists wouldn't work.
Tuples are marked by 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: True and 1. The next example again has two elements: "Hello world" and False. The third example is a tuple consisting of five elements: 4 (a number), 5 (another number), "Six" (a string), True (a boolean value), and 'b' (a character).
A quick note on nomenclature: In general you use n-tuple to denote a tuple of size n. Commonly, we call 2-tuples (that is, tuples with 2 elements) pairs and 3-tuples triples. Tuples of greater sizes aren't actually all that common, but we can logically extend the naming system to quadruples, quintuples, and so on.
Exercises |
---|
|
Tuples are 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 single-purpose data structure, maybe one that only gets used in that function. In Haskell, we would return such results 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 within 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 related combinations.
Example: Nesting tuples and lists
((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]
The type of a tuple is defined not only by its size, but, like lists, 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 Haskell cannot have a list like [("a",1),(2,"b"),(9,"c")]
.
Exercises |
---|
|
Retrieving values
For lists and tuples to be useful, we will need to access the internal values they contain.
Let's begin with pairs (i.e. 2-tuples) representing the (x, y) coordinates of a point. Imagine you want to specify a specific square on a chess board. You could label the ranks and files from 1 to 8. Then, a pair (2, 5)
could represent the square in rank 2 and file 5. Say we want a function for finding all the pieces in a given rank. We could start with the coordinates of all the pieces and then look at the rank part and see whether it equals whatever row we want to examine. Given a coordinate pair (x, y)
of a piece, our function would need to extract the x
(the rank coordinate). For this sort of goal, there are two standard functions, fst
and snd
, that retrieve[2] 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, by definition, only work on pairs.[3]
For lists, the functions head
and tail
are roughly analogous to fst
and snd
. 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]
Note
Unfortunately, we have 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. Outside of GHCi, attempting to run head
or tail
on the empty list will crash a program.
We will play with head
and tail
for the moment, but we want to avoid any risk of such malfunctions in our real code, so we will learn later about better options. One might ask "What is the problem? Using head
and tail
works 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 could end up being passed to head
and tail
grows quickly as 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. As we advance through the book, we will learn better ways to avoid these risks.
Pending questions
The four functions introduced here do not appear 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 we do any better than just breaking them after the first element? For the moment, we will have to leave these questions pending. Once we do some necessary groundwork, we will return to this subject in future chapters on list manipulation. For now, know that separating head and tail of a list will allow us to do anything we want.
Exercises |
---|
|
Polymorphic types
Recall that 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]]
Lists of Bool
are a different type than lists of [Char]
(which is the same as a list of String
because [Char]
and String
are synonyms). Since functions only accept arguments of the types specified in the type of the function, that might lead to some complications. For example, consider the case of head
. Given that [Int]
, [Bool]
and [String]
are different types, it seems we would need separate functions for every case – headInt :: [Int] -> Int
, headBool :: [Bool] -> Bool
, headString :: [String] -> String
, and so on… That, however, would be not only very annoying but also rather senseless. After all, lists are assembled in the same way regardless of the types of the values they contain, and so we would expect the procedure to get the first element of the list would remain the same in all cases.
Fortunately, we do have a single function head
, which works on all lists:
Prelude> head [True, False] True Prelude> head ["hey", "my"] "hey"
How can that possibly work? As usual, checking the type of head
provides a good hint:
Example: Our first polymorphic type
Prelude> :t head head :: [a] -> a
The a
in the signature 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. 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. The type of head
, for instance, tells us that it takes a list ([a]
) of values of an arbitrary type (a
) and gives back a value of that same type (a
).
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 result, as opposed to
f :: a -> b
which means that f
takes an argument of any type and gives a result of any type which may or may not match the type of whatever we have for a
. The different type variables do not specify that the types must be different, it only says that they can be different.
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?" for 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. As with lists, the type of a pair depends on the type of its elements, so the functions need to be polymorphic. Also remember that pairs (and tuples in general) don't have to be homogeneous with respect to internal 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 the correct type is:
Example: The types of fst
and snd
fst :: (a, b) -> a
snd :: (a, b) -> b
If you knew nothing about fst
and snd
other than the type signatures, you might still guess that they return the first and second parts of a pair, respectively. Although that is correct, other functions may have this same type signature. All the signatures say is that they just have to return something with the same type as the first and second parts of the pair, respectively.
Exercises |
---|
Give type signatures for the following functions:
|
Summary
This chapter introduced lists and tuples. The key similarities and differences between them are:
- Lists are defined by square brackets and commas :
[1,2,3]
.- Lists can contain anything as long as all the 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 can contain anything, even things of different types.
- The length of a tuple is encoded in its type; tuples with different lengths will have different types.
- Lists and tuples can be combined in any number of ways: lists within lists, tuples within lists, etc, but their criteria must still be fulfilled for the combinations to be valid.
Notes
- ↑ At this point you might question the value of types. While they can feel annoying at first, more often than not they turn out to be extremely helpful. 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 math-speak, a function that gets some data out of a structure is called a projection.
- ↑ Yes, 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 from the standard libraries work.
Type basics II
In this chapter, we will show how numerical types are handled in Haskell and 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
Mathematics puts few restrictions on the kinds of numbers we can add together. Consider, for instance, (two natural numbers), (a negative integer and a rational number), or (a rational and an irrational). All of these are valid. In fact, any two real numbers can be added together. In order to capture such generality in the simplest way possible we need a general Number
type in Haskell, so that the signature of (+)
would be simply
(+) :: Number -> Number -> Number
However, that design fits poorly with the way computers perform arithmetic. While computers can handle integers as a sequence of binary digits in memory, that approach does not work for real numbers,[2] thus making a more complicated encoding necessary for dealing with 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 makes using the simpler encoding worthwhile for integer values. So, we have at least two different ways of storing numbers: one for integers and another for general real numbers. Each approach 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.
So much for having a universal Number
type – it seems that we can't even have (+)
mix integers and floating-point numbers. However, Haskell can at least use the same (+)
function with either integers or floating point numbers. Check this yourself in GHCi:
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, here's a possible type signature for (+)
that would account for the facts above:
(+) :: a -> a -> a
With that type signature, (+)
would take two arguments of the same type a
(which could be integers or floating-point numbers) and evaluate to a result of type a
(as long as both arguments are the same type). But this type signature indicates any type at all, and we know that we can't use (+)
with two Bool
values, or two Char
values. What would adding two letters or two truth-values mean? So, the actual type signature of (+)
uses 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, in Haskell terminology, instances of Num
.
Numeric types
So, which are the actual number types (that is, the instances of Num
that the a
in the signature may stand for)? The most important numeric types are
Int
, Integer
and Double
:
Int
corresponds to the plain integer type found in most languages. It has fixed maximum and minimum values that depend on a computer's processor. (In 32-bit machines the range goes from -2147483648 to 2147483647).
Integer
also is used for integer numbers, but it supports arbitrarily large values – at the cost of some efficiency.
Double
is the double-precision floating point type, a good choice for real numbers in the vast majority of cases. (Haskell also hasFloat
, the single-precision counterpart ofDouble
, which is usually less attractive due to further loss of precision.)
Several other number types are available, but these cover most in everyday tasks.
Polymorphic guesswork
If you've read carefully thus far, you know that we don't need to specify types always because the compiler can infer types. You also know that we cannot mix types when functions require matched types. Combine this with our new understanding of numbers to understand how Haskell handles basic arithmetic like this:
Prelude> (-7) + 5.12 -1.88
This may seem to add two numbers of different types – an integer and a non-integer. Let's see what the types of the numbers we entered actually are:
Prelude> :t (-7) (-7) :: (Num a) => a
So, (-7)
is neither Int
nor Integer
! Rather, it is a polymorphic value, which can "morph" into any number type. Now, let's look at the other number:
Prelude> :t 5.12 5.12 :: (Fractional t) => t
5.12
is also a polymorphic value, but one of the Fractional
class, which is a subset of Num
(every Fractional
is a Num
, but not every Num
is a Fractional
; for instance, Int
s and Integer
s are not Fractional
).
When a Haskell program evaluates (-7) + 5.12
, it must settle for an actual matching type for the numbers. The type inference accounts for the class specifications: (-7)
can be any Num
, but there are extra restrictions for 5.12
, so that's the limiting factor. With no other restrictions, 5.12
will assume the default Fractional
type of Double
, so (-7)
will become a Double
as well. Addition then proceeds normally and returns a Double
.[4]
The following test will give you a better feel of this 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 result in a non-integer. Nevertheless, we can still write something like
Prelude> 4 / 3 1.3333333333333333
because the literals 4
and 3
are polymorphic values and therefore assume the type Double
at the behest of (/)
. Suppose, however, we want to divide a number by the number of elements in a list.[5] The obvious thing to do would be using the length
function, which takes a list and gives the number of elements in it:
Prelude> length [1,2,3] 3 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:0-17 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 :: (Foldable t) => t a -> Int
For now, let's focus on the type of the result of length
. It is Int
; the result is not polymorphic. As an Int
is not a Fractional
, Haskell won't let us use it with (/)
.
To escape this problem, we have a special function. Before following on with the text, try to guess what this 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 value. 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
In some ways, this issue is annoying and tedious, but it is an inevitable side-effect of having a rigorous approach to manipulating numbers. In Haskell, if you define a function with an Int
argument, it will never be converted to an Integer
or Double
, unless you explicitly use a function like fromIntegral
. As a direct consequence of its refined type system, Haskell has a surprising diversity of classes and functions dealing with numbers.
Classes beyond numbers
Haskell has 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 for types of values which can be compared for equality, and it includes all of the basic non-functional types.[6]
A quite different example of a typeclass that we have glossed over has appeared in the type of length
. Given that length
takes a list and gives back an Int
, we might have expected its type to be:
length :: [a] -> Int
The actual type, however, is a little trickier:
length :: (Foldable t) => t a -> Int
Beyond lists, there are other kinds of structures that can be used to group values in different ways. Many of these structures (together with lists themselves) belong to a typeclass called Foldable
. The type signature of length
tells us that it works not only with lists, but also with all those other Foldable
structures. Later in the book, we will see examples of such structures, and discuss Foldable
in detail. Until then, whenever you see something like Foldable t => t a
in a type signature, feel free to mentally replace that with [a]
.
Typeclasses add a lot to the power of the type system. We will return to this topic later 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. - ↑ Among other issues, between any two real numbers there are uncountably many real numbers – and that fact can't be directly mapped into a representation in memory no matter what we do.
- ↑ This is a loose definition, but will suffice until we 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 (where an integer literal is silently converted to a double). In C, however, the conversion is done behind your back, while in Haskell it only occurs if the variable/literal is a polymorphic value. This distinction will become clearer shortly, when we show a counter-example.
- ↑ A reasonable scenario – think of computing an average of the values in a list.
- ↑ Comparing two functions for equality is considered intractable
Building vocabulary
This chapter will be a bit of an interlude with some advice for studying and using Haskell. We will discuss the importance of acquiring a vocabulary of functions and how this book and other resources can help. First, however, we need to understand function composition.
Function composition
Function composition means applying one function to a value and then applying another function to the result. Consider these two 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 of those would give type errors.
The composition of two functions results in a function in its own right. If we regularly apply f and then square (or vice-versa), we should generate a new variable name for the resulting combinations:
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
. (.)
is modeled after the mathematical operator , which works in the same way: .
Incidentally, our function definitions are effectively mathematical equations, so we can take
squareOfF x = (square . f) x
and cancel the x
from both sides, leaving:
squareOfF = square . f
We will later learn more about such cases of functions without arguments shown. For now, understand that we can simply substitute our defined variable name for any case of the composed functions.
The need for a vocabulary
Haskell makes it simple to write composed functions and to define variables, so we end up with relatively simple, elegant, and expressive code. Of course, to use function composition, we first need to have functions to compose. While functions we write ourselves will always be available, every installation of GHC comes with a vast assortment of libraries (i.e. packaged code), which provide functions for many common tasks. For that reason, effective Haskell programmers need some familiarity with the essential libraries. At the least, you should know how to find useful functions in the libraries when you need them.
Given only the Haskell syntax we will cover through the Recursion chapter, we will, in principle, have enough knowledge to write nearly any list manipulation program we want. However, writing full programs with only these basics would be terribly inefficient because we would end up rewriting large parts of the standard libraries. So, much of our study going forward will involve studying and understanding these valuable tools the Haskell community has already built.
Prelude and the libraries
Here are a few basic facts about Haskell libraries:
First and foremost, Prelude is the core library loaded by default into every Haskell program. This ubiquitous library provides a useful set of functions, classes, and types. We refer to Prelude types and functions throughout these introductory chapters.
GHC provides a large set of core libraries having a wide range of tools, but only Prelude loads automatically. The other libraries are modules available for import into your program. Later on, we explain the minutiae of how modules work. For now, just know that your source file needs lines near the top to import any desired modules. For example, to use the function permutations
from the module Data.List
, add the line import Data.List
to the top of your .hs file. Here's a full source file example:
Example: Importing a module in a source file
import Data.List
testPermutations = permutations "abc"
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.[1] 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"
. We could solve this problem using only the basics we have already covered along with a few insights in the upcoming Recursion chapter. Below is one messy, complicated solution. 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 = 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:
- To see whether
monsterRevWords
does what you expect, 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,[2] we are set for an awful time.
- Finally, we have 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 no other whitespace characters (tabs, newlines, etc.).[3]
We can do much better than the junk above if we use 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) bug-free.[4] So, any time some program you are writing begins to look like monsterRevWords
, look around and reach for your toolbox — the libraries.
This book's use of the libraries
After the stern warnings above, you might expect us to continue diving deep into the standard libraries. However, the Beginner's Track is meant to cover Haskell functionality in a conceptual, readable, and reasonably compact manner. A systematic study of the libraries would not help us, but we will introduce functions from the libraries as appropriate to each concept we cover.
- In the Elementary Haskell section, 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 tightly-knit, later parts of the book are more independent. Haskell in Practice includes 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, all modules have basic documentation. You may not be ready to read that directly yet, but we'll get there. You can read the Prelude specification on-line 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, beginner friendly. It covers a large set of libraries. You can search by function name (say, length) or by type ("function from lists to Int", which you'd write [a]->Int). This second type of search helps you find very specific functions and prevents reinventing the wheel.
- 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 has documentation for its libraries. We will not venture outside of the core libraries in the Beginner's Track, but you should certainly use Hackage once you begin your own projects.
- When appropriate, we will give pointers to other useful learning resources, especially when we move towards intermediate and advanced topics.
Notes
- ↑ The example here is inspired by the Simple Unix tools demo in the HaskellWiki.
- ↑ Co-author'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, many other functions from Prelude or
Data.List
could help to makemonsterRevWords
somewhat saner — to name a few:(++)
,concat
,groupBy
,intersperse
— but no use of those would compare to the one-liner above.
Next steps
This chapter introduces pattern matching and two new pieces of syntax: if
expressions and let
bindings.
if / then / else
Haskell syntax supports garden-variety 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
. The predefined signum
function does that job already; but for the sake of illustration, 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:
*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, Haskell will think that you are trying to subtract 1
from mySignum
(which would give a type error).
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. The construct has to result in a value in both cases and, specifically, a value of the same type in both cases.
Function definitions using if / then / else like the one above can be rewritten using Guards.
Example: From if to guards
mySignum x
| x < 0 = -1
| x > 0 = 1
| otherwise = 0
Similarly, the absolute value function defined in Truth values can be rendered with an if/then/else:
Example: From guards to if
absolute 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, either 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
Consider 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 second-placed;
- 4 for third-placed;
- 3 for fourth-placed;
- 2 for fifth-placed;
- 1 for sixth-placed;
- 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 piece-wise 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 piece-wise definition from now on) shows to a reader of the code what the function does in a 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 left-hand sides? What about variable arguments?
This feature of Haskell is called pattern matching. When we call pts
, the argument is matched against the numbers on the left side of each of the equations, which in turn are the patterns. The matching is done in the order we wrote the equations. First, 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; 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 the lack of x
or any other variable standing for the argument, we simply don't need that to write the definitions. All possible return values are constants. Besides, variables are used to express relationships on the right side of the definition, so the x
is unnecessary in our pts
function.
However, we could use a variable 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
So, 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 is booleans. For instance, the (||)
logical-or 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.
Now, let's 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: because 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 2-tuple - 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 power of pattern matching comes from its use in accessing 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 (an alternative to where
clauses for making local declarations). For instance, take the problem of finding the roots of a polynomial of the form (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 or 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 insist on keeping tabs as distinct, at least ensure that your tabs always have the same length. |
Note
The Indentation chapter has a full account of indentation rules.
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
Beyond internally calculating values, we want our programs to interact with the world. The most common beginners' program in any language simply displays a "hello world" greeting on the screen. Here's a Haskell version:
Prelude> putStrLn "Hello, World!"
putStrLn
is one of the standard Prelude tools. As the "putStr" part of the name suggests, it takes a String
as an argument and prints it to the screen. We could use putStr
on its own, but we usually include the "Ln" part so to also print a line break. Thus, 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 tells 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 these IO
values 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). ()
(pronounced as "unit") is a type that only contains one value also called ()
(effectively a tuple with zero elements). 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 ()
".
A few more examples of when we 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 putStrLn
to pixels in the screen, but we don't need to understand any of the details to write our programs. A complete Haskell program is actually a big IO action. 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 action main
that will be executed when the program is run. The compiler takes care of instructing the computer on how to do this.
Exercises |
---|
Back in the Type Basics chapter, we mentioned that the type of the openWindow function had been simplified. What do you think its type should actually be? |
Sequencing actions with do
do notation provides a convenient means of putting actions together (which is essential in doing useful things with Haskell). Consider the following 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. We could explain how those functions work and then introduce do
notation. However, there are several topics we would need to cover before we can give a convincing explanation. Jumping in with do
right now is a pragmatic shortcut that will allow you to start writing complete programs with IO right away. We will see how 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 (to the terminal in this case) and brings back a String
. 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 isn't a defined value with a type until we bring it into the Haskell program.
The program doesn't know the state of the outside world until runtime, so it cannot predict the exact results of IO actions. To manage the relationship of these IO actions to other aspects of a program, the actions must be executed in a predictable sequence defined in advance in the code. With regular functions that do not perform IO, the exact sequencing of execution is less of an issue — 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 assigns a variable name to stand for the returned value. We cannot know what the value will be in advance, but we know it will use the specified variable name, so we can then use the variable elsewhere (in this case, to prepare the final message being printed). The final action defines the type of the whole do
block. Here, the final action is the result of a putStrLn
, and so our whole program 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.91You will need to use the function read to convert user strings like "3.3" into numbers like 3.3 and the 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 write something like this:
Example: executing getLine
directly
main = do
putStrLn "Please enter your name:"
getLine
putStrLn "Hello, how are you?"
In this case, we don't use the input at all, but we still give the user the experience of entering their name. By omitting the <-
, the action will happen, but the data won't be stored or accessible to the program.
<-
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 the final 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
Making sense of this requires a somewhat deeper understanding of Haskell than we currently have. Suffice it to
say, after any line where you use <-
to get the value of an action, Haskell expects another action, so the final action cannot have any <-
s.
Controlling actions
Normal Haskell constructions like if/then/else can be used within the do notation, but you need to take some care here. 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!"
Remember that the if/then/else construction 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.
That has the correct type. Let's now 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 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 a common stumbling block for new Haskellers. If you have run into trouble working with actions, see if any of your problems or questions match any of the cases below. We suggest skimming this section now, then come back here 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. putStrLn
is expecting a String
as input. We do not have a String
; we have 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 ever-handy 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 non-actions 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 converts a String to uppercase
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 expecting an IO type and something which does not produce IO. This time, the trouble is 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. 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
would be misguided. Consider another issue too: what if we wanted to use makeLoud from some other, non-IO, 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. We at least leave themakeLoud
function itself nice and IO-free whilst using it in an IO-compatible 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 extra-convenient 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 have the fundamentals needed to do some fancier input/output. Here are some IO-related topics you may want to check in parallel with the main track of this course.
- You could continue the sequential track, learning more about types and eventually monads.
- Alternately: you could start learning about building graphical user interfaces in the GUI chapter
- For more IO-related functionality, you could also consider learning more about the System.IO library
Elementary Haskell
Recursion
Recursive functions play a central role in Haskell, and are used throughout computer science and mathematics generally. Recursion is basically a form of repetition, and we can understand it by making distinct what it means for a function to be recursive, as compared to how it behaves.
A recursive function simply means this: a function that has the ability to invoke itself.
And it behaves such that it invokes itself only when a condition is met, as with an if/else/then expression, or a pattern match which contains at least one base case that terminates the recursion, as well as a recursive case which causes the function to call itself, creating a loop.
Without a terminating condition, a recursive function may remain in a loop forever, causing an infinite regress.
Numeric recursion
The factorial function
Mathematics (specifically combinatorics) has a function called factorial.[1] It takes a single non-negative 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 continue:
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 one-liner. To do this, we need to add a semicolon to separate the lines:
> let factorial 0 = 1; factorial n = n * factorial (n - 1)
Haskell actually uses line separation and other whitespace as a substitute for separation and grouping characters such as semicolons. Haskell programmers generally prefer the clean look of separate lines and appropriate indentation; still, explicit use of semicolons and other markers is always an alternative.
The example above demonstrates the 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 sub-task. 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 the convention (which is often useful) is to define the factorial of 0.)
When reading or composing recursive functions, you'll rarely need to “unwind” the recursion bit by bit — we leave that to the compiler.
One more note about our 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 (clearly 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
Imperative languages use loops in the same sorts of contexts where Haskell programs use 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 by making each loop variable 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 have concerns about performance problems caused by recursion. However, compilers for Haskell and other functional programming languages include a number of optimizations for recursion, (not surprising given how often recursion is needed). Also, Haskell is lazy — calculations are only performed once their results are required by other calculations, and that helps to avoid some of the performance problems. We'll discuss such issues and some of the subtleties they involve further 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 learning 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 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 |
---|
|
List-based recursion
Haskell has many recursive functions, especially concerning lists.[4] Consider 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
Note
If you try to load the definition above from a source file, GHCi will complain about an “ambiguous occurrence” when you try to use it, as the Prelude already provides length
. In that case, just change the name of the function which you are defining to something else. like length'
or myLength
.
So, 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 (this 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, by convention, 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).
Consider 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
. 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 list-based 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 list-based 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 list-based algorithm, start with a case for the empty list and a case for the non-empty list and see if your algorithm is recursive.
Don't get TOO excited about recursion...
Despite its ubiquity in Haskell, one rarely has to write functions that are explicitly recursive. Instead, standard library functions perform recursion for us in various ways. For example, a simpler way to implement the factorial
function is:
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 uses 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 non-negative 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 uses a function called
foldl
to which it “delegates” the recursion.
Lists II
Earlier, we learned that Haskell builds lists via the cons operator (:)
and the empty list []
. We saw how we can work on lists bit by bit using a combination of recursion and pattern matching. In this chapter and the next, we will consider more in-depth techniques for list processing and discover some new notation. We will get our first taste of Haskell features like infinite lists, list comprehensions, and higher-order 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 that list elements are of type Integer
. However, as you will recall from the discussions on Type basics II, there are many different types within 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
Here's 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 which evaluates to an empty list. In the recursive case, doubleList builds up a new list by using (:)
. The first element of this new list is twice the head of the argument, and we obtain the rest of the result by recursively calling doubleList on the tail of the argument. When the tail gets to an empty list, the base case will be invoked and recursion will stop.[1]
Let's study the evaluation of an example expression:
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 evaluated the doublings immediately after each recursive call of doubleList.[2]
Haskell uses this flexibility on evaluation order in some important ways. As a pure functional programming language, the compiler makes most of the decisions about when to actually evaluate things. As a lazy language, Haskell usually defers evaluation until a final value is needed (which may sometimes never occur).[3] From the programmer's point of view, evaluation order rarely matters.[4]
Generalizing
To triple each element in a list, we could follow the same strategy as with doubleList
:
tripleList :: [Integer] -> [Integer]
tripleList [] = []
tripleList (n:ns) = (3 * n) : tripleList ns
But we don't want to write a new list-multiplying function for every different multiplier (such as multiplying the elements of a list by 4, 8, 17 etc.). So, let's make a general function to allow multiplication by any number. Our new function will take two arguments: the multiplicand as well as a list of Integer
s to multiply:
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 we ignore that argument instead of giving it a name (like m
, n
, or ns
).
We can test multiplyList
to see that it works as expected:
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
In this chapter, we started with a function constrained to multiplying the elements by 2
. Then, we recognized that we could avoid hard-coding a new function for each multiplicand by making multiplyList
to easily use any Integer
. Now, what if we wanted a different operator such as addition or to compute the square of each element?
We can generalize still further using a key functionality of Haskell. However, because the solution can seem 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. The function thus returned, then, takes a list of Integer
s and returns another list of Integer
s.
Consider our old doubleList
function redefined in terms of multiplyList
:
doubleList :: [Integer] -> [Integer]
doubleList xs = multiplyList 2 xs
Writing this way, we can clearly cancel out the `xs`:
doubleList = multiplyList 2
This definition style (with no argument variables) is called point-free style. Our definition now says that applying only one argument to multiplyList
doesn't fail to evaluate, rather it gives us a more specific function of type [Integer] -> [Integer]
instead of finishing with a final [Integer]
value.
We now see that functions in Haskell behave much like any other value. Functions can return other functions, and functions can stand alone as objects without mentioning their arguments. Functions seem almost like normal constants. Can we use functions themselves as arguments even? Yes, and that's the key to the next step in generalizing multiplyList
. We need a function that takes 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 thus use this generalized function to redefine multiplyList
:
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = applyToIntegers ((*) m)
That uses the (*)
function with a single initial argument to create a new function which is ready to take one more argument (which, in this use case, will come from the numbers in a given list).
Currying
If all this abstraction confuses 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 a second argument and multiplies that by 5. So, for our example, we then give the 7 as an argument to the 5* function, and that returns us our final evaluated number (35).
So, all functions in Haskell really take only one argument. However, when we know how many intermediate functions we will generate to reach a final result, we can treat functions as if they take many arguments. The number of arguments we generally talk about functions taking is actually the number of one-argument functions we get between the first argument and a final, non-functional result value.
The process of creating intermediate functions when feeding arguments into a complex function is called currying (named after Haskell Curry, also the namesake of the Haskell programming language).
The map
function
While applyToIntegers
has type (Integer -> Integer) -> [Integer] -> [Integer]
, the definition itself contains nothing specific to integers. To use the same logic with other types of lists, we could define versions such as applyToChars
, applyToStrings
and so on. They would all have the same definition but different type signatures. We can avoid all that redundancy with the final step in generalizing: making a fully polymorphic version with signature (a -> b) -> [a] -> [b]
. Prelude already has this function, and it is called map
:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
With map
, we can effortlessly implement functions as different as...
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = map ((*) m)
... 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 general solution for applying a function to each and every element of a list. Our original doubleList
problem was simply a specific version of map
. Functions like map
which take other functions as arguments are called higher-order functions. We will learn about more higher-order functions for list processing in the next chapter.
Exercises |
---|
|
Tips and Tricks
A few miscellaneous notes about lists in Haskell:
Dot Dot Notation
Haskell has a convenient shorthand for writing ordered lists of regularly-spaced 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 works with characters and even with floating point numbers. Unfortunately, floating-point numbers are problematic 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
Thanks to lazy evaluation, Haskell lists can 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 Ctrl-c).
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
Infinite lists are useful in practice because Haskell's lazy evaluation never actually evaluates more than it needs at any given moment. In most cases, we can treat an infinite list like an ordinary one. The program will only go into an infinite loop when evaluation requires all the values in the list. So, we can't sort or print an infinite list, but:
evens = doubleList [1..]
will define "evens" to be the infinite list [2,4,6,8..], and we can then pass "evens" into other functions that only need to evaluate part of the list for their final result. Haskell will know to only use the portion of the infinite list needed in the end.
Compared to hard-coding a long finite list, it's often more convenient to define an infinite list and then take the first few items. An infinite list can also be 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. It may be tempting to use head
and tail
due to simplicity and terseness, but it is too easy to forget that they fail on empty lists (and runtime crashes are never good). We do have a Prelude function, null :: [a] -> Bool
, which returns True
for empty lists and False
otherwise, so that provides a sane way of checking for empty lists without pattern matching; but matching an empty list tends to be cleaner and clearer than the corresponding if-then-else expression using null
.
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 may sometimes evaluate things sooner in order to 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
Lists III
Folds
Like map
, a fold is a higher order function that 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 look at a few concrete examples. sum
could be implemented as:
Example: sum
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
and product
as:
Example: product
product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs
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
All these examples show a pattern of recursion known as a fold. Think of the name referring to a list getting "folded up" into a single value or to a function being "folded between" the elements of the list.
Prelude defines four fold
functions: foldr
, foldl
, foldr1
and foldl1
.
foldr
The right-associative foldr
folds up a list from the right to left. As it proceeds, foldr uses the given function to combine each of the elements 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 to foldr
is a function with two arguments. The second argument is the value for the accumulator (which often starts at a neutral "zero" value). The third argument is the list to be folded.
In sum
, f
is (+)
, and acc
is 0
. In concat
, f
is (++)
and acc
is []
. In many cases (like all of our examples so far), the function passed to a fold will be one that takes two arguments of the same type, but this is not necessarily the case (as we can see from the (a -> b -> b)
part of the type signature — if the types had to be the same, the first two letters in the type signature would have matched).
Remember, a list in Haskell written as [a, b, c]
is an alternative (syntactic sugar) style for a : b : c : []
.
Now, foldr f acc xs
in the foldr
definition simply replaces each cons (:) in the xs
list with the function f
while replacing the empty list at the end with acc
:
foldr f acc (a:b:c:[]) = 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 (:) []
will 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 left-associative 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, parentheses in the resulting expression accumulate around the left end of the list:
foldl f acc (a:b:c:[]) = 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 fold-right-to-left and foldl as fold-left-to-right. The names refer to where the fold starts.
Note
Technical Note: foldl is tail-recursive, that is, it recurses
immediately, calling itself. For this reason the compiler will optimise it to a
simple loop for efficiency. However, Haskell is a lazy language, 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, we have a version of foldl called foldl'
that is strict — it forces the evaluation of f immediately at each step.
An apostrophe at the end of a function name is pronounced "tick" as in
"fold-L-tick" or "prime" as in "fold-L-prime". A tick is a valid character in Haskell identifiers.
foldl'
can be found in the Data.List
library module
(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.
Are foldl and foldr opposites?
You may notice that in some cases foldl
and foldr
do not appear to be opposites. Let's examine one such case, involving subtraction as the combining operation. Will we get True
or False
for each of the equalities below?
foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
Thinking of foldr
as going from right to left might lead us to suppose that the second equality would be true, as the rightmost elements show up before the leftmost ones. That, however, is not what we actually see:
GHCi> foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
False
This happens because the difference between foldr
and foldl
lies in the way the resulting expression is associated, and not in the left-to-right order of the elements of the list. Here is the expansion of the expressions above, with explicit parentheses:
foldl (-) 6 [3, 2, 1] == ((6 - 3) - 2) - 1 -- True
foldr (-) 6 [1, 2, 3] == 1 - (2 - (3 - 6)) -- True
Also note how the initial accumulator (6
in this example) is always found in the innermost parentheses.
For the sake of contrast, here is a simulated imperative style that does change the order of the elements in the list: [1]
GHCi> import Data.List -- So that we can give foldl' a try
GHCi> reduce f acc list = foldl' f acc list -- This is the same as plain old foldl'
GHCi> reduceRight f acc list = foldl' f acc (reverse list) -- keep foldl', but reverse list
Now we get True
in both cases from our initial example, because both are folding from the left:
GHCi> reduce (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> reduceRight (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
True
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
There is also a variant called foldr1
("fold - R - one") which dispenses with an explicit "zero" for an accumulator 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] = x
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 right-associative folds are more natural in Haskell than left-associative 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 needed and the compiler will know when to stop. 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 :: [Int] -> [Int]
echoes = foldr (\ x xs -> (replicate x x) ++ xs) []
GHCi> take 10 (echoes [1..])
[1,2,2,3,3,3,4,4,4,4]
(Note: This definition is compact thanks to the \ x xs ->
syntax. The \
, meant to look like a lambda (λ), works as an
unnamed function for cases where we won't use the function again anywhere
else. Thus, we provide the definition of our one-time function in situ. In
this case, x
and xs
are the arguments, and the
right-hand side of the definition is what comes after the ->
.)
We could have instead used a foldl:
echoes :: [Int] -> [Int]
echoes = foldl (\ xs x -> xs ++ (replicate x x)) []
GHCi> take 10 (echoes [1..]) -- not terminating
but only the foldr version works on infinite lists. What would happen if you just evaluate
echoes [1..]
? Try it! (If you try this in GHCi or a terminal, remember you can stop an evaluation with Ctrl-c, 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, map
itself can be implemented as a fold:
map :: (a -> b) -> [a] -> [b]
map f = foldr (\ x xs -> f x : xs) []
Folding takes some 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 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 returning a separate result for each item. A scan does both: it accumulates a value like a fold, but instead of returning only a final value it returns a list of all the intermediate values.
Prelude contains four scan functions:
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl
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]
scanl1
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 between scanl
and scanl1
. scanl1 (+) [1,2,3] = [1,3,6]
.
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr (+) 0 [1,2,3] = [6,5,3,0]
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 (+) [1,2,3] = [6,5,3]
These two functions are the counterparts of scanl
and scanl1
that accumulate the totals from the right.
Exercises |
---|
|
filter
A common operation performed on lists is filtering — generating a new list composed only of elements of the first list that meet a certain condition. A simple example: making a list of only even numbers from a list of integers.
retainEven :: [Int] -> [Int]
retainEven [] = []
retainEven (n:ns) =
-- mod n 2 computes the remainder for the integer division of n by 2.
if (mod n 2) == 0
then n : (retainEven ns)
else retainEven ns
This definition is somewhat verbose and specific. Prelude provides a concise and general filter
function with type signature:
filter :: (a -> Bool) -> [a] -> [a]
So, a (a -> Bool)
function tests an elements for some condition, we then feed in a list to be filtered, and we get back the filtered list.
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 to indicate that we know these are numbers and not just anything, but we can ignore that and use a more terse point-free definition:
retainEven = filter isEven
This is like what we demonstrated before for map
and the folds. Like filter
, those take another function as argument; and using them point-free emphasizes this "functions-of-functions" aspect.
List comprehensions
List comprehensions are syntactic sugar for some common list operations, such as filtering. For instance, instead of using the Prelude filter
, we could write retainEven
like this:
retainEven es = [n | n <- es, isEven n]
This compact syntax may look intimidating, 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 [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 comma-separated 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
functionalities of map
and filter
.
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 drawn from [1..4]
and the second from [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)]
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 |
---|
|
Notes
- ↑ The
reduce
andreduceRight
functions are taken from JavaScript, and they behave in this manner.
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, that is, alternative names for existing types.
- The newtype declaration, which defines new data types equivalent to existing ones.
In this chapter, we will study data and type. In a later chapter, we will discuss newtype and see where it can be useful.
data
and constructor functions
data is used to define new data types mostly 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 have 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, year, month and day 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 piece-wise.
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 vice-versa: 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]
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 kick-start 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.
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 non-empty 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 without binding (wildcard, "don't care" pattern).
In the (x:xs)
pattern, x
and xs
can be seen as sub-patterns 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 one-element 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 right-hand 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 non-empty 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 left-hand 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 catch-all second definition provides a reasonable default[1] 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 piece-wise 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[2] 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 non-empty 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
As-patterns
Sometimes, when matching a sub-pattern within a value, it may be useful to bind a name to the whole value being matched. As-patterns 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 as-patterns 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 Lists III, but this time using an as-pattern. |
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
x = Baz2 1 "Haskell" -- construct by declaration order, try ":t Baz2" in GHCi
y = Baz2 {bazName = "Curry", bazNumber = 2} -- construct by name
h x -- 7
h y -- 5
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 in more details 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 left-hand 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 .
Lambda abstractions
Pattern matching can be used directly in lambda abstractions:
swap = \(x,y) -> (y,x)
It is clear, however, that this syntax permits only one pattern (or one for each argument in the case of a multi-argument lambda abstraction).
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.[3] 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.[4]
do
blocks
Within a do
block like the ones we used in the Simple input and output chapter, we can pattern match with the left-hand 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
- ↑ 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 constructor-based. 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 key-value 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 <true-value> else <false-value>
<condition> is an expression which evaluates to a boolean. If the <condition> is True then the <true-value> is returned, otherwise the <false-value> 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, <true-value> and <false-value> 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 top-level 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 catch-all, 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 pattern-matched 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 one-line if
expressions would be hard to read, making let
and where
attractive options in such cases.
Short-circuit operators
The ||
and &&
operators mentioned before are in fact control structures: they evaluate the first argument and then the second argument only if needed.
Avoiding excessive effort
For instance, suppose a large number n is to be checked to determine if it is a prime number and a function isPrime is available, but alas, it requires a lot of computation to evaluate. Using the function \n -> n == 2 || (n `mod` 2 /= 0 && isPrime n)
will help if there are to be many evaluations with even values of n.
Avoidance of error conditions
&&
can be used to avoid signalling a run-time error, such as divide-by-zero or index-out-of-bounds, etc. For instance, the following locates the last non-zero element of a list:
lastNonZero a = go a (length a-1)
where
go a l | l >= 0 && a !! l == 0 = go a (l-1)
| l < 0 = Nothing
| otherwise = Just (a !! l)
Should all elements of the list be zero, the loop will work down to l = -1
, and in this case the condition in the first guard will be evaluated without attempting to dereference element -1, which does not exist.
case expressions
One control structure we haven't talked about yet is case
expressions. They are to piece-wise function definitions what if
expressions are to guards. Take this simple piece-wise 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 right-hand side of the corresponding equal sign (in the piece-wise 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 piece-wise 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 human-readable 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 if-expression (with a condition of null str
to pick the empty string case).
Finally, just like if
expressions (and unlike piece-wise 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 expression 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 putStrLn "You Win!"
We can write the same doGuessing
function using a case
expression. 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 if-else 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
expressions (unlike if
expressions) 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 putStrLn "Too low!"
doGuessing num
else do putStrLn "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 expression 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 expression 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 Shangri-La"
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
expressions 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 self-contained, 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 then-branch 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 one-off 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 non-space 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 non-alphanumeric 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 set-difference 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 Lists II:
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
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 higher-order 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 higher-order functions when discussing map
in Lists II. 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 well-known 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 in-place 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 pseudo-dictionary 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 dictionary-like 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 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 higher-order 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 case-insensitive version is left as an exercise!
insensitive = ...
-- How can we do case-insensitive 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"] . |
Higher-Order Functions and Types
A reader requests clarification of this page's material to reduce confusion. You can help clarify material, request assistance, or view current progress. |
The concept of currying (the generating of intermediate functions on the way toward a final result) was first introduced in the earlier chapter "Lists II". 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 higher-order 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 right-associative. Thus, our erroneous type signature a -> a -> Ordering -> [a] -> [a]
means the same thing as a -> (a -> (Ordering -> ([a] -> [a])))
.
Given that ->
is right-associative, 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 general-purpose higher-order 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 point-free 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 higher-order function.
Composition
The (.)
composition operator is another higher-order function. It has the signature:
(.) :: (b -> c) -> (a -> b) -> a -> c
(.)
takes two functions as arguments and returns a new function which applies the second function to the argument and then the first. (Writing the type of (.)
as (b -> c) -> (a -> b) -> (a -> c)
can make that easier to see.)
Composition and higher-order 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 one-line implementation for inits
(written point-free for extra dramatic effect) using only the following higher-order 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 mile-long (.)
chains, things will get confusing; but, when deployed reasonably, these point-free 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 higher-order ones and their functional arguments — take care of such plumbing.
Application
($)
is a curious higher-order 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 non-point-free 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 higher-order functions themselves, are most often used as arguments to higher-order 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 higher-order 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
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 auto-complete 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.
Multi-line 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 multi-line 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 multi-line 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 lower-case 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 comma-separation:
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 compile-time 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 far-left edge) makes a difference to the interpretation of the layout.
Things get more complicated when the beginning of an expression is not at the start of a line. In this case, it's safe to just indent further than the line containing the expression's beginning. In the following example, do
comes at the end of a line, so the subsequent parts of the expression simply need to be indented relative to the line that contains the do
, not relative to the do
itself.
myFunction firstArgument secondArgument = do
foo
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 "one-dimensional" languages like C. Even though the consensus among Haskell programmers is that meaningful indentation leads to better-looking 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 one-liners 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 weird-looking 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
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 made-up 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 value 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 object-oriented 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 pre-existing 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
command-line 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 = Configuration { 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 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 is 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 Lists II and Lists III, 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:
-- Pseudo-Haskell, 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 Classes and types. 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 list-map
uses a call to itself on the tail of the list (recursion), 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 re-reading 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. With a non-empty list, the first element is combined (with f
) with the result of folding the tail of the list, and so the fold proceeds until we get to the empty list.
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 empty-list 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
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, contrived 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 element-by-element...
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 clearly. 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 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