The functions that we considered so far only used a fixed number of elementary operations. Even

distance :: ColourPoint -> ColourPoint -> Float
distance (x1, y1, colour1) (x2, y2, colour2) 
  = sqrt (fromIntegral (dx * dx + dy * dy))
  where
    dx = x2 - x1
    dy = y2 - y1

needs exactly one addition, two subtractions, two multiplications, the invocation of fromIntegral, and one square root — which makes seven operations. If conditional expressions or guards are used, the number of operations may vary, but we can still place an upper limit on the number of operations (independently of the input passed to the function).

However, many problems cannot be solved by functions limited in this way; indeed, some functions —depending on the input— have to perform an arbitrarily large number of operations. In the following, we look at a programming technique known as recursion as the fundamental mechanism to implementing such functions in Haskell.

Recursion over Numbers

Consider the function natSum, which computes the sum of all natural numbers up to a limit, or the Prelude function product, which computes the product of all of the elements of an integer list:

The above are not actual function definitions, since the notation “⋯” is not valid Haskell. However, they illustrate the meaning of the two functions in reasonably formal terms. From this specification of the meaning, we see that both functions require n operations to compute their result. Thus, we can make two important observations:

Computing n + ⋯ + 2 + 1 + 0

Let us start with the simplest case: recursion over the natural numbers. How can we define the function natSum :: Num a => a -> a, which sums up all natural numbers from zero up to a given number n? It should behave as natSum n = n + ⋯ + 1 + 0 but how can we substitute the ellipsis by working program code?

To get an idea of what we would like to happen, consider the following rules describing the computations to be performed by natSum for input values up to 5:

natSum 0 =                     0
natSum 1 =                 1 + 0 
natSum 2 =             2 + 1 + 0
natSum 3 =         3 + 2 + 1 + 0
natSum 4 =     4 + 3 + 2 + 1 + 0
natSum 5 = 5 + 4 + 3 + 2 + 1 + 0
...

The above are legal Haskell definitions, but obviously, we would need an unbounded number of definitions to define natSum for every possible input. There is, however, an observation that comes to our rescue: each of the above equations contains computations that already appear in the previous equations. For example, for natSum 5, we have to evaluate 0 + 1 + 2 + 3 + 4 + 5, but the subcomputation 0 + 1 + 2 + 3 + 4 already appears in natSum 4. This seems like good news, as it allows us to reuse earlier equations for later ones. In other words, we could redefine natSum 5 as

natSum 5 = 5 + natSum 4

In fact, except for the first equation, we can systematically reuse the immediately preceding equation:

natSum 0 = 0
natSum 1 = 1 + natSum 0
natSum 2 = 2 + natSum 1 
natSum 3 = 3 + natSum 2 
natSum 4 = 4 + natSum 3 
natSum 5 = 5 + natSum 4 
...

Interestingly, all equations —except for the first one— now look exactly the same; they just use different values. This seems like an ideal situation to once more apply the trick that we already used when we introduced function definitions, i.e., we use abstraction to replace concrete values by variables and, in this way, we distill a repeating pattern out of the above equations. The repeating pattern is

natSum n = n + natSum m

where we know that m always equals n - 1. In other words, given the two rules

natSum 0 = 0
natSum n = n + natSum (n - 1)

we seem to have captured the essence of natSum. In natural language, we could describe this essence as follows:

This sounds sensible; indeed, it is sufficient to compute the result of natSum for every case. For example, let us look at the stepwise evaluation of one application of natSum:

This obviously works the way we intended it to work. The above definition of natSum is called recursive, because natSum itself is used in the definition of natSum — i.e., a recursive function is a function that makes use of itself in its definition.

Recursive function definitions have at least two cases: the base case and the recursive case (or stepping case). The base case specifies what to do in the simplest form of input (where the function stops calling itself), whereas the stepping case includes the recursive use of the function by itself:

natSum :: Num a => a -> a
natSum 0  = 0                    -- base case
natSum n  = n + natSum (n - 1)   -- recursive/stepping case

Later, we will encounter recursive functions with more than one base case and/or more than one recursive case — but there will always be at least one of each kind.

natSum :: Num a => a -> a
natSum n = if n == 0 
              then 0 
              else n + natSum (n - 1)

It contains only one equation and makes the case distinction explicit through a conditional.

