Recursion

The functions and datatypes we have written so far are limited in power:

• We lack a mechanism to repeat a number of computation steps. If we want some computation to be repeated five times, we explicitly have to write five function calls. If we want six instead, we have to modify the program and add a sixth call.
• Similarly, we lack a mechanism to arbitrarily extend the size of a data structure. If we want a data structure that holds five values, we have to write an algebraic datatype (ADT) definition with a constructor that has five fields. If five is not enough, and we want six instead, we need to modify existing definitions.

These extensions of existing definitions quickly become unwieldy for larger sizes, and we cannot dynamically determine the number at runtime (at least not beyond the cases we have explicitly foreseen while writing the program).

Imperative programs solve this problem in two different ways for repeated computations and data structure...

Standard libraries

From this chapter onward, we will more actively see and use code from the Haskell standard libraries. This serves two purposes. Firstly, functions in the standard libraries often serve as good examples of particular programming patterns. Secondly, knowing these library functions (alongside the language features and programming patterns) makes us more fluent programmers.

Haskell comes with a rich set of standard libraries. The most prominent library is called the Prelude. It comes with some of the most heavily used functionality and does not need to be explicitly imported; it is imported by default. Another library that we will use frequently is Data.List, which contains functions related to lists. This library has to be imported explicitly by putting the following declaration at the top of the source file:

import Data.List

This imports all the functionality provided by the library. If only a small subset of that functionality should be imported, it can be...

Lists

As a first example of recursion, we will study Haskell’s built-in datatype for lists.

List syntax

A list is a sequence of an arbitrary number of elements of some type. For instance, seasons is a list of strings:

seasons :: [String]
seasons = ["spring","summer","fall","winter"]

The signature shows that the list type is written as two square brackets, [ and ], with the type of elements between them. In the case of seasons, the element type is String. The equation of seasons shows that a list value is written as a comma-separated list of elements between square brackets.

As the notation suggests, the list type is parametric in its element type. For example, redSuits is a list of Suits:

redSuits :: [Suit]
redSuits = [Hearts,Diamonds]

This uses the Suit datatype from the previous chapter.

A special case of a list is an empty list – for example, of Bool elements:

noBools :: [Bool]
noBools = []

Another...

Custom list processing

We can write our own functions to process lists in very much the same style as we wrote functions over algebraic datatypes in the previous section.

As a first example, let us write evenLength. This function determines whether a given list has an even length:

evenLength :: [a] -> Bool
evenLength []     = True
evenLength (x:xs) = not (evenLength xs)

The empty list case is the base case – the empty list does have an even length. The non-empty list case is the recursive case. We determine whether the tail, xs, has an even length and then negate its result to determine whether (x:xs) has an even length.

It is instructive to see how a recursive function such as evenLength is evaluated:

  evenLength (1 : 2 : 3 : [])
= not (evenLength (2 : 3 : []))
= not (not (evenLength (3 : [])))
= not (not (not (evenLength [])))
= not (not (not True))
= False

The preceding snippet shows a sequence of simplification steps...

Recursive datatypes

While the list type is predefined, we can also define our own recursive algebraic datatypes.

Arithmetic expressions

The Expr datatype is a symbolic representation of arithmetic expressions:

data Expr = Lit Int | Add Expr Expr

The recursive datatype Expr has two constructors:

• The first, Lit, is the base case; it represents a trivial expression that is just an Int constant (aka literal)
• The second constructor, Add, is a recursive case; an addition is built out of two smaller expressions (also called subexpressions)

For example, we symbolically represent 2 + 5 as Add (Lit 2) (Lit 5).

Of course, a symbolic expression is just data; it does not compute. To actually evaluate expressions, we need to write an evaluation function:

eval :: Expr -> Int
eval (Lit n)     = n
eval (Add e1 e2) = eval e1 + eval e2

This function has a base case that returns the Int value of the literal and a recursive case for Add...

Structural recursion

