Programming, in its broadest sense, is problem solving. It begins when we look out into the world and see problems that we want to solve, problems that we think can and should be solved using a digital computer. Understanding the problem well is the first - and probably the most important -step in programming, because without that understanding we may find ourselves wandering aimlessly down a dead-end alley, or worse, down a fruitless alley with no end. "Solving the wrong problem" is a phrase often heard in many contexts, and we certainly don't want to be victims of that crime. So the first step in programming is answering the question, "What problem am I trying to solve?"

Once you understand the problem, then you must find a solution. This may not be easy, of course, and in fact you may discover several solutions, so we also need a way to measure success. There are various dimensions in which to do this, including correctness ("Will I get the right answer?") and efficiency ("Will I have enough resources?"). But the distinction of which solution is better is not always clear, because the number of dimensions can be large, and programs will often excel in one dimension and do poorly in others. For example, there may be one solution that is fastest, one that uses the least amount of memory, and one that is easiest to understand. Choosing can be difficult and is one of the more interesting challenges that you will face in programming.

The last measure of success mentioned above - clarity of a program - is somewhat elusive, most difficult to measure, and, quite frankly, sometimes difficult to rationalize. But in large software systems clarity is an especially important goal, because the most important maxim about such systems is that they are never really finished! The process of continuing work on a software system after it is delivered to users is what software engineers call software maintenance, and is the most expensive phase of the so-called "software lifecycle." Software maintenance includes fixing bugs in programs, as well as changing certain functionality and enhancing the system with new features in response to users' experience.

Therefore, taking the time to write programs that are highly legible - easy to understand and to reason about - will facilitate the software maintenance process. It is important to realize that the person performing software maintenance is usually not the person who wrote the original program. Therefore, when you write your programs, write them as if you are writing them for someone else to see, to understand, and ultimately to pass judgment on!

In this book, I will often solve each example in several different ways (some of which are dead ends!), taking the time to contrast the style, efficiency, clarity, and functionality of the results. I do this not just for pedagogical purposes. Such reworking of programs is the norm, and you are encouraged to get into the habit of doing so. Don't always be satisfied with your first solution to a problem, and always be prepared to go back and change parts of your program that you later discover do not satisfy your actual needs.

Discussions of program clarity bring us ultimately to the issue of our programming language choice. This choice determines how we express our solutions in such a way that a computer can understand them. Our programs embody our solutions - and our creativity, eloquence, and perseverance - for interpretation by the computer.

In this text I will use the programming language Haskell to address many of the issues discussed in the last section. I have tried to avoid the approach of explaining Haskell first and giving examples second. Rather, I will walk with you, step by step, along the path of understanding an application, understanding the solution space, and understanding how to express a particular solution in Haskell. I want you to learn how to problem solve!

