Haskell/Beginning

Haskell is a programming language. If you can write and understand Haskell, you will be able to create new computer programs, and to understand and modify programs others have written. Learning to program is a fairly complex task, and Haskell is an ideal medium in this respect in that it is fairly simple and predictable. You may end up doing most of your programming in a language other than Haskell, but a significant portion of your knowledge will carry over to any language.

Haskell SoftwareEdit

To begin using any programming language, you will need some special software to make up your development toolchain. At the minimum, you will need a compiler or an interpreter.

In order to understand the role of compilers and interpreters in the programming process, it is necessary to reveal a little about how computers work. You may have heard of CPUs, or Central Processing Units. This piece of hardware is responsible for interpreting data known as machine language stored in the computer's memory. Machine language encodes simple instructions which, when processed by the CPU, cause the computer to do useful things such as bring you to this Web page. In other words, it is a programming language. Pause to consider how clever this is: the programs your computer executes, and the data they operate on, are stored in the same manner.

One significant consequence of this architecture is that programs can write other programs. This sounds like a bizarre act, but, in fact, it is terribly commonplace, and is exactly the purpose of interpreters and compilers. They translate programs written in a programming language such as Haskell into programs written in machine language, such that they may be executed.

The difference between a compiler and an interpreter has to do with the internal workings of the software; we will not discuss the difference and in modern times, the difference is becoming increasingly unclear and irrelevant.

"But what about my compiler?" Sorry about that brief digression. You want the Glasgow Haskell Compiler, or GHC. It is a free program, available for all major operating systems. Download

The REPL: Using Haskell as a CalculatorEdit

GHC includes a program known as GHCi, or "GHC Interactive." This program lets you type in small Haskell programs on one line, and executes them when you hit Enter. Consult the GHC documentation for info on how to start GHCi, and do so.

