Yet Another Haskell Tutorial/Language basics

Haskell

Yet Another Haskell Tutorial
Preamble
Introduction
Getting Started
Language Basics (Solutions)
Type Basics (Solutions)
IO (Solutions)
Modules (Solutions)
Advanced Language (Solutions)
Advanced Types (Solutions)
Monads (Solutions)
Advanced IO
Recursion
Complexity
This box: view • talk • edit

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 $1$ 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 $1$ 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 $10$ elements), the fact that the list is infinitely long doesn't matter. If you only use the first $10$ elements, only the first $10$ 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: $1,2,3,...$ ); 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

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 $5$ is an expression (its value is $5$ ). Values can be built up from other values; for instance, $5+6$ is an expression (its value is $11$ ). 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.

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

In addition to single values, we should also address multiple values. For instance, we may want to refer to a position by its $x$ / $y$ 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, $5$ and $3$ . 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 `'a'` out of the tuple `((1,'a'),"foo")`.

Lists

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

In Haskell, a String is simply a list of Chars. 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

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"

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 ( $\cdot$ ) is associative if $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ ). When we write $4\cdot 8\cdot 5\cdot 1$ , we need to specify where to put the parentheses. Namely, do we mean $((4\cdot 8)\cdot 5)\cdot 1$ or $4\cdot (8\cdot (5\cdot 1))$ ? 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 `map` to convert a string into a list of booleans, each element in the new list representing whether or not the original element was a lower-case character. That is, it should take the string "aBCde" and return `[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 `max` returns the maximum of two numbers, write a function using a fold that will return the maximum value in a list (and zero if the list is empty). So, when applied to `[5,10,2,8,1]` it will return 10. Assume that the values in the list are always $\geq 0$ . Explain to yourself why it works.

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 `[(5,'b'),(1,'c'),(6,'a')]`, it will return 1.

Source Code Files

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

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 $-1$ if its argument is less than $0$ ; $0$ if its argument is $0$ ; and $1$ if its argument is greater than $0$ (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 $x<0$ 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 $1$ if its argument were $0$ ; a value of $5$ if its argument were $1$ ; a value of $2$ if its argument were $2$ ; and a value of $-1$ 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 $0$ , the value of f is $1$ . If it matches $1$ , the value of f is $5$ . If it maches $2$ , then the value of f is $2$ ; and if it hasn't matched anything by that point, the value of f is $-1$ (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.

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 $5*4$ and then applying $+3$ 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 ( $\circ$ ) operator in mathematics.

Note

In mathematics we write $f\circ g$ to mean "f following g," in Haskell we write f . g also to mean "f following g."

The meaning of $f\circ g$ is simply that $(f\circ g)(x)=f(g(x))$ . That is, applying the value $x$ to the function $f\circ g$ is the same as applying it to $g$ , taking the result, and then applying that to $f$ .

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

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 $ax^{2}+bx+c=0$ : $x=(-b\pm {\sqrt {b^{2}-4ac}})/(2a)$ . We could write the following function to compute the two values of $x$ :

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

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"

Comments

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

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:

$n!={\begin{cases}1&n=1\\n*(n-1)!&{\mbox{otherwise}}\\\end{cases}}$

This definition itself is exactly a recursive definition: namely the value of $n!$ depends on the value of $(n-1)!$ . 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 $n=1$ ) and one recursive case (when $n>1$ ). 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 $a$ and $b$ , and that we want to calculate $a^{b}$ . This problem has a single base case: namely when $b$ is $1$ . The recursive case is when $b>1$ . We can write a general form as:

$a^{b}={\begin{cases}a&b=1\\a*a^{b-1}&{\mbox{otherwise}}\\\end{cases}}$

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:

$F_{n}={\begin{cases}1&n=1{\mbox{ or }}n=2\\F_{n-2}+F_{n-1}&{\mbox{otherwise}}\\\end{cases}}$

Write a recursive function fib that takes a positive integer n as a parameter and calculates

F_{n}

.

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

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 $(1,100)$ . 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 reading 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))