Haskell

3.4 Data Recursion

So far we have used recursion as a technique for defining functions. Recursive

functions are useful in nearly all programming languages, and they are especially

important for programming with data structures like trees and graphs.

Another important programming technique uses recursion to define data structures;

this is called data recursion.

The idea is to define circular data structures. Here is one way to define an

infinitely long list where every element is 1:

f :: a -> [a]

f x = x : f x

ones = f 1

Each time the recursive function f is applied, it uses (:) to construct a new

list element containing x. As a result, there is no bound on how much computer

memory will be required to represent ones; this depends on how much of the

computation is actually demanded by the rest of the program.

However, its possible to represent ones very compactly with a circular list,

defined with recursion in the data rather than in a function:

twos = 2 : twos

Figure 3.1 shows the internal representations of ones and twos. Mathematically,

the value of both is a list that is infinitely long. However, the circular

definition requires far less memory.

A data structure consisting of nodes connected by links is called a graph.

Graphs can be constructed by defining each node with an equation in a let

expression; this means that each node can be referred to by any other node

(including even itself). For example, the following Haskell definition creates a

circular data structure, where the internal names a, b, and c are used to set

up the links:

object = let a = 1:b

3.5. SUGGESTIONS FOR FURTHER READING 59

ones 1 1 1 ...

twos 2

Figure 3.1: Circular and Non-circular Infinite Lists

b = 2:c

c = [3] ++ a

in a

Data recursion does not work in all programming languages. If you were

to try defining twos in C, for example, the program would go into an infinite

loop. Haskell, however, is careful to delay the evaluation of an expression until

it is actually needed. This technique is called lazy evaluation, and it makes

possible a number of useful programming techniques including data recursion.

Lazy evaluation also plays a role in making it easier to use mathematics to

reason formally about Haskell programs.

Read Section 3.4 before attempting this Draw the linked list represented by the object defined in the book (page 58,59) object = let a = 1:b b= 2:0 c = [3] ++ a in a