You should have a prompt, which says something such as Main>, in front of you. (Don't be alarmed if it says something else, such as Prelude>). When GHCi is in this state, it is ready to accept and execute a program. Try typing in the following simple program:

1 + 1

GHCi should respond by displaying the number two. This is, in fact, the purpose of this program: to compute the sum of 1 and 1, and display it. Programs that compute things and display them are called expressions, and they make up the larger part of Haskell. When you execute an expression to determine the value it produces, it is referred to as evaluating that expression.

Note that, once you've evaluated an expression, you can do more than simply display it; in fact, there are a variety of ways in which the values expressions produce can be used. We will encounter these various techniques later on; simply be aware that they exist.

Moving back to less theoretical matters, at this point, your interaction with GHCi should look something like this:

Main> 1 + 1
2

When showing examples, we will display interactions with GHCi this way, as well. A program will generally be included with its result, and preceded by a Main> prompt. You can duplicate the same interaction with GHCi by typing in the program on the prompt.

More ArithmeticEdit

As you may have guessed, Haskell supports a full complement of arithmetic operators; addition (+), subtraction (-), multiplication (*), and division (/). Numbers can be notated in the usual way, as integers or real numbers, with one catch; no number may be written without numbers before the decimal point. That is, for instance, .5 should always be written as 0.5. The operators follow the normal order of operations, and parentheses can be used in the usual way. You can also use a variety of constants and functions, such as pi, sqrt, log, sin, cos, and tan.

Go ahead and try out a few expressions; you can't break anything if you mess up. Here are some simple examples:

Main> 3 * 3 * 3
27
Main> 9.6
9.6
Main> 5 / 7
0.7142857142857143
Main> sqrt(2)
1.4142135623730951
Main> (7 - 5) * 3
6
Main> cos(pi)
-1.0

Note that the spaces in the examples are not necessary; the first one could have been written 3*3*3, and the fifth (7-5)*3, for instance. In general, Haskell isn't picky about spaces, except where otherwise noted. When in doubt, however, use more spaces, rather than fewer.

ErrorsEdit

Any computer user is familiar with errors. You can get them when programming, as well. Try this little experiment:

Main> 1 +
<interactive>:1:3: parse error (possibly incorrect indentation)

When you make a mistake in your program, GHCi will notify you, and tell you what it perceives to be the problem. Unfortunately, it doesn't always guess correctly, and it's usually rather cryptic about its diagnosis. In this example, aside from the useless comment about indentation, it's on the right track, but it still has the latter problem of being rather cryptic. So, what is a "parse error?"

A parser is the part of a compiler responsible for breaking the program down into logical pieces, and converting it to a format suitable for translation into machine language. A "parse error," then, is when the compiler can't make sense of your program; this means that there's a problem with your program.

So, what's this business: <interactive>:1:3:? The first part, <interactive>, means that it's reporting an error from the program you just typed; there are other methods of program entry (which we are ignoring for now), which would display something else here. The first number is the number of the line that the error occurred on; it will always be one for interactively entered programs, so, again, it is of little use to us. The second is the column in which GHC thinks the erroneous piece of code occurs (actually, the first column is numbered zero, so it's the offending code's column number minus one). Here it points to the fourth column, just after the plus sign; this is correct, because the problem is that we omitted a right operand for the operator. (By the way, in general, do not take these numbers as Gospel; GHC sometimes gives you numbers that are slightly off.)

Now, what about when GHC guesses the problem incorrectly? Let's consider a slightly modified version of the mistake above:

Main> (1 +)

Top level:
    No instance for (Show (a -> a))
      arising from use of `print' at Top level
    Probable fix: add an instance declaration for (Show (a -> a))
    In a 'do' expression: print it

We made a small change, and the error message changed completely. In addition, the message now diagnoses a problem completely different than the actual one, and refers to fairly advanced features of Haskell which you have yet to learn. An unfortunately large class of errors produces messages like this one; dealing with these messages is one of the more challenging aspects of learning Haskell. (Other programming systems share this problem, as well, but most are somewhat better off than Haskell.)

Of course, this was an extreme example; most of the time, the messages will not be so far off-target as this one.

Try typing in a few invalid programs and see what kinds of error messages you get back, just to get a feel for them. Again, you can't break anything, so don't worry about it. Here are some examples:

Main> xxx
<interactive>:1:0: Not in scope: `xxx'
Main> .5
<interactive>:1:0: parse error on input `.'
Main> 5*.5
<interactive>:1:1: Not in scope: `*.'
Main> &$#^!
<interactive>:1:0: parse error on input `&$#^!'
Main> sqrt sqrt 4
<interactive>:1:0:
    No instance for (Floating (a -> a))
      arising from use of `sqrt' at <interactive>:1:0-3
    Probable fix: add an instance declaration for (Floating (a -> a))
    In the definition of `it': it = sqrt sqrt 4
Main> sqrt(sqrt(4))
1.4142135623730951

VariablesEdit

Haskell supports a feature called variables. These are similar to the variables of algebra, but there are more restrictions on their usage.

A variable is named by one or more letters; x, jane, respond, and xyzzy are all acceptable names for variables. They can contain uppercase letters, as well, but not as the first letter; Jane, for instance, is not an acceptable variable name, although jAnE is. The typical use of uppercase letters is to delimit words in names; for instance, instead of writing multiwordvariablename, it is customary to write multiWordVariableName, which is easier on the eyes.

You can assign values to variables with a program of the form:

 let variable name = value

For instance, the program let x = 5 defines x to be five. The value can also be an arbitrary expression, such as (2 + 3) / 1.

Notice that the name of a variable is the only thing that can appear on the left side of an equals sign. These programs all work incorrectly:

Main> let 5 = x
Main> let 2 * x = 5
Main> let x = x

Curiously, GHCi generates no errors for any of them. That's because they're valid Haskell; they just don't do what you expect. For instance, after executing the second statement, 2 * 7 is five, and, after executing the third statement, attempting to find the value of x will result in GHCi hanging. (Press ctrl+c in UNIX, ctrl+. in Mac OS X, and ctrl+break in Windows to stop it.) The first appears to do nothing, but this is probably a bug; it should produce an error message.

Bottom line: Haskell isn't algebra; don't use it as such, because the compiler will delight in surprising you.

Once you've established a variable's value, you can use that variable in following expressions; each occurrence of the variable will be substituted for its value. For instance:

Main> let x = 5
Main> let y = 2 + 2
Main> let z = sqrt 9
Main> x * (y + z)
35.0

Multiple variables can be established in one let by delimiting the assignments with a semicolon. For instance, the previous example could be rewritten as:

Main> let x = 5; y = 2 + 2; z = sqrt 9
Main> x * (y + z)
35.0

FunctionsEdit

While you've made it through quite a bit of material, you may feel like you're not much closer to programming your computer. The programs we've written so far haven't accomplished much; you'd do just as well with pencil and paper, or a conventional pocket calculator. By the end of this chapter, you will be able to do less trivial things, but the examples will still be quite contrived. However, at this point, you have nowhere to go but up; the variety and complexity of the programs you can write will begin to grow exponentially from here, and continue for the next several chapters, as you learn about new kinds of expressions, and new ways to combine expressions.

Haskell supports functions. To begin with, banish any preconceptions of this word related to mathematical functions; Haskell's functions are only superficially similar.

A better match to Haskell functions is Haskell variables. A variable stands in for an expression. A function stands in for an expression, as well, with one twist: it takes an argument; a variable which is defined inside the function, supplied when the function is used. This concept is perhaps best understood by example:

Main> let f x = x + 3

This code defines the function f, with the argument x.

What can we do with f? We can apply it to an argument. Suppose the argument is to be four. The code for this is:

Main> f 4
7

What's going on here? Let's refer back to the definition of f:

let f x = x + 3

The expression f 4 is substituted by the definition of f, with x substituted by four. Thus, it becomes 4 + 3, which is, of course, seven.

The general form of a function definition is:

 let function argument = definition

And the general form of a function application is:

 function argument

Notice that, in these definitions, the word "argument" is used in two different ways. The first is the kind the function has attached to its definition; simply a name standing in for a value that is supplied when it is applied. The second is the actual value that ousts the previous type of argument when the function is applied, resulting an expression which can be evaluated.

A few examples:

Main> let reciprocal n = 1 / n
Main> reciprocal 5
0.2
Main> let theSame thing = thing
Main> theSame 6
6
Main> let funny joe = log(pi / joe) * cos(joe + 3)
Main> funny 6
0.5895282337509272

Again, there is a simple technique for figuring out the value of a function expansion by hand:

  1. Write down the expansion of the function.
  2. Write it down again, with all occurrences of the argument name substituted for the argument value.
  3. Solve the resulting expression.

Functions With Several ArgumentsEdit

The function notation suggests that it might be possible to create a function with more than one argument. In fact, this is possible, and works exactly as you might expect:

Main> let add x y = x + y
Main> add 5 6
11
Main> let average x y z = (x + y + z) / 3
Main> average 5 6 7
6
Main> let first a b = a
Main> first 8 1
8

One "gotcha" to watch out for when programming with multi-argument functions is giving too many arguments, or not enough arguments, to a function. These examples demonstrate the problem:

Main> average 1 2
Top level:
    No instance for (Show (a -> a))
      arising from use of `print' at Top level
    Probable fix: add an instance declaration for (Show (a -> a))
    In a 'do' expression: print it
Main> average 1 2 3 4
<interactive>:1:0:
    No instance for (Fractional (t -> a))
      arising from use of `average' at <interactive>:1:0-6
    Probable fix: add an instance declaration for (Fractional (t -> a))
    In the definition of `it': it = average 1 2 3 4

Both of these errors look fairly similar. In general, if you get an error of this form, check that you gave the right number of arguments to your functions.

Functions in ExpressionsEdit

Up until now, we have only given numbers as arguments to functions. However, you can give expressions as arguments, as well, and use function applications as expressions:

Main> let f x = 2 * x
Main> f (1 + 1)
4
Main> f (f (f 3))
24
Main> f 4 + 2
10

Function applications are evaluated before operators; thus, f 4 + 2 is equivalent to (f 4) + 2, not f (4 + 2).

Since function applications are expressions, they can be used in function definitions. For instance:

Main> let f x = 2 * x; g x = 3 + f x
Main> f 5
10
Main> g 5
13

There are several small points to note here:

  • We used the semicolon notation in the let expression to squeeze in definitions for two functions; f x = 2 * x and g x = 3 + f x.
  • f is defined before g, but it doesn't have to be that way; the program would still work if the definitions were reversed. However, this does not work:
Main> let g x = 3 + f x
<interactive>:1:14: Not in scope: `f'

(When GHC complains that a variable or function is "not in scope," it simply means that it has not yet seen a definition of it yet. As was mentioned before, GHC requires that variables and functions be defined before they are used.)

  • The definition of g, 3 + f x, is equivalent to 3 + (f x), as mandated by the rules given earlier. Thus, g 5 becomes 3 + (2 * 5) after expanding the definitions of g and f; the expression is further evaluated to produce 13.

Conditional TestsEdit

I promised that, as you read more of this book, you would learn to write newer, more exciting types of programs. In this chapter, we will fill in another missing piece of the puzzle.

The programs you have written so far have seemed somewhat simplistic; they haven't been able to make choices, to do different things at different times. An easy to achieve simple choice-making is to use an if expression. These expressions take the following form:

 if test then expression else expression

The test part can take one of the following forms:

 expression == expression
 expression /= expression
 expression < expression
 expression > expression
 expression <= expression
 expression >= expression

Each form describes some sort of relation between the two expressions; for instance, < is the mathematical less-than test. Each is a plain-text corruption of some mathematical operator:

== The equal-to test. It is a doubled equals sign to distinguish it from the equals sign used in let expressions.
/= The not-equal-to test. It is a corruption of \ne.
<, > The less-than and greater-than tests.
<=, >= The less-than-or-equal-to and greater-than-or-equal-to tests. Corruptions of \le and \ge.

When an if expression is evaluated, if the test part states something true (e.g. 5 < 6), then it evaluates to the then expression; otherwise, if the test part states something false (e.g. 5 == 6), then it evaluates to the else expression. This is demonstrated in these examples:

Main> let x = 5
Main> if x < 7 then 1 else 2
1
Main> if x <= 5 then x + 1 else pi
6
Main> 1 + (if 2 * x == 10 then 2 else 1)
3
Main> if x < 6 then (if x < 5 then 1 else 2) else 3
2
Main> if x < 5 then 1 else (if x < 6 then 2 else 3)
2

Note that, in the last three examples, the parentheses were not necessary; however, if the last example had been written with the operands to the plus sign reversed, the parentheses would have been necessary; thus, it would be

(if 2 * x == 10 then 2 else 1) + 1

If it were written without the parentheses, it would evaluate to:

Main> if 2 * x == 10 then 2 else 1 + 1
2

ExamplesEdit

Here are a few examples of functions using if expressions.

Absolute ValueEdit

Main> let abs x = if x < 0 then -x else x
Main> abs 5
5
Main> abs (-3)
3
Main> abs 0
0

Numerical Three-Way TestsEdit

Main> let nif x p z n = if x > 0 then p else if x == 0 then z else n
Main> nif 3 1 2 3
1
Main> nif 0 1 2 3
2
Main> nif (-6) 1 2 3
3

This function corresponds to the following mathematical function:

f(x,p,z,n) =
\begin{cases}
  p & \mbox{if } x > 0;\\
  z & \mbox{if } x = 0;\\
  n & \mbox{if } x < 0.
\end{cases}

The last test, instead of being if x < 0 then n, is simply else n. This is because, by the definition of the numeric relations, if x is neither less than or equal to zero, it must be greater than zero, so the test will always be true. Furthermore, every if needs an else clause, and what would you put in an else clause that can never be reached?

Actually, Haskell has a tool for these cases; undefined. This is the name of a special value that, when produced as an answer from an expression, simply flags an error. It is a good value to put in "impossible" cases of your if expressions.

SignEdit

Main> let sign x = nif x 1 0 -1
Main> sign 5
1
Main> sign 0
0
Main> sign (-8)
-1

This function corresponds to the following mathematical function:

S(x) =
\begin{cases}
  1 & \mbox{if } x > 0;\\
  0 & \mbox{if } x = 0;\\
  -1 & \mbox{if } x < 0.
\end{cases}

We could have defined it like this:

let sign x = if x > 0 then 1 else if x == 0 then 0 else -1

However, since nif turns out to be a generalization of the sign function, it is simpler to define it as an application of nif. In fact, expanding nif into the function's body leaves you with exactly the above code!

Logical ConjunctionsEdit

Boolean Expressions and PredicatesEdit

Last modified on 12 May 2012, at 20:50