You may have noticed that the recursive functions we have written so far in this section show a great deal of commonality. This is no coincidence, as they are, in fact, all based on the same recipe for writing recursive functions, known as structural recursion. Structurally recursive functions are sometimes also called catamorphisms.

Structural recursion on lists

Let us revisit two recursive functions on lists we wrote earlier and expose their common structure:

evenLength :: [a] -> Bool
evenLength []     = True
evenLength (x:xs) = not (evenLength xs)
Prelude
sum :: [Integer] -> Integer
sum []     = 0
sum (x:xs) = x + sum xs

These two definitions follow a standard recursion scheme to define functions over a list:

f :: [A] -> B
f []     = n
f (x:xs) = c x (f xs)

It features two equations, one for the empty list pattern, [], and one for the non-empty list pattern, ...

Variants on structural recursion

Not all recursive functions can be written in a basic structurally recursive manner on an algebraic datatype. Here, we will review a range of common variations and extensions.

Primitive recursion

Structurally recursive functions only use the recursive occurrences of a datatype (e.g., the tail of a list or the subtrees of a tree) in recursive calls. Consider the following predefined function, which multiplies all the elements of a list:

Prelude
product :: [Integer] -> Integer
product []     = 1
product (x:xs) = x * product xs

The body of the recursive case only uses the tail of the list, xs, in the recursive call product, xs. This is an essential part of structural recursion; the tail cannot be used in any other way.

Primitive recursive functions (also called paramorphisms) relax this condition; the recursive occurrences can be used in other ways. For example, the following function computes all the tails of...

Non-structural recursion

You can write recursive functions that do not follow the structure of a datatype. Some of them are problematic and to be avoided, while others are legitimate. We will review several patterns here.

Non-termination

Non-terminating functions are an important class of recursive functions that are non-structural. Here is a first, small example:

loop :: Integer -> Integer
loop x = loop x

Here is an example derivation:

  loop 5
= loop 5
= loop 5
= …

Clearly, this derivation never terminates; it just repeats itself endlessly. If you have inadvertently invoked such a non-terminating function call in GHCi, you can abort it with the Ctrl + C key combination.

While the loop function is blatantly non-terminating, the source of non-termination may often not be so apparent when it dresses up in a lot more code (such as mutually recursive functions).

A slightly different pattern of non-termination is the following:

diverge :: [Integer...

Summary

This chapter introduced the concept of recursive definitions for both functions and datatypes. We saw how recursive datatypes allow us to express values of an arbitrarily large size, with Haskell’s built-in list type as a notable example. Functions that process such recursive datatypes are themselves naturally recursive. More specifically, when the recursive structure of a function aligns with that of the datatype it processes, we speak of structural recursion. We saw several common variations in structural recursion as well as a few examples of non-structural recursion.

In Chapter 4, Higher-Order Functions, we will see how repeated patterns in function definitions, such as the structural recursion scheme we used here, can themselves be captured as reusable code. The key mechanism that enables this is the ability to pass functions as parameters to other functions. Such functions with function parameters are called higher-order functions.

Questions

1. How can we create lists and manipulate them with common predefined functions?
2. How can we write custom functions over lists?
3. How can we define and process custom recursive algebraic datatypes?
4. What is structural recursion?
5. How can we work with common variations on structured recursion?
6. What are examples of recursion that are not structural?

Answers

1. Lists can be created with the syntax [e1,...,en] where e1,...,en is a comma-separated list of elements. The empty list is just written []. More primitive notation for constructing a composite list is (e:es), where e is the first element of the new list and es is an existing list that becomes the tail (or remainder) of the new list.

   Lists can be processed with a range of predefined list functions, with list comprehensions and with custom functions (see the next question).

2. Functions over lists can be defined by pattern matching, just like for other ADTs. The typical form distinguishes two cases, that of the empty list [] and of the non-empty list (x:xs).
3. ADT definitions are recursive when we mention the type we are defining in one or more of its constructors field types. They are processed, like ordinary ADTs, with pattern matching on the constructors. Usually the functions are recursive and make use of structural recursion (see the next question).
4. In structural...