A question that might come up during the definition of natSum is, what happens if we call this function with an argument that causes the recursive case to move away from, rather than towards the base case. For example, what does natSum (-1) result in? As the recursive case is applicable, the argument will be reduced to -2, -3, and so on, which means that we enter an infinite computation. In other words, natSum is not defined for arguments smaller than 0.

This is another instance of the concept of partial functions, which we discussed in Fundamentals. However, here the problem is not simply a lack of an undefined input pattern, but that the function fails to terminate for some of the input values admitted by its type signature. To replace non-termination by a proper runtime error, we can use the previously discussed error function:

natSum :: (Num a, Ord a) => a -> a
natSum 0              = 0
natSum n  | n > 0     = n + natSum (n - 1) 
          | otherwise = error "natSum: Input value too small!"

The following screencast demonstrate how to develop natSum's recursive definition interactively with the help of a Haskell playground.

Recursion and Lists

List construction

We can not only use recursion to calculate numbers, but also to build lists: A simple example of such a recursive function is repeatN, which produces a list that contains a given item n times; i.e., has type

repeatN :: Int -> a -> [a]

To find a suitable definition for the function, we first consider what an appropriate base case might look like. Let us assume that we want the function to work for zero repetitions. Then, the expression repeatN 0 x would have to return an empty list, which fully specifies the base case.

Next, we have to find a suitable recursive case. If we already had a definition that works for repeatN (n - 1) x, how would we extend the result of repeatN (n - 1) x such that it gives us the result for repeatN n x? Another way to ask the same question is, which operation is it that should be repeated in the recursive definition? The answer is using the colon operator to add another copy of the replicated item to the result string. So, overall, we get

repeatN :: Int -> a -> [a]
repeatN 0 x  = []
repeatN n x  = x : repeatN (n - 1) x

Given the material that we covered so far, it should be relatively straightforward to write a function that, when given a string, produces a list containing all of the possible suffixes of that string. For example, we would have

The base case is when we have an empty string; then, we have no suffix, so we return the empty list:

suffixes "" = []

we only need to add the string Hello at the front of the result to get the value of suffixes Hello. Moreover, as

suffixes :: String -> [String]
suffixes ""  = []
suffixes str = str : suffixes (tail str)

In other words, after adding the current string str, we only need the suffixes of tail str.

Note that we can build lists recursively using only the empty list [] and the list forming operator (:). As these two suffice to build any list, they are regarded as the basic list forming constructors. In fact, they are usually called nil and cons, respectively.¹

Lists as recursive structures

All lists are constructed from nil and cons, where the following equality illustrates the correspondence between the square bracket and the nil/cons notation:

Due to the repeated occurrence of cons, the right hand side exposes the recursive structure of lists. For each element x_i in a list, we have one cons operator including this element into the list. Finally, each list is terminated by nil. This representation not only makes the recursive nature of lists explicit, but it is, in fact, the original representation of lists. The closed [x₁, x₂,… , x_n] notation is only a convenient shorthand.

Pattern matching on lists

The nil and cons operators are so elementary that we not only use them to construct lists, but also to decompose them; much as we did with pattern matching to decompose tuples in this definition of fst:

fst :: (a, b) -> a
fst (x, y)  = x

In a similar manner, we use pattern matching to decompose lists into their first element and the rest of the list; i.e., into the two components joined together by cons. In fact, this is exactly what the two functions head and tail do to extract the first element and the remaining elements from a list:

head :: [a] -> a
head (x:xs) = x

tail :: [a] -> [a]
tail (x:xs) = xs

In other words, they yield the two values that are used to compose a list using the cons operator. Thus, for every non-empty list xs, we have the equality:

Therefore, the first component passed to cons is often called the head of the new list and the second component the tail.

In Fundamentals, we discussed that head and tail are partial functions as they lack a pattern matching the empty list. If we want to define a total function over lists with pattern matching, we have to specify at least two cases, one for the case where the input is an empty list and a second for the case where it is not empty; i.e., can be regarded as being constructed by a cons operator. The following function (also included in the Prelude), which checks whether a given list is empty, covers both cases:

null :: [a] -> Bool
null []     = True
null (x:xs) = False

Mapping: applying an operation to every element of a list

Combining pattern matching with recursion, we can traverse a list from beginning to end. Let's say we have a list of numerals and want to compute the square of each element and return the resulting squared numbers as a new list:

