Yet Another Haskell Tutorial/Language basics
In this chapter we present the basic concepts of Haskell. In addition to familiarizing you with the interactive environments and showing you how to compile a basic program, we introduce the basic syntax of Haskell, which will probably be quite alien if you are used to languages like C and Java.
However, before we talk about specifics of the language, we need to establish some general properties of Haskell. Most importantly, Haskell is a lazy language, which means that no computation takes place unless it is forced to take place when the result of that computation is used.
This means, for instance, that you can define infinitely large data structures, provided that you never use the entire structure. For instance, using imperative-esque pseudo-code, we could create an infinite linked-list containing the number in each position by doing something like:
List makeList() { List current = new List(); current.value = 1; current.next = makeList(); return current; }
By looking at this code, we can see what it's trying to do: it creates
a new list, sets its value to and then recursively calls itself to
make the rest of the list. Of course, if you actually wrote this code
and called it, the program would never terminate, because makeList
would keep calling itself ad infinitum.
This is because we assume this imperative-esque language is strict, the opposite of lazy. Strict languages are often referred to as "call by value," while lazy languages are referred to as "call by name." In the above pseudo-code, when we "run" makeList on the fifth line, we attempt to get a value out of it. This leads to an infinite loop.
The equivalent code in Haskell is:
makeList = 1 : makeList
This program reads: we're defining something called makeList
(this is what goes on the left-hand side of the equals sign). On the
right-hand side, we give the definition of makeList
. In Haskell,
the colon operator is used to create lists (we'll talk more about this
soon). This right-hand side says that the value of
makeList
is the element 1
stuck on to the beginning of the
value of makeList
.
However, since Haskell is lazy (or "call by name"), we do not
actually attempt to evaluate what makeList
is at this point: we
simply remember that if ever in the future we need the second element
of makeList
, we need to just look at makeList
.
Now, if you attempt to write makeList
to a file, print it to the
screen, or calculate the sum of its elements, the operation won't
terminate because it would have to evaluate an infinitely long list.
However, if you simply use a finite portion of the list (say the first
elements), the fact that the list is infinitely long doesn't
matter. If you only use the first elements, only the first
elements are ever calculated. This is laziness.
Second, Haskell is case-sensitive. Many languages are, but Haskell actually uses case to give meaning. Haskell distinguishes between values (for instance, numbers: ); strings: "abc", "hello", ...; characters: 'a', 'b', ' ', ...; even functions (for instance, the function that squares a value, or the square-root function); and types (the categories to which values belong).
By itself, this is not unusual. Most languages have some system of
types. What is unusual is that Haskell requires that the names
given to functions and values begin with a lower-case letter and that
the names given to types begin with an upper-case letter. The moral
is: if your otherwise correct program won't compile, be sure you
haven't named your function Foo
, or something else beginning with
a capital letter.
Being a functional language, Haskell eschews side effects. A side effect is essentially something that happens in the course of executing a function that is not related to the output produced by that function.
For instance, in a language like C or Java, you are able to modify "global" variables from within a function. This is a side effect because the modification of this global variable is not related to the output produced by the function. Furthermore, modifying the state of the real world is considered a side effect: printing something to the screen, reading a file, etc., are all side effecting operations.
Functions that do not have side effects are called pure. An easy test for whether or not a function is pure is to ask yourself a simple question: "Does this function's result depend only on the arguments it receives, and is returning a result the only thing it does?"
All of this means that if you're used to writing code in an imperative
language (like C or Java), you're going to have to start thinking
differently. Most importantly, if you have a value x
, you must
not think of x
as a register, a memory location or
anything else of that nature. x
is simply a name, just as
"Hal" is my name. You cannot arbitrarily decide to store a
different person in my name any more than you can arbitrarily decide
to store a different value in x
. This means that code that
might look like the following C code is invalid (and has no
counterpart) in Haskell:
int x = 5; x = x + 1;
A call like x = x + 1 is called destructive update because we are destroying whatever was in x before and replacing it with a new value. Destructive update does not exist in Haskell.
By not allowing destructive updates
(or any other such side effecting operations), Haskell code is very
easy to comprehend. That is, when we define a function f
, and
call that function with a particular argument a
in the beginning
of a program, and then, at the end of the program, again call f
with the same argument a
, we know we will get out the same
result. This is because we know that a
cannot have changed and
because we know that f
only depends on a
(for instance, it
didn't increment a global counter). This property is called
referential transparency and
basically states that if two functions f
and g
produce the
same values for the same arguments, then we may replace f
with
g
(and vice-versa).
Note
There is no agreed-upon exact definition of referential transparency. The definition given above is the one I like best. They all carry the same interpretation; the differences lie in how they are formalized.
Arithmetic
[edit | edit source]Let's begin our foray into Haskell with simple arithmetic. Start up your favorite interactive shell (Hugs or GHCi; see the chapter Getting started for installation instructions). The shell will output to the screen a few lines talking about itself and what it's doing and then should finish with the cursor on a line reading:
Example:
Prelude>
From here, you can begin to evaluate
expressions. An expression is basically
something that has a value. For instance, the number is an
expression (its value is ). Values can be built up from other
values; for instance, is an expression (its value is ). In
fact, most simple arithmetic operations are supported by Haskell,
including plus (+
), minus (-
), times (*
), divided-by
(/
), exponentiation (^
) and square-root (sqrt
).
You can experiment with these by asking the interactive shell to
evaluate expressions and to give you their value. In this way, a
Haskell shell can be used as a powerful calculator. Try some of the
following:
Example:
Prelude> 5*4+3 23 Prelude> 5^5-2 3123 Prelude> sqrt 2 1.4142135623730951 Prelude> 5*(4+3) 35
We can see that, in addition to the standard arithmetic operations, Haskell also allows grouping by parentheses, hence the difference between the values of 5*4+3 and 5*(4+3). The reason for this is that the "understood" grouping of the first expression is (5*4)+3, due to operator precedence.
Also note that parentheses aren't required around function arguments.
For instance, we simply wrote sqrt 2
, not sqrt(2)
, as would
be required in most other languages. You could write it with the
parentheses, but in Haskell, since function application is so common,
parentheses aren't required.
Even though parentheses are not always needed, sometimes it is better to leave them in anyway; other people will probably have to read your code, and if extra parentheses make the intent of the code clearer, use them. |
Now try entering 2^5000. Does it work?
Note
If you're familiar with programming in other languages, you may find it odd that sqrt 2 comes back with a decimal point (i.e., is a floating point number) even though the argument to the function seems to be an integer. This interchangability of numeric types is due to Haskell's system of type classes and will be discussed in detail in the section on Classes).
Exercises |
---|
We've seen that multiplication binds more tightly than addition. Can you think of a way to determine whether function application binds more or less tightly than multiplication? |
Pairs, Triples and More
[edit | edit source]In addition to single values, we should also address multiple values. For instance, we may want to refer to a position by its / coordinate, which would be a pair of integers. To make a pair of integers is simple: you enclose the pair in parenthesis and separate them with a comma. Try the following:
Example:
Prelude> (5,3) (5,3)
Here, we have a pair of integers, and . In Haskell, the first element of a pair need not have the same type as the second element: that is, pairs are allowed to be heterogeneous. For instance, you can have a pair of an integer with a string. This contrasts with lists, which must be made up of elements of all the same type (we will discuss lists further in the section on Lists).
There are two predefined functions that allow you to extract the
first and second elements of a pair. They are, respectively, fst
and snd
. You can see how they work below:
Example:
Prelude> fst (5, "hello") 5 Prelude> snd (5, "hello") "hello"
In addition to pairs, you can define triples, quadruples etc. To define a triple and a quadruple, respectively, we write:
Example:
Prelude> (1,2,3) (1,2,3) Prelude> (1,2,3,4) (1,2,3,4)
And so on. In general, pairs, triples, and so on are called tuples and can store fixed amounts of heterogeneous data.
Note
The functions fst
and snd
won't work on anything longer than
a pair; if you try to use them on a larger tuple, you will get a
message stating that there was a type error. The meaning of this
error message will be explained in the chapter Type basics.
Exercises |
---|
Use a combination of fst and snd to extract the character ((1,'a'),"foo") . |
Lists
[edit | edit source]The primary limitation of tuples is that they hold only a fixed number of elements: pairs hold two, triples hold three, and so on. A data structure that can hold an arbitrary number of elements is a list. Lists are assembled in a very similar fashion to tuples, except that they use square brackets instead of parentheses. We can define a list like:
Example:
Prelude> [1,2] [1,2] Prelude> [1,2,3] [1,2,3]
Lists don't need to have any
elements. The empty list is simply []
.
Unlike tuples, we can very easily add an element on to the beginning of the list using the colon operator. The colon is called the "cons" operator; the process of adding an element is called "consing." The etymology of this is that we are constructing a new list from an element and an old list. We can see the cons operator in action in the following examples:
Example:
Prelude> 0:[1,2] [0,1,2] Prelude> 5:[1,2,3,4] [5,1,2,3,4]
We can actually build any list by using the cons operator (the colon) and the empty list:
Example:
Prelude> 5:1:2:3:4:[] [5,1,2,3,4]
In fact, the [5,1,2,3,4]
syntax is "syntactic
sugar" for the expression using the explicit
cons operators and empty list. If we write something using the
[5,1,2,3,4]
notation, the compiler simply translates it to the
expression using (:)
and []
.
Note
In general, "syntactic sugar" is a strictly unnecessary language feature, which is added to make the syntax nicer.
One further difference between lists and tuples is that, while tuples are heterogeneous, lists must be homogeneous. This means that you cannot have a list that holds both integers and strings. If you try to, a type error will be reported.
Of course, lists don't have to just contain integers or strings; they can also contain tuples or even other lists. Tuples, similarly, can contain lists and other tuples. Try some of the following:
Example:
Prelude> [(1,1),(2,4),(3,9),(4,16)] [(1,1),(2,4),(3,9),(4,16)] Prelude> ([1,2,3,4],[5,6,7]) ([1,2,3,4],[5,6,7])
There are two basic list functions:
head
and tail
. The head
function returns the first
element of a (non-empty) list, and the tail
function returns all
but the first element of a (non-empty) list.
To get the length of a list, you use the length
function:
Example:
Prelude> length [1,2,3,4,10] 5 Prelude> head [1,2,3,4,10] 1 Prelude> length (tail [1,2,3,4,10]) 4
Strings
[edit | edit source]In Haskell, a String
is simply a list of Char
s. So, we can
create the string "Hello" as:
Example:
Prelude> 'H':'e':'l':'l':'o':[] "Hello"
Lists (and, of course, strings) can
be concatenated using the ++
operator:
Example:
Prelude> "Hello " ++ "World" "Hello World"
Additionally, non-string values can be converted to strings using the
show
function, and strings can be converted to non-string values
using the read
function. Of course, if you try to read a value
that's malformed, an error will be reported (note that this is a
run-time error, not a compile-time error):
Example:
Prelude> "Five squared is " ++ show (5*5) "Five squared is 25" Prelude> read "5" + 3 8 Prelude> read "Hello" + 3 Program error: Prelude.read: no parse
In the above, the exact error message is implementation dependent. However,
the interpreter has inferred that you're trying to add three to
something. This means that when we execute read "Hello"
, we
expect to be returned a number. However, "Hello"
cannot be
parsed as a number, so an error is reported.
Simple List Functions
[edit | edit source]Much of the computation in Haskell programs is done by processing
lists. There are three primary list-processing functions: map
,
filter
and foldr
(also foldl
).
The map
function takes as arguments a list of values and a
function that should be applied to each of the values. It returns the result of this
application. For instance,
there is a built-in function Data.Char.toUpper
that takes as input a
Char
and produces a Char
that is the upper-case version of
the original argument. So, to convert an entire string (which is
simply a list of characters) to upper case, we can map the
toUpper
function across the entire list:
Example:
Prelude> map Data.Char.toUpper "Hello World" "HELLO WORLD"
Hugs users: Hugs doesn't like qualified names like Data.Char.toUpper .
In Hugs, simply use toUpper . If toUpper is undefined, use :load Data.Char |
When you map across a list, the length of the list never changes --
only the individual values in the list change.
To remove elements from the list, you can use the filter
function. This function allows you to remove certain elements from a
list depending on their value, but not on their context. For instance,
the function Data.Char.isLower
tells you whether a given character is lower
case. We can filter out all non-lowercase characters using this:
Example:
Prelude> filter Data.Char.isLower "Hello World" "elloorld"
The function foldr
takes a little more getting used to.
foldr
takes three arguments: a function, an initial value and a
list. The best way to think about foldr
is that it replaces
occurrences of the list cons operator (:
) with the function
parameter and replaces the empty list constructor ([]
) with the
initial value. Thus, if we have a list:
3 : 8 : 12 : 5 : []
and we apply foldr (+) 0
to it, we get:
3 + 8 + 12 + 5 + 0
which sums the list. We can test this:
Example:
Prelude> foldr (+) 0 [3,8,12,5] 28
We can perform the same sort of operation to calculate the product of all the elements on a list:
Example:
Prelude> foldr (*) 1 [4,8,5] 160
We said earlier that folding is like
replacing (:
) with a particular function and ([]
) with an
initial element. This raises a question as to what happens when the
function isn't associative (a function () is associative if ). When we write , we need to specify where to put the parentheses.
Namely, do we mean or ? foldr
assumes the function is
right-associative (i.e., the correct bracketing is the latter). Thus,
when we use it on a non-associative function (like minus), we can see
the effect:
Example:
Prelude> foldr (-) 1 [4,8,5] 0
The exact derivation of this looks something like:
foldr (-) 1 [4,8,5] ==> 4 - (foldr (-) 1 [8,5]) ==> 4 - (8 - foldr (-) 1 [5]) ==> 4 - (8 - (5 - foldr (-) 1 [])) ==> 4 - (8 - (5 - 1)) ==> 4 - (8 - 4) ==> 4 - 4 ==> 0
The foldl
function goes the other way and effectively produces
the opposite bracketing. foldl
looks the same when applied, so
we could have done summing just as well with foldl
:
Example:
Prelude> foldl (+) 0 [3,8,12,5] 28
However, we get different results when using the non-associative function minus:
Example:
Prelude> foldl (-) 1 [4,8,5] -16
This is because foldl
uses the opposite bracketing. The way it
accomplishes this is essentially by going all the way down the list,
taking the last element and combining it with the initial value via
the provided function. It then takes the second-to-last element in
the list and combines it to this new value. It does so until there is
no more list left.
The derivation here proceeds in the opposite fashion:
foldl (-) 1 [4,8,5] ==> foldl (-) (1 - 4) [8,5] ==> foldl (-) ((1 - 4) - 8) [5] ==> foldl (-) (((1 - 4) - 8) - 5) [] ==> ((1 - 4) - 8) - 5 ==> ((-3) - 8) - 5 ==> (-11) - 5 ==> -16
Note that once the foldl
goes away, the parenthesization is
exactly the opposite of the foldr
.
Note
foldl
is often more efficient than foldr
for reasons that we
will discuss in the section on Lists. However,
foldr
can work on infinite lists, while foldl
cannot. This
is because before foldl
does anything, it has to go to the end of
the list. On the other hand, foldr
starts producing output
immediately. For instance, foldr (:) [] [1,2,3,4,5]
simply
returns the same list. Even if the list were infinite, it would
produce output. A similar function using foldl
would fail to
produce any output.
If this discussion of the folding functions is still somewhat unclear, that's okay. We'll discuss them further in the section on Lists.
Exercises |
---|
Use [True,False,False,True,True] . |
Exercises |
---|
Use the functions mentioned in this section (you will need two of them) to compute the number of lower-case letters in a string. For instance, on "aBCde" it should return 3. |
Exercises |
---|
We've seen how to calculate sums and products using folding functions.
Given that the function |
Exercises |
---|
Write a function that takes a list of pairs of length at least
2 and returns the first component of the second element in the list.
So, when provided with |
Source Code Files
[edit | edit source]As programmers, we don't want to simply evaluate small expressions like these -- we want to sit down, write code in our editor of choice, save it and then use it.
We already saw in the sections Ghc and Nhc how to write a Hello World program and how to compile it. Here, we show how to use functions defined in a source-code file in the interactive environment. To do this, create a file called Test.hs and enter the following code:
module Test where x = 5 y = (6, "Hello") z = x * fst y
This is a very simple "program" written in Haskell. It defines a module called "Test" (in general module names should match file names; see the section on Modules for more on this). In this module, there are three definitions: x, y and z. Once you've written and saved this file, in the directory in which you saved it, load this in your favorite interpreter, by executing either of the following:
Example:
% hugs Test.hs % ghci Test.hs
This will start Hugs or GHCi, respectively, and load the file. Alternatively, if you already have one of them loaded, you can use the ":load" command (or just ":l") to load a module, as:
Example:
Prelude> :l Test.hs ... Test>
Between the first and last line, the interpreter will print various data to explain what it is doing. If any errors appear, you probably mistyped something in the file; double check and then try again.
You'll notice that where it used to say "Prelude" it now says
"Test." That means that Test is the current module. The Prelude module (usually simply referred to as "the
Prelude") is always loaded and contains the
standard definitions (for instance, the (:
) operator for lists,
or (+
) or (*
), fst
, snd
and so on).
Now that we've loaded Test, we can use things that were defined in it. For example:
Example:
Test> x 5 Test> y (6,"Hello") Test> z 30
Perfect, just as we expected!
One final issue regarding how to compile programs to stand-alone
executables remains. In order for a program to be an executable, it
must have the module name "Main" and must contain a function
called main
. So, if you go in to Test.hs and rename it to
"Main" (change the line that reads module Test
to module
Main
), we simply need to add a main function. Try this:
main = putStrLn "Hello World"
Now, save the file, and compile it (refer back to the section on Getting started for information on how to do this for your compiler). For example, in GHC, you would say:
Example:
% ghc --make Test.hs -o test
Note
For Windows, it would be "-o test.exe"
This will create a file called "test" (or on Windows, "test.exe") that you can then run.
Example:
% ./test Hello World
Note
Or, on Windows:
Example:
C:\> test.exe Hello World
Functions
[edit | edit source]Now that we've seen how to write code in a file, we can start writing functions. As you might have expected, functions are central to Haskell, as it is a functional language. This means that the evaluation of a program is simply the evaluation of a function.
We can write a simple function to square a number and enter it into our Test.hs file. We might define this as follows:
square x = x * x
In this function definition, we say that we're defining a function
square
that takes one argument (aka parameter), which we call
x
. We then say that the value of square x
is equal
to x * x
.
Haskell also supports standard conditional expressions. For instance, we could define a function that returns if its argument is less than ; if its argument is ; and if its argument is greater than (this is called the signum function):
signum x = if x < 0 then -1 else if x > 0 then 1 else 0
You can experiment with this as:
Example:
Test> signum 5 1 Test> signum 0 0 Test> signum (5-10) -1 Test> signum (-1) -1
Note that the parenthesis around "-1" in the last example are required; if missing, the system will think you are trying to subtract the value "1" from the value "signum," which is illtyped.
The if/then/else construct in Haskell is very similar to that of most
other programming languages; however, you must have both a
then and an else
clause. It evaluates the condition (in this case and, if this
evaluates to True
, it evaluates the then clause; if the
condition evaluated to False
, it evaluates the else
clause).
You can test this program by editing the file and loading it back into your interpreter. If Test is already the current module, instead of typing :l Test.hs again, you can simply type :reload or just :r to reload the current file. This is usually much faster.
Haskell, like many other languages, also supports case constructions. These are used when there are multiple values that you want to check against (case expressions are actually quite a bit more powerful than this -- see the section on Pattern matching for all of the details).
Suppose we wanted to define a function that had a value of if its
argument were ; a value of if its argument were ; a value of
if its argument were ; and a value of in all other
instances. Writing this function using if statements would be
long and very unreadable; so we write it using a case statement
as follows (we call this function f
):
f x = case x of 0 -> 1 1 -> 5 2 -> 2 _ -> -1
In this program, we're defining f
to take an argument x
and
then inspect the value of x
. If it matches , the value of
f
is . If it matches , the value of f
is . If it
maches , then the value of f
is ; and if it hasn't matched
anything by that point, the value of f
is (the underscore
can be thought of as a "wildcard" -- it will match
anything) .
The indentation here is important. Haskell uses a system called "layout" to structure its code (the programming language Python uses a similar system). The layout system allows you to write code without the explicit semicolons and braces that other languages like C and Java require.
Because whitespace matters in Haskell, you need to be careful about whether you are using tabs or spaces. If you can configure your editor to never use tabs, that's probably better. If not, make sure your tabs are always 8 spaces long, or you're likely to run in to problems. |
The general rule for layout is that an open-brace is inserted after the keywords where, let, do and of, and the column position at which the next command appears is remembered. From then on, a semicolon is inserted before every new line that is indented the same amount. If a following line is indented less, a close-brace is inserted. This may sound complicated, but if you follow the general rule of indenting after each of those keywords, you'll never have to remember it (see the section on Layout for a more complete discussion of layout).
Some people prefer not to use layout and write the braces and semicolons explicitly. This is perfectly acceptable. In this style, the above function might look like:
f x = case x of { 0 -> 1 ; 1 -> 5 ; 2 -> 2 ; _ -> -1 }
Of course, if you write the braces and semicolons explicitly, you're free to structure the code as you wish. The following is also equally valid:
f x = case x of { 0 -> 1 ; 1 -> 5 ; 2 -> 2 ; _ -> -1 }
However, structuring your code like this only serves to make it unreadable (in this case).
Functions can also be defined piece-wise, meaning that you can write
one version of your function for certain parameters and then another
version for other parameters. For instance, the above function f
could also be written as:
f 0 = 1 f 1 = 5 f 2 = 2 f _ = -1
Here, the order is important. If we had put the last line first, it
would have matched every argument, and f
would return -1
,
regardless of its argument (most compilers will warn you about this,
though, saying something about overlapping patterns). If we had not
included this last line, f
would produce an error if anything
other than 0, 1 or 2 were applied to it (most compilers will warn you
about this, too, saying something about incomplete patterns). This
style of piece-wise definition is very popular and will be used quite
frequently throughout this tutorial. These two definitions of f
are actually equivalent -- this piece-wise version is translated into
the case expression.
More complicated functions can be built from simpler functions using
function composition. Function composition is simply taking
the result of the application of one function and using that as an
argument for another. We've already seen this way back in arithmetic
(the section on Arithmetic), when we wrote 5*4+3
.
In this, we were evaluating and then applying to the
result. We can do the same thing with our square
and f
functions:
Example:
Test> square (f 1) 25 Test> square (f 2) 4 Test> f (square 1) 5 Test> f (square 2) -1
The result of each of these function applications is fairly
straightforward. The parentheses around the inner function are
necessary; otherwise, in the first line, the interpreter would think
that you were trying to get the value of "square f
," which has
no meaning. Function application like this is fairly standard in most
programming languages. There is another, more mathematically
oriented, way to express function composition, using the (.
)
(just a single period) function. This (.
) function is supposed
to look like the () operator in mathematics.
Note
In mathematics we write to mean "f following g," in
Haskell we write f . g
also to mean "f following g."
The meaning of is simply that . That is, applying the value to the function is the same as applying it to , taking the result, and then applying that to .
The (.
) function
(called the function composition
function), takes two functions and makes them in to one. For
instance, if we write (square . f)
, this means that it creates a new
function that takes an argument, applies f
to that argument and
then applies square
to the result. Conversely, (f . square)
means that it creates a new function that takes an argument, applies
square
to that argument and then applies f
to the result.
We can see this by testing it as before:
Example:
Test> (square . f) 1 25 Test> (square . f) 2 4 Test> (f . square) 1 5 Test> (f . square) 2 -1
Here, we must enclose the function composition in parentheses;
otherwise, the Haskell compiler will think we're trying to compose
square
with the value f 1
in the first line, which makes no
sense since f 1
isn't even a function.
It would probably be wise to take a little time-out to look at some of the functions that are defined in the Prelude. Undoubtedly, at some point, you will accidentally rewrite some already-existing function (I've done it more times than I can count), but if we can keep this to a minimum, that would save a lot of time. Here are some simple functions, some of which we've already seen:
sqrt |
the square root function |
id |
the identity function: id x = x
|
fst |
extracts the first element from a pair |
snd |
extracts the second element from a pair |
null |
tells you whether or not a list is empty |
head |
returns the first element on a non-empty list |
tail |
returns everything but the first element of a non-empty list |
++ |
concatenates two lists |
== |
checks to see if two elements are equal |
/= |
checks to see if two elements are unequal |
Here, we show example usages of each of these functions:
Example:
Prelude> sqrt 2 1.41421 Prelude> id "hello" "hello" Prelude> id 5 5 Prelude> fst (5,2) 5 Prelude> snd (5,2) 2 Prelude> null [] True Prelude> null [1,2,3,4] False Prelude> head [1,2,3,4] 1 Prelude> tail [1,2,3,4] [2,3,4] Prelude> [1,2,3] ++ [4,5,6] [1,2,3,4,5,6] Prelude> [1,2,3] == [1,2,3] True Prelude> 'a' /= 'b' True Prelude> head [] Program error: {head []}
We can see that applying head
to an empty list gives an error
(the exact error message depends on whether you're using GHCi or
Hugs -- the shown error message is from Hugs).
Let Bindings
[edit | edit source]Often we wish to provide local declarations for use in our functions. For instance, the following equation is used to find the roots (zeros) of a polynomial of the form : . 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))
Unfortunately, we duplicate expressions here. To remedy this problem,
Haskell allows for local bindings. That is,
we can create values inside of a function that only that function can
see. For instance, we could create a local binding for the expression
sqrt(b*b-4*a*c)
, calling it discr
for discriminant, and then use that in
both places where sqrt(b*b - 4*a*c)
occurred. We can do this using
a let/in declaration:
roots a b c = let discr = sqrt (b*b - 4*a*c) in ((-b + discr) / (2*a), (-b - discr) / (2*a))
In fact, you can provide multiple declarations inside a let. Just make sure they're indented the same amount, or you will have layout problems:
roots a b c = let discr = sqrt (b*b - 4*a*c) twice_a = 2*a in ((-b + discr) / twice_a, (-b - discr) / twice_a)
Infix
[edit | edit source]Infix functions are ones that are composed of symbols, rather than
letters. For instance, (+)
, (*)
, (++)
are all infix
functions. You can use them in non-infix mode by enclosing them in
parentheses. Hence, the two following expressions are the same:
Example:
Prelude> 5 + 10 15 Prelude> (+) 5 10 15
Similarly, non-infix functions (like map
) can be made infix by
enclosing them in backquotes (the ticks on the tilde key on American
keyboards):
Example:
Prelude> map Data.Char.toUpper "Hello World" "HELLO WORLD" Prelude> Data.Char.toUpper `map` "Hello World" "HELLO WORLD"
Hugs users: Hugs doesn't like qualified names like Data.Char.toUpper .
In Hugs, simply use toUpper . |
Comments
[edit | edit source]There are two types of comments in Haskell: line comments and block
comments. Line comments begin with the token --
and extend until
the end of the line. Block comments begin with {-
and extend to
a corresponding -}
. Block comments can be nested.
Note
The --
in Haskell corresponds to // in C++ or Java, and
{-
and -}
correspond to /* and */.
Comments are used to explain your program in English and are completely ignored by compilers and interpreters. For example:
module Test2 where main = putStrLn "Hello World" -- write a string -- to the screen {- f is a function which takes an integer and produces integer. {- this is an embedded comment -} the original comment extends to the matching end-comment token: -} f x = case x of 0 -> 1 -- 0 maps to 1 1 -> 5 -- 1 maps to 5 2 -> 2 -- 2 maps to 2 _ -> -1 -- everything else maps to -1
This example program shows the use of both line comments and (embedded) block comments.
Recursion
[edit | edit source]In imperative languages like C and Java, the most basic control structure is a loop (like a for loop). However, for loops don't make much sense in Haskell because they require destructive update (the index variable is constantly being updated). Instead, Haskell uses recursion.
A function is recursive if it calls itself (see the appendix on Recursion for more). Recursive functions exist also in C and Java but are used less than they are in functional languages. The prototypical recursive function is the factorial function. In an imperative language, you might write this as something like:
int factorial(int n) { int fact = 1; for (int i=2; i <= n; i++) fact = fact * i; return fact; }
While this code fragment will successfully compute factorials for positive integers, it somehow ignores the basic definition of factorial, usually given as:
This definition itself is exactly a recursive definition: namely the value of depends on the value of . If you think of as a function, then it is calling itself. We can translate this definition almost verbatim into Haskell code:
factorial 1 = 1 factorial n = n * factorial (n-1)
This is likely the simplest recursive function you'll ever see, but it is correct.
Note
Of course, an imperative recursive version could be written:
int factorial(int n) { if (n == 1) return 1; else return n * factorial(n-1); }
but this is likely to be much slower than the loop version in C.
Recursion can be a difficult thing to master. It is completely
analogous to the concept of induction in mathematics
(see the chapter Recursion for a more formal treatment of this).
However, usually a problem can be thought of as having one or more
base cases and one or more recursive-cases. In the case of
factorial
, there is one base case (when ) and one recursive
case (when ). For designing your own recursive algorithms, it is
often useful to try to differentiate these two cases.
Turning now to the task of exponentiation, suppose that we have two positive integers and , and that we want to calculate . This problem has a single base case: namely when is . The recursive case is when . We can write a general form as:
Again, this translates directly into Haskell code:
exponent a 1 = a exponent a b = a * exponent a (b-1)
Just as we can define recursive functions on integers, so can we
define recursive functions on lists. In this case, usually the base
case is the empty list []
, and the recursive case is a cons list
(i.e., a value consed on to another list).
Consider the task of calculating the length of a list. We can again break this down into two cases: either we have an empty list or we have a non-empty list. Clearly the length of an empty list is zero. Furthermore, if we have a cons list, then the length of this list is just the length of its tail plus one. Thus, we can define a length function as:
my_length [] = 0 my_length (x:xs) = 1 + my_length xs
Note
Whenever we provide alternative definitions for standard Haskell
functions, we prefix them with my_
so the compiler doesn't
become confused.
Similarly, we can consider the filter
function. Again, the base
case is the empty list, and the recursive case is a cons list.
However, this time, we're choosing whether to keep an element,
depending on whether or not a particular predicate holds. We can
define the filter function as:
my_filter p [] = [] my_filter p (x:xs) = if p x then x : my_filter p xs else my_filter p xs
In this code, when presented with an empty list, we simply return an empty list. This is because filter cannot add elements; it can only remove them.
When presented with a list of the form (x:xs)
, we need to decide
whether or not to keep the value x
. To do this, we use an
if statement and the predicate p
. If p x
is true, then
we return a list that begins with x
followed by the result of
filtering the tail of the list. If p x
is false, then we exclude
x
and return the result of filtering the tail of the list.
We can also define map
and both fold functions using explicit
recursion. See the exercises for the definition of map
and
the chapter Language advanced for the folds.
Exercises |
---|
The fibonacci sequence is defined by: Write a recursive function fib that takes a positive integer n as a parameter and calculates . |
Exercises |
---|
Define a recursive function mult that takes two positive integers a and b and returns a*b , but only uses addition (i.e., no fair just using multiplication). Begin by making a mathematical definition in the style of the previous exercise and the rest of this section. |
Exercises |
---|
Define a recursive function my_map that behaves identically to the standard function map . |
Interactivity
[edit | edit source]If you are familiar with books on other (imperative) languages, you might be wondering why you haven't seen many of the standard programs written in tutorials of other languages (like ones that ask the user for his name and then says "Hi" to him by name). The reason for this is simple: Being a pure functional language, it is not entirely clear how one should handle operations like user input.
After all, suppose you have a function that reads a string from the keyboard. If you call this function twice, and the user types something the first time and something else the second time, then you no longer have a function, since it would return two different values. The solution to this was found in the depths of category theory, a branch of formal mathematics: monads. We're not yet ready to talk about monads formally, but for now, think of them simply as a convenient way to express operations like input/output. We'll discuss them in this context much more in the chapter Io and then discuss monads for monads' sake in the chapter Monads.
Suppose we want to
write a function that's interactive. The way to do this is to use the
do keyword. This allows us to specify
the order of operations (remember that normally, since Haskell is a
lazy language, the order in which operations are evaluated in it is
unspecified). So, to write a simple program that asks a user for his
name and then address him directly, enter the following code into
"Name.hs":
module Main where import System.IO main = do hSetBuffering stdin LineBuffering putStrLn "Please enter your name: " name <- getLine putStrLn ("Hello, " ++ name ++ ", how are you?")
Note
The parentheses are required on the second instance of putStrLn
but not the first. This is because function application binds more tightly than
++
, so without the parentheses, the second would be
interpreted as (putStrLn "Hello, ") ++ name ++ ...
.
You can then either load this code in your
interpreter and execute main
by simply typing "main
," or
you can compile it and run it from the command line. I'll show the
results of the interactive approach:
Example:
Main> main Please enter your name: Hal Hello, Hal, how are you? Main>
And there's interactivity. Let's go back and look at the code a
little, though. We name the module "Main," so that we can compile
it. We name the primary function "main
," so that the compiler
knows that this is the function to run when the program is run. On
the fourth line, we import the IO
library, so that we can access
the IO functions. On the seventh line, we start with do, telling
Haskell that we're executing a sequence of commands.
The first command is hSetBuffering stdin
LineBuffering
, which you should probably ignore for now
(incidentally, this is only required by GHC -- in Hugs you can get by
without it). The necessity for this is because, when GHC reads input,
it expects to read it in rather large blocks. A typical person's name
is nowhere near large enough to fill this block. Thus, when we try to
read from stdin
, it waits until it's gotten a whole block. We
want to get rid of this, so we tell it to use LineBuffering
instead of block buffering.
The next command is putStrLn
, which prints a string to the
screen. On the ninth line, we say name <- getLine
. This
would normally be written name = getLine
, but using the arrow
instead of the equal sign shows that getLine
isn't a real
function and can return different values. This command means "run
the action getLine
, and store the results in name
."
The last line constructs a string using what we read in the previous line and then prints it to the screen.
Another example of a function that isn't really a function would be
one that returns a random value. In this context, a function that
does this is called randomRIO
. Using this, we can write a
"guess the number" program. Enter the following code into
"Guess.hs":
module Main where import System.IO import System.Random main = do hSetBuffering stdin LineBuffering num <- randomRIO (1::Int, 100) putStrLn "I'm thinking of a number between 1 and 100" doGuessing num doGuessing num = do putStrLn "Enter your guess:" guess <- getLine let guessNum = read guess if guessNum < num then do putStrLn "Too low!" doGuessing num else if guessNum > num then do putStrLn "Too high!" doGuessing num else do putStrLn "You Win!"
Let's examine this code. On the fifth line we write "import Random"
to tell the compiler that we're going to be using some random
functions (these aren't built into the Prelude). In the first line of
main
, we ask for a random number in the range . We need
to write ::Int
to tell the compiler that we're using integers
here -- not floating point numbers or other numbers. We'll talk more
about this in the section on Type basics. On the next line, we tell the
user what's going on, and then, on the last line of main
, we tell
the compiler to execute the command doGuessing
.
The doGuessing
function takes the number the user is trying to
guess as an argument. First, it asks the user to guess and then
accepts their guess (which is a String
) from the keyboard. The
if statement checks first to see if their guess is too low.
However, since guess
is a string, and num
is an integer, we
first need to convert guess
to an integer by read
ing it.
Since "read guess
" is a plain, pure function (and not an IO
action), we don't need to use the <-
notation (in fact, we
cannot); we simply bind the value to guessNum
. Note that while
we're in do notation, we don't need ins for lets.
If they guessed too low, we inform them and then start doGuessing
over again. If they didn't guess too low, we check to see if they
guessed too high. If they did, we tell them and start doGuessing
again. Otherwise, they didn't guess too low and they didn't guess too
high, so they must have gotten it correct. We tell them that they
won and exit. The fact that we exit is implicit in the fact that
there are no commands following this. We don't need an explicit
return ()
statement.
You can either compile this code or load it into your interpreter, and you will get something like:
Example:
Main> main I'm thinking of a number between 1 and 100 Enter your guess: 50 Too low! Enter your guess: 75 Too low! Enter your guess: 85 Too high! Enter your guess: 80 Too high! Enter your guess: 78 Too low! Enter your guess: 79 You Win!
The recursive action that we just saw doesn't actually return a value that we use in any way. In the case when it does, the "obvious" way to write the command is actually incorrect. Here, we will give the incorrect version, explain why it is wrong, then give the correct version.
Let's say we're writing a simple program that repeatedly asks the user to type in a few words. If at any point the user enters the empty word (i.e., he just hits enter without typing anything), the program prints out everything he's typed up until that point and then exits. The primary function (actually, an action) in this program is one that asks the user for a word, checks to see if it's empty, and then either continues or ends. The incorrect formulation of this might look something like:
askForWords = do putStrLn "Please enter a word:" word <- getLine if word == "" then return [] else return (word : askForWords)
Before reading ahead, see if you can figure out what is wrong with the above code.
The error is on the last line, specifically with the term word :
askForWords
. Remember that when using (:
), we are making a list
out of an element (in this case word
) and another list (in this
case, askForWords
). However, askForWords
is not a
list; it is an action that, when run, will produce a list. That means
that before we can attach anything to the front, we need to run the
action and take the result. In this case, we want to do something
like:
askForWords = do putStrLn "Please enter a word:" word <- getLine if word == "" then return [] else do rest <- askForWords return (word : rest)
Here, we first run askForWords
, take the result and store it in
the variable rest
. Then, we return the list created from
word
and rest
.
By now, you should have a good understanding of how to write simple functions, compile them, test functions and programs in the interactive environment, and manipulate lists.
Exercises |
---|
Write a program that will repeatedly ask the user for numbers until she types in zero, at which point it will tell her the sum of all the numbers, the product of all the numbers, and, for each number, its factorial. For instance, a session might look like: Example: Give me a number (or 0 to stop): 5 Give me a number (or 0 to stop): 8 Give me a number (or 0 to stop): 2 Give me a number (or 0 to stop): 0 The sum is 15 The product is 80 5 factorial is 120 8 factorial is 40320 2 factorial is 2 Hint: write an IO action that reads a number and, if it's zero, returns the empty list. If it's not zero, it recurses itself and then makes a list out of the number it just read and the result of the recursive call. Hint: You will need to make use of "show" to print a number. putStrLn("Number " ++ show(n)) |