Along this path I will use whatever tools are appropriate for analyzing a particular problem domain, very often mathematical tools familiar to the average college student, indeed most to the average high school student. Concurrently, I will evolve our problems toward a particular view of computation that is especially useful: that of computation by calculation. You will find that such a viewpoint is not only powerful, it is also simple (we won't shy away from difficult problems). Haskell supports well the idea of computation by calculation. Programs in Haskell can be viewed as functions whose input is that of the problem being solved, and whose output is our desired result; and the behavior of functions can be understood easily as computation by calculation.

An example might help to demonstrate these ideas. Suppose we want to perform an arithmetic calculation such as 3 × (9 + 5). In Haskell we would write this as 3 * (9 + 5) because most standard computer keyboards and text editors do not recognize the special symbol ×. To calculate the result, we proceed as follows:

3 * (9 + 5)
 => 3 * 14
 => 42

It turns out that this is not the only way to compute the result, as evidenced by this alternative calculation:

3 * (9 + 5)
 => 3 * 9 + 3 * 5
 => 27 + 3 * 5
 => 27 + 15
 => 42

Even though this calculation takes two extra steps, it at least gives the correct answer. Indeed, an important property of each and every program in this textbook - in fact every program that can be written in the functional language Haskell - is that it will always yield the same answer when given the same inputs, regardless of the order in which we choose to perform the calculations. This is precisely the mathematical definition of a function: For the same inputs, it always yields the same output.

On the other hand, the first calculation above took fewer steps than the second, and so we say that it is more efficient. Efficiency in both space (amount of memory used) and time (number of steps executed) is important when searching for solutions to problems, but of course if we get the wrong answer, efficiency is a moot point. In general, we will search first for any solution to a problem, and later refine it for better performance.

The above calculations are fairly trivial, of course. But we will be doing much more sophisticated operations soon enough. For starters - and to introduce the idea of a function - we could generalize the arithmetic operations performed in the previous example by defining a function to perform them for any numbers x, y, and z:

simple x y z = x * (y + z)

This equation defines simple as a function of three arguments, x, y, and z. In mathematical notation, we might see the above written slightly differently, namely: simple(x, y, z) = x × (y + z). In any case, it should be clear that “simple 3 9 5” is the same as “3 * (9 + 5)”. In fact the proper way to calculate the result is:

simple 3 9 5
 => 3 * (9 + 5)
 => 3 * 14
 => 42

The first step in this calculation is an example of unfolding a function definition: 3 is substituted for x, 9 for y, and 5 for z on the right-hand side of the definition of simple. This is an entirely mechanical process, not unlike what the computer actually does to execute the program.

When I wish to say that an expression e evaluates (via zero, one, or possibly many more steps) to the value v, I will write e ==> v (this arrow is longer than that used earlier). So we can say directly, for example, that

simple 3 9 5 ==> 42

With simple now suitably defined, we can repeat the sequence of arithmetic calculations as often as we like, using different values for the arguments to simple. For example,

simple 4 3 2 ==> 20

We can also use calculation to prove properties about programs. For example, it should be clear that for any a, b and c,  simple a b c should yield the same result as  simple a c b. For a proof of this, we calculate symbolically, that is, using the symbols a, b and c rather than concrete numbers such as 3, 5 and 9:

simple a b c
 => a * (b + c)
 => a * (c + b)
 => simple a c b

The same notation will be used for these symbolic steps as for concrete ones. In particular, the arrow in the notation reflects the direction of our reasoning, and nothing more. In general, if e1 => e2, then it's also true that e2 => e1.

I will also refer to these symbolic steps as “calculations”, even though the computer will not typically perform them when executing a program (although it might perform them before a program is run if it thinks that it might make the program run faster). The second step in the calculation above relies on the commutativity of addition (namely that, for any numbers x and y,  x + y = y + x). The third step is the reverse of an unfold step, and is appropriately called a fold calculation. It would be particularly strange if a computer performed this step while executing a program, because it does not seem to be headed toward a final answer. But for proving properties about programs, such “backward reasoning” is quite important.

When I wish to make the justification for each step clearer, whether symbolic or concrete, a calculation will be presented with more detail, as in:

simple a b c => {unfold}
 => a * (b + c)
 => {commutativity} a * (c + b)
 => {fold} simple a c b

Proving properties of programs is another theme that will be repeated often in this text. As the world relies more and more on computers to accomplish not just ordinary tasks such as writing term papers and sending email, but also life-critical tasks such as controlling medical procedures and guiding spacecraft, then the correctness of programs gains in importance. Proving complex properties of large, complex programs is not easy, and is rarely if ever done in practice. However, that should not deter us from proving simpler properties of the whole system, or complex properties of parts of the system, because such proofs may uncover errors, and if not, at least help us to gain confidence in our effort.

If you are already an experienced programmer, the idea of computing everything by calculation may seem odd at best and naive at worst. How does one write to a file, draw a picture, or respond to mouse clicks? If you are wondering about these things, have patience reading the early chapters and find delight reading the later chapters where the full power of this approach begins to shine. I will avoid, however, most comparisons between Haskell and conventional programming languages such as C, C++, Ada, Java, or even Scheme or ML (two ''almost functional'' languages), because for those who have programmed in these other languages the differences will be obvious, and for those who haven't the comments would be superfluous.

In many ways this first chapter is the most difficult chapter in the entire text because it contains the highest density of new concepts. If you have trouble with some of the ideas here, keep in mind that we will return to almost every idea at later points in the text. And don't hesitate to return to this chapter later to reread difficult sections; they will likely be much easier to grasp at that time.

In this section we will take a much closer look at the idea of computation by calculation. In Haskell, the objects that we perform calculations on are called expressions, and the objects that result from a calculation (i.e., “the answers”) are called values. It is helpful to think of a value just as an expression on which no more calculation can be carried out.

Examples of expressions include atomic (meaning indivisible) expressions such as the integer 42 and the character 'a', as well as structured (meaning made from smaller pieces) expressions such as the list [1, 2, 3] and the pair ('b', 4) (lists and pairs are different in a subtle way, to be described later). Each of these examples is also a value, because by themselves there is no calculation that can be carried out. As another example, 1 + 2 is an expression, and one step of calculation yields the expression 3, which is a value, because no more calculations can be performed on it.

Sometimes, however, an expression has only a never-ending sequence of calculations. For example, if x is defined as:

x = x + 1

x => x + 1
 => (x + 1) + 1
 => ((x + 1) + 1) + 1
 => (((x + 1) + 1) + 1) + 1

Every expression (and therefore every value) also has an associated type. You can think of types as sets of expressions (or values) in which members of the same set have much in common. Examples include the atomic types Integer (the set of all fixed-precision integers) and Char (the set of all characters), as well as the structured types [Integer] (the set of all lists of integers) and (Char, Integer) (the set of all character/integer pairs). The association of an expression or value with its type is very important, and there is a special way of expressing it in Haskell. Using the examples of values and types above, we write:

42 :: Integer
'a' :: Char
[1,2,3] :: [Integer]
('b', 4) :: (Char, Integer)

Haskell's type system ensures that Haskell programs are well-typed; that is, that the programmer has not mismatched types in some way. For example, it does not make much sense to add together two characters, so the expression 'a' + 'b' is ill-typed. The best news is that Haskell's type system will tell you if your program is well-typed before you run it. This is a big advantage, because most programming errors are manifested as typing errors.

The idea of dividing the world of values into types should be familiar to most people. We do it all the time for just about every kind of object. Take boxes, for example. Just as we have integers and reals, lists and tuples, etc., we also have large boxes and small boxes, cardboard boxes and wooden boxes, and so on. And just as we have lists of integers and lists of characters, we also have boxes of nails and boxes of shoes. And just as we would not expect to be able to take the square of a list or add two characters, we would not expect to be able to use a box to pay for our groceries.

Types help us to make sense of the world by organizing it into groups of common shape, size, functionality, and others. The same is true for programming, where types help us to organize values into groups of common shape, size, and functionality, among others. Of course, the kinds of commonality between values will not be the same as those between objects in the real world, and in general, we will be more restricted - and more formal - about just what we can say about types and how we say it.

What should the type of a function be? It seems that it should at least convey the fact that a function takes values of one type - T1, say - as input and returns values of (possibly) some other type - T2, say - as output. In Haskell this is written T1 -> T2, and we say that such a function “maps values of type T1 to values of type T2”. If there is more than one argument, the notation is extended with more arrows. For example, if our intent is that the function simple defined in the previous section has type Integer -> Integer -> Integer -> Integer, we can declare this fact by including a type signature with the definition of simple:

simple :: Integer -> Integer -> Integer -> Integer
simple x y z = x * (y + z)

Haskell's type system also ensures that user-supplied type signatures, such as this one, are correct. Actually, Haskell's type system is powerful enough to allow us to avoid writing any type signatures at all, in which case we say that the type system infers the correct types for us. Nevertheless, judicious placement of type signatures, as we did for simple, is a good habit, because type signatures are an effective form of documentation and help bring programming errors to light. Also, in almost every example in this text, I will make a habit of first talking about the types of expressions and functions as a way to better understand the problem at hand, organize our thoughts, and lay down the first ideas of a solution.

The normal use of a function is referred to as function application. For example, simple 3 9 5 is the application of the function simple to the arguments 3, 9 and 5.

The title of this section answers the question: “What are the three most important ideas in programming?” Well, perhaps this is an overstatement, but I hope that I've gotten your attention, at least. Webster defines the verb “abstract” as follows:

One of the most basic ideas in programming - for that matter, in everyday life - is to name things. For example, because it is inconvenient to retype (or remember) the value of π beyond a small number of digits, we may wish to give it a name. In mathematics the Greek letter π in fact is the name for this value, but unfortunately we don't have the luxury of using Greek letters on standard computer keyboards and text editors. So in Haskell we write:

pi :: Float
pi = 3.14159

Suppose now that we are working on a problem whose solution requires writing some expression more than once. For example, we might find ourselves computing something such as:

x :: Float
x = f (a - b + 2) + g y (a - b + 2)

The first line declares x to be a floating-point number, while the second is an equation that defines the value of x. Note on the right-hand side of this equation that the expression a - b + 2 is repeated - it has two instances -and thus, applying the abstraction principle, we wish to separate it from these instances. We already know how to do this - it's called naming - so we might choose to rewrite the single equation above as two:

c = a - b + 2
x = f c + g y c

If, however, the definition of c is not intended for use elsewhere in the program, then it is advantageous to “hide” the definition of c within the definition of x. This will avoid cluttering up the namespace, and prevents c from clashing with some other value named c. To achieve this, we simply use a let expression:

x = let c = a - b + 2 in f c + g y c

A let expression restricts the visibility of the names that it creates to the internal workings of the let expression itself. For example, if we write:

c = 42
x = let c = a - b + 2 in f c + g y c

So you can see that naming - using either top-level equations or equations within a let expression - is an example of the abstraction principle in action. It's often the case, of course, that we anticipate the need for abstraction; for example, directly writing down the final solution above, because we knew that we would need to use the expression a - b + 2 more than once.

Let's now consider a more complex example. Suppose we are computing the sum of the areas of three circles with radii r1, r2, and r3, as expressed by

totalArea :: Float
totalArea = pi * r1^2 + pi * r2^2 + pi * r3^2

Although there isn't an obvious repeating expression here as there was in the last example, there is a repeating pattern of operations, namely, the operations that square some given quantity - in this case the radius - and then multiply the result by π. To abstract a sequence of operations such as this, we use a function, which we will give the name circleArea, that takes the "given quantity" - the radius - as an argument. There are three instances of the pattern, each of which we can expect to replace with a call to circleArea. This leads to:

circleArea :: Float -> Float
circleArea r = pi * r ^ 2
totalArea = circleArea r1 + circleArea r2 + circleArea r3

Using the idea of unfolding described earlier, it is easy to verify that this definition is equivalent to the previous one.

This application of the abstraction principle is sometimes called functional abstraction, because the sequence of operations is abstracted as a function, in this case circleArea. Actually, it can be seen as a generalization of the previous kind of abstraction: naming. That is, circleArea r1 is just a name for pi * r1 ^ 2, circleArea r2 - for pi * r2 ^ 2, and circleArea r3 - for pi * r3 ^ 2. In other words, a named quantity, such as c or pi defined previously, can be thought of as a function with no arguments.

Note that circleArea takes a radius (a floating-point number) as an argument and returns the area (also a floating-point number) as a result. This is reflected in its type signature.

The definition of circleArea could also be hidden within totalArea using a let expression as we did in the previous example:

totalArea = let circleArea r = pi * r ^ 2
            in circleArea r1 + circleArea r2 + circleArea r3

On the other hand, it is more likely that computing the area of a circle will be useful elsewhere in the program, so leaving the definition at the top level is probably preferable in this case.

The value of totalArea is the sum of the areas of three circles. But what if in another situation we must add the areas of five circles, or in other situations, even more? In situations where the number of things is not certain, it is useful to represent them in a list whose length is arbitrary.

So imagine that we are given an entire list of circle areas whose length isn't known when we write the program. What now?

I will define a function listSum to add the elements of a list. Before doing so, however, there is a bit more to say about lists.

Lists are an example of a data structure, and when their use is motivated by the abstraction principle, I will say that we are applying data abstraction. Earlier we saw the example [1, 2, 3] as a list of integers, whose type is thus [Integer]. Not surprisingly, a list with no elements is written [], and pronounced “nil”. To add a single element x to the front of a list xs, we write x : xs. (Note the naming convention used here; xs is the plural of x, and should be read that way). In fact, the list [1, 2, 3] is equivalent to 1 : (2 : (3 : [ ])), which can also be written 1 : 2 : 3 : [ ] because the infix operator (:) is “right associative”.

Examples of predefined functions defined on lists in Haskell include head and tail, which return the “head” and “tail” of a list, respectively. That is, head (x : xs) ==> x and tail (x : xs) ==> xs (we will define these two functions formally in Section 5.1). Another example is the function (++), which concatenates, or appends, together its two list arguments. For example, [1, 2, 3] ++ [4, 5, 6] ==> [1, 2, 3, 4, 5, 6]  ((++) will be defined in Section 11.2).

Returning to the problem of defining a function to add the elements of a list, let's first express what its type should be:

listSum :: [Float] -> Float

Now we must define its behavior appropriately. Often in solving problems such as this, it is helpful to consider, one by one, all possible cases that could arise. To compute the sum of the elements of a list, what might the list look like? The list could be empty, in which case the sum is surely 0. So we write:

listSum [] = 0

The other possibility is that the list isn't empty (i.e., it contains at least one element) in which case the sum is the first number plus the sum of the remainder of the list. So we write:

listSum (x : xs) = x + listSum xs

Combining these two equations with the type signature brings us to the complete definition of the function listSum:

listSum :: [Float] -> Float
listSum [] = 0
listSum (x : xs) = x + listSum xs

This is called a recursive function definition because listSum “refers to itself” on the right-hand side of the second equation. Recursion is a very powerful technique that will be used many times in this text. It is also an example of a general problem-solving technique where a large problem is broken down into many simpler but similar problems; solving these simpler problems one by one leads to a solution to the larger problem. Here is an example of listSum in action:

listSum [1, 2, 3]
 => listSum (1 : (2 : (3 : [])))
 => 1 + listSum (2 : (3 : []))
 => 1 + (2 + listSum (3 : []))
 => 1 + (2 + (3 + listSum []))
 => 1 + (2 + (3 + 0))
 => 1 + (2 + 3)
 => 1 + 5
 => 6

The first step above is not really a calculation, but rather is a rewriting of the list syntax. The remaining calculations consist of four unfold steps followed by three integer additions.

Given this definition of listSum we can rewrite the definition of totalArea as:

totalArea = listSum [circleArea r1, circleArea r2, circleArea r3]

This may not seem like much of an improvement, but if we were adding many such circle areas in some other context, it would be. Indeed, lists are arguably the most commonly used structured data type in Haskell. In the next chapter we will see a more convincing example of the use of lists; namely, to represent the vertices that make up a polygon. Because a polygon can have an arbitrary number of vertices, using a data structure such as a list seems like just the right approach.

In any case, how do we know that this version of totalArea behaves the same as the original one? By calculation, of course:

listSum [circleArea r1, circleArea r2, circleArea r3] => { unfold listSum (four succesive times) }
 circleArea r1 + circleArea r2 + circleArea r3 + 0 => { unfold circleArea (three places) }
 pi * r1 ^ 2 + pi * r2 ^ 2 + pi * r3 ^ 2 + 0 => { simple arithmetic }
 pi * r1 ^ 2 + pi * r2 ^ 2 + pi * r3 ^ 2

totalArea = pi * r1 ^ 2 + pi * r2 ^ 2 + pi * r3 ^ 2

totalArea = listSum [circleArea r1, circleArea r2, circleArea r3]

But we have also introduced definitions for the auxiliary functions circleArea and listSum. In terms of size, our final program is actually larger than what we began with! So have we actually improved things?

From the standpoint of “removing repeating patterns”, we certainly have, and we could argue that the resulting program is easier to understand. But there is more. Now that we have defined auxiliary functions, such as circleArea and listSum, we can reuse them in other contexts. Being able to reuse code is also called modularity, because the reused components are like little modules, or bricks, that can form the foundation of many applications. We've already talked about reusing circleArea; and listSum is surely reusable: imagine a list of grocery item prices, or class sizes, or city populations, for each of which we must compute the total. In later chapters you will learn other concepts - most notably higher-order functions and polymorphism - that will substantially increase your ability to reuse code.

In mathematics there are many different kinds of number systems. For example, there are integers, natural numbers (i.e., non-negative integers), real numbers, rational numbers, and complex numbers. These number systems possess many useful properties, such as the fact that multiplication and addition are commutative, and that multiplication distributes over addition. You have undoubtedly learned many of these properties in your studies and have used them often in algebra, geometry, trigonometry, and physics, among others.

Unfortunately, each of these number systems places great demands on computer systems. In particular, a number can in general require an arbitrary amount of memory to represent it - even an infinite amount! Clearly, for example, we cannot represent an irrational number such as π exactly; the best we can do is approximate it, or possibly write a program that computes it to whatever (finite) precision we need in a given application. But even integers (and therefore rational numbers) present problems, because any given integer can be arbitrarily large.

Most programming languages do not deal with these problems very well. In fact, most programming languages do not have exact forms of any of these number systems. Haskell does slightly better than most, in that it has exact forms of integers (the type Integer) as well as rational numbers (the type Rational, defined in the Ratio Library). But in Haskell and most other languages, there is no exact form of real numbers, for example, which are instead approximated by floating-point numbers with either single-word precision (Float in Haskell) or double-word precision (Double). What's worse, the behavior of arithmetic operations on floating-point numbers can vary somewhat depending on the CPU being used, although hardware standardization in recent years has lessened the degree of this problem.

The bottom line is that, as simple as numbers seem, great care must be taken when programming with them. Many computer errors, some quite serious and renowned, have been rooted in numerical incongruities. The field of mathematics known as numerical analysis is concerned precisely with these problems, and programming with floating-point numbers in sophisticated applications often requires a good understanding of numerical analysis to devise proper algorithms and write correct programs.

As a simple example of this problem, consider the distributive law, expressed here as a calculation in Haskell and used earlier in this chapter in calculations involving the function simple:

a * (b + c) => a * b + a * c

For most floating-point numbers, this law is perfectly valid. For example, in the Hugs implementation of Haskell, the expressions pi * (3.52 + 4.75) and pi * 3.52 + pi * 4.75 both yield the same result: 25.981. But funny things can happen when the magnitude of b + c differs significantly from the magnitude of either b or c. For example, the following two calculations are from Hugs:

5 * (-0.123456 + 0.123457) ==> 4.99189e-006
5 * (-0.123456) + 5 * (0.123457) ==> 5.00679e-006

Although the error here is small, its very existence is worrisome, and in certain situations it could be disastrous. The nature of floating-point numbers will not be discussed much further in this text, but just remember that they are approximations to the real numbers. If real-number accuracy is important to your application, further study of the nature of floating-point numbers is probably warranted.

On the other hand, the distributive law (and many others) is valid in Haskell for the exact data types Integer and Ratio Integer (i.e., rational numbers). However, another problem arises: Although the representation of an Integer in Haskell is not normally something that we are concerned about, it should be clear that the representation must be allowed to grow to an arbitrary size. For example, Haskell has no problem with the following number:

veryBigNumber :: Integer
veryBigNumber = 43208345720348593219876512372134059

For this reason, Haskell provides another integer data type called Int, which has maximum and minimum values that depend on the word size of the CPU. In other words, every value of type Int fits into one word of memory, and the primitive machine instructions for integers can be used to manipulate them very efficiently. Unfortunately, this means that overflow or underflow errors could occur when an Int value exceeds either the maximum or minimum values. However, most implementations of Haskell (as well as most other languages) do not even tell you when this happens. For example, in Hugs, the following Int value:

i :: Int
i = 1234567890

This is alarming! Indeed, why should anyone ever use Int when Integer is available? The answer, as mentioned earlier, is efficiency, but clearly, care should be taken when making this choice. If you are indexing into a list, for example, and you are confident that you are not performing index calculations that might result in the above kind of error, then Int should work just fine, because a list longer than 2³¹ will not fit into memory anyway! But if you are calculating the number of microseconds in some large time interval or counting the number of people living on earth, then Integer would most likely be a better choice. Choose your number data types wisely!

In this text the data types Integer, Int, Float and Rational will be used for a variety of different applications; for a discussion of the other number types, consult the Haskell Report. As I use these data types, I will do so without much discussion; this is not, after all, a book on numerical analysis. But I will issue a warning whenever reasoning about numbers in a way that might not be technically sound.