For the base case, that is, empty list, we just return the empty list. If the list consists of a head x and a tail xs (pronounced: xes, as in boxes), we build a new list, with x * x as head, and the result of the recursive call allSquares xs as tail:

allSquares :: Num a => [a] -> [a]
allSquares []       = []
allSquares (x : xs) = x * x : allSquares xs

With the same list traversal pattern, we can define a function allToUpper which converts a string to upper case.

To do so, we use a function defined in the standard module Data.Char called toUpper :: Char -> Char, which converts a lower case letter to an uppercase letter and leaves all other characters as they are:

import Data.Char 

allToUpper :: String -> String
allToUpper []                 = []
allToUpper (chr : restString) = toUpper chr : allToUpper restString

The following screencast demonstrates the interactive development of allToUpper.

Apart from the names of the functions and variables, and that we have to import the module Data.Char, the functions allSquares and allToUpper are almost identical — both follow the pattern

recursiveFunction []       = []
recursiveFunction (x : xs) = doSomethingWith x : recursiveFunction xs

Such functions can get additional arguments than the list as parameter. For example, re-using the definition ColourPoint from Fundamentals, we might define function that, given a point :: ColourPoint together with a list of points points :: [ColourPoint], calculates the distance of each point in points to point:

distancesFromPoint :: ColourPoint -> [ColourPoint] -> [Float]
distancesFromPoint point []
  = []
distancesFromPoint point (p : ps)
  = distance point p : distancesFromPoint point ps

This function still follows the same pattern of recursive list traversal as do allSquares and allToUpper.

Filtering: removing elements from a list

The two functions allSquares and allToUpper produced lists with exactly the same length as their input list. Let's continue with a string example: given a string, how can we extract all the digits. For example, extractDigits "das43 dffe 23 5 def45" should return the string "4323545", using the function isDigit :: Char -> Bool from Data.Char to check whether a single character is a digit.

The base case is (as almost always), straightforward: if we get an empty string, we just return the empty string. The recursive case is slightly more complicated than in previous examples: we have to check if the first character is a digit in which case we include it in the result. Otherwise, we ignore it and just call extractDigits on the tail of the input list:

import Data.Char

extractDigits :: String -> String
extractDigits []
  = []
extractDigits (chr : restString)
  | isDigit chr = chr : extractDigits restString
  | otherwise   =       extractDigits restString

While the structure of this function definition is still quite close to that of allSquares and allToUpper, the most obvious difference is the use of guards to distinguish between two different recursive cases: one that uses chr, the first element of the input list, and one that disregards that element.

Another example, using the ColourPoint type again, receives a point and a radius in addition to a list of points as arguments, and then, yields a list of all points which are located within the radius around the point passed as the first argument:

inRadius :: ColourPoint -> Float -> [ColourPoint] -> [ColourPoint]
inRadius point radius []
  = []
inRadius point radius (p : ps)
  | distance point p <= radius = p : inRadius point radius ps
  | otherwise                  =     inRadius point radius ps

Reductions: combining the elements of a list

Another important pattern of recursive functions are reductions, which combine the elements of a collection, such as a list, into a new value. An example is the product function, which we mentioned at the start of this chapter and which computes the product of all the elements of a given list:

Using our knowledge about the recursive nature of lists, we can rephrase the task as defining a function product computing

By fixing a suitable order for the calculation of the products on the right hand side and adding the neutral value of multiplication (i.e. 1), we get the right hand side exactly into the same format as the recursive list representation, replacing : with *, and [] with the neutral element of multiplication, 1:

Thus, we can use a recursive function definition following the recursion inherent in the list data structure — this is known as structural recursion. For the base case, we have product applied to an empty list; i.e., nil. From the above specification of product, it is clear that we have to return 1 (the neutral value) in this case:

product [] = 1

The recursive case is that of a non-empty list, where cons allows us to decompose the list into a head and a tail. We multiply the head with the result of recursively applying product to the tail of the list. So, overall, we have

product :: Num a => [a] -> a
product []     = 1
product (x:xs) = x * product xs

This definition clearly does what we said before. It replaces nil by 1 and cons by multiplication. Reductions like product constitute a common pattern of structurally recursive functions.

