9.3 Mutable pairs and lists

The Pair datatype introduced in Chapter 5 is immutable. This means that once a Pair is created, the values in its cells cannot be changed.1

The MutablePair datatype is a mutable pair. A MutablePair is constructed using mcons, which is similar to cons but produces a MutablePair. The parts of a MutablePair can be extracted using the mcar and mcdr procedures, which behave analogously to the car and cdr procedures. A MutablePair is a distinct datatype from a Pair; it is an error to apply car to a MutablePair, or to apply mcar to an immutable Pair.

The MutablePair datatype also provides two procedures that change the values in the cells of a MutablePair:

set-mcar!: MutablePair $\times$ Value $\rightarrow$ Void: Replaces the value in the first cell of the MutablePair with the value of the second input.
set-mcdr!: MutablePair $\times$ Value $\rightarrow$ Void: Replaces the value in the second cell of the MutablePair with the value of the second input.

The Void result type indicates that set-mcar! and set-mcdr! produce no output.

Here are some interactions using a MutablePair:

> (define pair (mcons 1 2))
> (set-mcar! pair 3)
> pair
(3 . 2)
> (set-mcdr! pair 4)
> pair
(3 . 4)

The set-mcdr! procedure allows us to create a pair where the second cell of the pair is itself: (set-mcdr! pair pair). This produces the rather frightening object shown in Figure 9.5.

Figure 9.5: Mutable pair created by evaluating (set-mcdr! pair pair)

Every time we apply mcdr to pair, we get the same pair as the output. Hence, the value of (mcar (mcdr (mcdr (mcdr pair)))) is 3.

We can also create objects that combine mutable and immutable Pairs. For example, (define mstruct (cons (mcons 1 2) 3)) defines mstruct as an immutable Pair containing a MutablePair in its first cell. Since the outer Pair is immutable, we cannot change the objects in its cells. Thus, the second cell of mstruct always contains the value 3. We can, however, change the values in the cells of the mutable pair in its first cell. For example, (set-mcar! (car mstruct) 7) replaces the value in the first cell of the MutablePair in the first cell of mstruct.

Mutable Lists. As we used immutable Pairs to build immutable Lists, we can use MutablePairs to construct MutableLists. A MutableList is either null or a MutablePair whose second cell contains a MutableList.

The MutableList type is defined by a library. To use it, evaluate the following expression: (require racket/mpair). All of the examples in this chapter assume this expression has been evaluated. This library defines the mlist procedure that is similar to the list procedure, but produces a MutableList instead of an immutable List. For example, (mlist 1 2 3) produces the structure shown in Figure 9.6.

Figure 9.6: MutableList created by evaluating (mlist 1 2 3)

Each node in the list is a MutablePair, so we can use the set-mcar! and set-mcdr! procedures to change the values in the cells.

> (define m1 (mlist 1 2 3))
> (set-mcar! (mcdr m1) 5)
> (set-mcar! (mcdr (mcdr m1)) 0)
> m1
{1 5 0}; DrRacket denotes MutableLists using curly brackets.

Many of the list procedures from Chapter 5 can be directly translated to work on mutable lists. For example, we can define mlist-length as:

(define (mlist-length m)
  (if (null? m) 0 (+ 1 (mlist-length (mcdr m)))))

As shown in Exercise 9.4, though, we need to be careful when using mcdr to recurse through a MutableList since structures created with MutablePairs can include circular pointers.

Exercise 9.4. What is the value of (mlist-length pair) for the pair shown in Figure 9.5?

Exercise 9.5. $\left[\star \right]$ Define a mpair-circular? procedure that takes a MutablePair as its input and outputs true when the input contains a cycle and false otherwise.

  1. The mutability of standard Pairs is quite a controversial issue. In most Scheme implementations and the standard definition of Scheme, a standard cons pair is mutable. But, as we will see later in the section, mutable pairs cause lots of problems. So, the designers of DrRacket decided for Version 4.0 to make the standard Pair datatype immutable and to provide a MutablePair datatype for use when mutation is needed.