Recursion

The Haskell designers recognized that iteration is a basic computational need, yet they didn't add a looping feature. There was no need, because Haskell promotes functions as the primary building block of computation, and functions can iterate by calling themselves. We saw several examples in the last chapter of how to repeat IO actions with impure recursive functions. Since recursion is key part of Haskell, let's see a few more examples of recursion, this time using pure functions.

Recursive Helpers

In computer graphics, images tend to have dimensions that are powers of 2. Such images can be accessed faster by hardware than images of other dimensions. If an image has dimensions that are not powers of 2, it is padded with extra pixels to reach the next power of 2. For example, this image originally had a resolution of 320×214, but it has been embedded inside a 512×256 image:

Let's call the next biggest power of 2 of a number its power-of-2 ceiling. The power-of-2 ceiling of 107 is 128. The ceiling of 30 is 32.

In C, we might write the power-of-2 ceiling function with this while loop that doubles an iterator until it reaches or just exceeds the target number:

int ceiling2(int target) {
  int power = 1;
  while (power < target) {
    power *= 2;
  }
  return power;
}

The power variable is mutated, so we'll have to make some significant changes to translate it to Haskell. A loop becomes the body of a recursive function. A mutated variable becomes a parameter. Each call to the recursive function passes along the variable's “mutated” value. An equivalent ceiling2 in Haskell might look something like this:

ceiling2 :: Int -> Int -> Int
ceiling2 target power =
  if power >= target then
    power
  else
    ceiling2 target (power * 2)

Adding a parameter makes the function harder to use. The C version only required one parameter, but the Haskell version requires two. On the initial call, the second parameter must be seeded with 1. Expecting a human to properly seed recursive parameters correctly is a big ask. A safer approach is to make the two-parameter function a hidden helper function and expose a simpler, one-parameter function that calls the helper function with the correct seed. This implementation uses a where clause to hide the function:

ceiling2 :: Int -> Int
ceiling2 target = helper 1
  where
    helper power =
      if power >= target then
        power
      else
        helper (power * 2)

This function demonstrates the three steps needed for translating loops into recursion:

1. Move the loop condition and body into a recursive function. The condition chooses between the base case that stops the iteration and the general case that triggers another iteration.
2. Turn each mutated variable into a function parameter.
3. Hide the function inside one that has a simpler interface and passes along the initial values to the parameters.

Recursing on Lists

A common way to apply a computation to a list is to break off the singular head element, process it individually, and recurse on the plural tail as needed. This has function, for example, iterates through and compares each head element to a target value:

has :: Eq a => a -> [a] -> Bool
has target items =
  if null items then  -- equivalent to items == []
    False
  else if target == head items then
    True
  else
    has target (tail items)

It stops recursing when it hits the empty list or when it finds the target.

Function has processes an existing list. What if we want to instead build a new list? The usual strategy is to prepend a single element onto the plural list returned by a recursive call. Prepending is done using the cons operator :.

For example, suppose we want to assemble a list containing a given number of zeroes. The length of the list n isn't known statically, so we can't use a list literal like [0, 0, 0]. Instead, we assemble the list dynamically, one zero at a time. A list of zero zeroes is []. A list of one is 0 : []. A list of two is 0 : 0 : []. A list of three is 0 : 0 : 0 : [].

We need a recursive function that performs this prepending n times. Like this one:

zeroes :: Int -> [Int]
zeroes n =
  if n == 0 then
    []
  else
    0 : zeroes (n - 1)