Inside reductions. To see how a list traversal proceeds, let us look at the stepwise evaluation of product [3, 5, 6], which we write as product (3:(5:(6:[]))) to make the recursive structure of the list explicit:

A general recursive pattern of reductions. There are many other examples of commonly used reductions. For instance, calculating the sum of a list is almost identical to the product function:

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

Calculating the minimum or maximum of a list is also similar. However, in this case, it is not clear what the return value for an empty list ought to be. One option is to leave the case of empty lists undefined and proceed as follows (note that we are using min as infix operator by enclosing it in backquotes):

minList :: [Int] -> Int
minList (x:[]) = x
minList (x:xs) = x `min` minList xs

The first equation applies whenever the argument list has exactly one element. The second, by itself, applies whenever a list has at least one element; so, the two patterns overlap. However, for any given argument, code evaluation tests patterns starting with the first equation and then working its way down. The first equation with a matching pattern will be selected. Hence, if a list has exactly one element, minList will always pick the first equation; it will only select the second equation if the argument list has more than one element. If the list is empty, the result is undefined; i.e, this version of minList is a partial function.

Alternatively, we might consider the largest possible value of Int type a neutral value of the min function and use it to define the base case. In Haskell, the range of Int is implementation dependent; hence, we use the Prelude value maxBound, which yields the largest Int value:²

minList :: [Int] -> Int
minList []     = maxBound
minList (x:xs) = x `min` minList xs

Looking at these examples, the general pattern for list reductions takes a list of the form

and replaces cons (:) and nil ([]) with a binary function op and some starting value n, respectively, to yield

More examples of reductions. The result of a reduction may even be another list: in fact, the list append operator (++) :: [a] -> [a] -> [a], which we used in First Steps, is an instance of such a function. This becomes obvious when we denote the behaviour of (++) as follows:

Here, we replace cons (:) by itself (i.e., it is the binary operator of this reduction) and we replace nil ([]) by the appended list ys. With that insight, the definition of (++) is straightforward (using infix notation for (++) in the definition of the two equations):

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Lists in Haskell can be nested; i.e., we can have lists of lists of integer numbers, such as

[[5, 6, 2], [], [4, 2]]

A commonly used Prelude function that takes a list of lists and reduces it to a list with one nesting level fewer is concat — an example use is

As we can join two lists with the ++ operator, we can write a specification for concat as follows:

This translates directly into the recursive pattern for reductions, replacing (:) by (++) and [] by itself:

concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

Finally, let's look at a slightly trickier function. The function reverse :: [a] -> [a] reverses the order of elements in a list:

Interestingly, we can express reverse as a reduction as well. This may seem counterintuitive at first, considering the general specification of reverse:

Let us take a step back. So far, we have always replaced cons (:) by some existing standard function (such as (+) or min). How about replacing it by a function of our own design instead?

In other words, to implement reverse using the reduction pattern, we are looking for a function snoc that we can use as follows:

The function snoc needs to have the same type signature as (:) :: a -> [a] -> [a]; i.e.,

snoc :: a -> [a] -> [a]

Considering the first invocation of snoc in the call reverse "Hello" (which is the same as reverse ('H':'e':'l':'l':'o':[])), we know that we need

The cons operator (:) can only attach elements at the head of a list and snoc is essentially the reverse of that (hence, the name). To attach at the end, we need to use (++) — i.e., we have got

x `snoc` xs = xs ++ [x]

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = x `snoc` reverse xs

Given the simplicity of snoc, we may like to inline its definition into reverse, which gets us

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

This approach of using our own function to replace (:) by way of the recursive pattern for reductions is a very powerful technique. In fact, any structurally recursive function can be implemented like that. This doesn't always lead to an intuitive definition of a given function, but it is certainly possible.

Getting back to our definition of reverse, the definition works, but it has a serious problem: from the definition of (++), we know that to append a single element [x] at the end of a list, we have to recurse down the whole list until we reach [], which we then replace by [x]. Reverse has to do this in every single recursive step! That is quite computationally expensive.

Left-associative reductions

The recursive pattern that we discussed so far replaces cons (:) and nil ([]) in

with a binary function op and some starting value n starting from the right and proceeding to the left:

In other words, we start by computing (x_n `op` []). Then, we use that result to compute (x_n-1 `op` (x_n `op` [])), and so forth. This is often called a right-associative reduction or a reduction from the right.

That is often what we want, and for associative operators, such as addition and multiplication, where we have

In other cases, we would actually like to proceed from the left to the right and compute

This, in particular, implies that we combine the starting value n from the left with x₁; instead of combining it from the right with x_n.

deductFromAccount :: Int -> [Int] -> Int

which gets the initial balance of an account in cents together with a list of deductions from that account in the order in which they are to be performed. On that basis, it needs to calculate the resulting account balance with the following exception: if a deduction would result in a negative account balance, the function should return an error message:

To implement this function, we need to implement a reduction proceeding from left to right over the input list, where the initial balance is the starting value n from our pattern above. We need to compute

for a suitable definition of deduct. It needs to use a conditional or guard to check whether the current balance is larger than the next deduction:

balance `deduct` x 
  | balance < x = error ("Your account balance is " ++ show balance ++
                         " - cannot deduct " ++ show x ++ " cents")
  | otherwise   = balance - x

leftReduce n []     = n
leftReduce n (x:xs) = leftReduce (n `op` x) xs

By substituting balance for n and deduct for op, and then, inlining deduct, we get the complete definition for deductFromAccount:

deductFromAccount balance []
  = balance
deductFromAccount balance (d : ds)
  | balance < d = error ("Your account balance is " ++ show balance ++
                         " - cannot deduct " ++ show d ++ " cents")
  | otherwise   = deductFromAccount (balance - d) ds

The parameter balance acts as an accumulator, passing down information of what happened earlier in the list.

In contrast to the right-associative recursive pattern, where the work (adding the numbers, computing the minimum, etc) happens after the recursive function call returns a result, the work here is in the computation of the accumulator, which is simply being returned by the base case.

A second example of a left-associative reduction. Another example that requires a reduction from the left is the function stringToInt :: String -> Int, which converts a string of digits into the corresponding Int value:

We can use the function digitToInt :: Char -> Int from module Data.Char to convert a single character, but the calculation for a string is more complicated:

As with balance, we use an accumulator argument to pass the result of the preceding calculations on to the recursive calls. In each recursive step, we have to multiply the accumulator by ten and add the digit value of the current character. To this end, we define a helper function stringToIntAcc that implements the left-reduction using an additional argument as the accumulator. This time around, we omit the individual steps of instantiating the left-reduction pattern and implementing the application specific version of the combination function op; instead, we immediately proceed to the final recursive definition and leave the skipped steps as an exercise.

import Data.Char

stringToInt :: String -> Int
stringToInt str = stringToIntAcc 0 str

stringToIntAcc :: Int -> String -> Int
stringToIntAcc acc []
  = acc
stringToIntAcc acc (chr : restString) 
  = stringToIntAcc (10 * acc + digitToInt chr) restString

Since the function stringToIntAcc is only a helper function and not called from anywhere else but stringToInt, we would like to define it as a function that is only visible inside the body of stringToInt; i.e., so that stringToIntAcc is local to stringToInt. We can do this in the same manner as for variable bindings using a where clause:

stringToInt :: String -> Int
stringToInt str = stringToIntAcc 0 str
  where
    stringToIntAcc :: Int -> String -> Int
    stringToIntAcc acc []
       = acc
    stringToIntAcc acc (chr : restString) 
       = stringToIntAcc (10 * acc + digitToInt chr) restString

Revisiting reverse. When we implemented the reverse function with a right-to-left reduction, we observed at the end that the code is quite inefficient. The recursion for reverse visits each element of the input list once, and then, calls (++) once for each element, which is itself a recursive function that visits each element of its first argument. Overall, this implies that for a list of size n, our implementation of reverse performs in the order of n² function calls. This is excessive. We would expect to be able to do it with about n function calls.³

The reason for the use of (++), and hence the inefficiency, in our definition of reverse was to add a single element x to a list xs using the expression xs ++ [x]. This was necessary as we used the right-to-left reduction pattern. This raises the question of whether we can do better with left-to-right reduction. Again, we leave writing out the left-associative reduction pattern for reverse as an exercise and go straight to the final implementation.

The intuition for the implementation of fastReverse is that the accumulator argument of the left-to-right reduction carries the already reversed prefix of the list down the recursive calls. As (:) is left-associative and we start with the leftmost element of the input list, we can add it with (:) to the accumulator to end up with the entire reversed list when the recursion encounters the base case.

fastReverse :: [a] -> [a]
fastReverse xs = reverseAcc [] xs
  where
    reverseAcc :: [a] -> [a] -> [a]
    reverseAcc accList []     = accList
    reverseAcc accList (x:xs) = reverseAcc (x : accList) xs

As there is a constant number of operations per recursive call of reverseAcc, this new definition meets our performance goal. This becomes obvious when using stepwise evaluation on an example invocation:

Associative binary operations. As mentioned earlier, we can use both right-to-left or left-to-right reduction in the case where the binary operation of the reduction is associative and the starting value is a neutral value for the binary operation. As an example, consider the following definition of sum, which sums up the elements of a list (and is almost the same as product, but using addition instead of multiplication).

sum :: Num a => [a] -> a
sum xs = sumAcc 0 xs
  where
    sumAcc :: Num a => a -> [a] -> a
    sumAcc acc []       = acc
    sumAcc acc (x : xs) = sumAcc (x + acc) xs

Due to certain optimisations expected of a Haskell compiler, this version of sum is in fact more efficient than the version using the right-to-left reduction pattern, as it is able to execute using a constant amount of call stack memory. These operational subtleties are, however, an advanced topic that we will save for later.

Reductions are a very powerful recursive pattern. We will also revisit them in the context of more advanced chapters.

Combining different patterns

We discussed four recursive patterns over lists: mapping, filtering, and two forms of reductions. Some problems require a combination of these patterns. Two example are

We can solve the first problem —i.e., computing the sum of all even elements— by first filtering out all even elements, and then, calculating the sum of these even elements as follows:

-- To keep things shorter, we use the 'sum' function defined in the 'Prelude'.
sumEvenElems :: Num a => [a] -> a
sumEvenElems xs = sum (filterEven xs)
  where
   filterEven [] 
     = []
   filtertEven (x : xs)
     | even x    = x : filterEven xs
     | otherwise = filterEven xs

Alternatively, we can pick out the even elements and compute the sum in one recursive traversal:

sumEvenElems :: Num a => [a] -> a
sumEvenElems []
  = 0
sumEvenElems xs
   | even x    = x + sumEvenElems xs
   | otherwise = sumEvenElems xs

Similarly, we can, on the one hand, implement the sum of square roots of all positive numbers as the application of three separate functions:

sumOfSquareRoots xs = sum (allSquareRoots (filterPositives xs))
  where
    allSquareRoots []     = []
    allSquareRoots (x:xs) = sqrt x : allSquareRoots xs

    filterPositives [] 
      = []
    filterPositives (x:xs)
      | x > 0     = x : filterPositives xs
      | otherwise = filterPositives xs

sumOfSquareRoots [] 
  = 0
sumOfSquareRoots (x:xs)
  | x > 0     = sqrt x + sumOfSquareRoots xs
  | otherwise = sumOfSquareRoots xs

Which is the better style? Generally, the first version using separate traversals is consider better style, as it is often more readable and, especially, because there is a set of powerful Prelude functions (which we will discuss in a later chapter) that we can usually use instead of writing the individual (quite simple functions) ourselves. Hence, we get better code reuse.

We might be concerned that the easier to read version is less efficient. However, due to Haskell's, so-called, lazy evaluation execution strategy, the overhead is significantly less than in most other languages. Moreover, a good Haskell compiler can usually derive the one traversal version from the more elegant multiple traversal version using a process called fusion. In other words, unless performance profiling of a program shows that you need to hand-code the more efficient version, you should always favour readability.

A More Complex Example

Let us consider the function closestPoint :: Point -> [Point] -> Point, which, given a point p and a list of points points, returns the point in points which is located closest to p. (If there is more than one such point, the one appearing first is returned.) The type Point is just a synonym for a pair of floating point values:

type Point = (Float, Float)

See function distance, at the beginning of this chapter, on how to calculate the distance between two points. The following screencast implements closestPoint to illustrate the development of a more complex recursive function.

Exercises

The word “nil” actually stands for “Not In List” and “cons” is an abbreviation for “(list) constructor”.↩
Strictly speaking, maxBound :: Bounded a => a is a member of the type class Bounded and works on a range of types, not just Int.↩
We will discuss the runtime performance of recursive function definitions in more detail in a later chapter.↩

Recursion