9.4.1 List mutators

All the procedures for changing the value of a list in Section 5.4.3 actually do not change any values; instead they construct new lists. When our goal is only to change some elements in an existing list, this wastes memory constructing a new list and may require more running time than a procedure that modifies the input list instead. Here, we revisit some of the procedures from Section 5.4.3, but instead of producing new lists with the desired property these procedures modify the input list.

Example 9.2: Mapping

The list-map procedure (from Example 5.4) produces a new list that is the result of applying the same procedure to every element in the input list.

(define (list-map f p)
  (if (null? p) null (cons (f (car p)) (list-map f (cdr p)))))

Whereas the functional list-map procedure uses cons to build up the output list, the imperative mlist-map! procedure uses set-car! to mutate the input list's elements:

(define (mlist-map! f p)
  (if (null? p) (void)
      (begin (set-mcar! p (f (mcar p)))
             (mlist-map! f (mcdr p)))))

The base case uses (void) to evaluate to no value. Unlike list-map which evaluates to a List, mlist-map! is evaluated for its side effects and produces no output.

Assuming the procedure passed as f has constant running time, the running time of the mlist-map! procedure is in $\Theta(n)$ where $n$ is the number of elements in the input list. There will be $n$ recursive applications of mlist-map! since each one passes in a list one element shorter than the input list, and each application requires constant time. This is asymptotically the same as the list-map procedure, but we would expect the actual running time to be faster since there is no need to construct a new list.

The memory consumed is asymptotically different. The list-map procedure allocates $n$ new cons cells, so it requires memory in $\Theta(n)$ where $n$ is the number of elements in the input list. The mlist-map! procedure is tail recursive (so no stack needs to be maintained) and does not allocate any new cons cells, so it requires constant memory.

Example 9.3: Filtering

The list-filter procedure takes as inputs a test procedure and a list and outputs a list containing the elements of the input list for which applying the test procedure evaluates to a true value. In Example 5.5, we defined list-filter as:

(define (list-filter test p)
   (if (null? p) null
       (if (test (car p)) (cons (car p) (list-filter test (cdr p)))
           (list-filter test (cdr p)))))

An imperative version of list-filter removes the unsatisfying elements from a mutable list. We define mlist-filter! using set-mcdr! to skip over elements that should not be included in the filtered list:

(define (mlist-filter! test p)
  (if (null? p) null
      (begin (set-mcdr! p (mlist-filter! test (mcdr p)))
             (if (test (mcar p)) p (mcdr p)))))

Assuming the test procedure has constant running time, the running time of the mlist-filter! procedure is linear in the length of the input list. As with mlist-map!, the space used by mlist-filter! is constant, which is better than the $\Theta(n)$ space used by list-filter.

Unlike mlist-map!, mlist-filter! outputs a value. This is needed when the first element is not in the list. Consider this example:

> (define a (mlist 1 2 3 1 4))
> (mlist-filter! (lambda (x) (> x 1)) a)
{2 3 4}
> a
{1 2 3 4}

The value of a still includes the initial 1. There is no way for the mlist-filter! procedure to remove the first element of the list: the set-mcar! and set-mcdr! procedures only enable us to change what the mutable pair's components contain.

To avoid this, mlist-filter! should be used with set! to assign the variable to the resulting mutable list:

(set! a (mlist-filter! (lambda (x) (> x 1)) a))
Example 9.4: Append

The list-append procedure takes as input two lists and produces a list consisting of the elements of the first list followed by the elements of the second list. An imperative version of this procedure instead mutates the first list to contain the elements of both lists.

(define (mlist-append! p q)
  (if (null? p) (error "Cannot append to an empty list")
      (if (null? (mcdr p)) (set-mcdr! p q)
          (mlist-append! (mcdr p) q))))

The mlist-append! procedure produces an error when the first input is null --- this is necessary since if the input is null there is no pair to modify.1

Like list-append, the running time of the mlist-append! procedure is in $\Theta(n)$ where $n$ is the number of elements in the first input list. The list-append procedure copies the first input list, so its memory use is in $\Theta(n)$ where $n$ is the number of elements in the first input list. The memory use of mlist-append! is constant: it does not create any new cons cells to append the lists.

Aliasing. Adding mutation makes it possible to define many procedures more efficiently and compactly, but introduces many new potential pitfalls in producing reliable programs. Since our evaluation model now depends on the environment in which an expression is evaluated, it becomes much harder to reason about code by itself.

One challenge introduced by mutation is aliasing. There may be different ways to refer to the same object. This was true before mutation also, but didn't matter since the value of an object never changed. Once object values can change, however, aliasing can lead to surprising behaviors.

For example,

> (define m1 (mlist 1 2 3))
> (define m2 (mlist 4 5 6))
> (mlist-append! m1 m2)
> (set! m1 (mlist-filter! (lambda (el) (= (modulo el 2) 0)) m1))

The value of m2 was defined as {4 5 6}, and no expressions since then explicitly modified m2. But, the value of m2 has still changed! It changed because after evaluating (mlist-append! m1 m2) the m1 object shares cells with m2. Thus, when the mlist-filter! application changes the value of m1, it also changes the value of m2 to {4 6}.

The built-in procedure eq? takes as input any two objects and outputs a Boolean. The result is true if and only if the inputs are the same object. For example, (eq? 3 3) evaluates to true but (eq? (mcons 1 2) (mcons 1 2)) evaluates to false. Even though the input pairs have the same value, they are different objects---mutating one of the pairs does not effect the value of the other pair.

For the earlier mlist-append! example, (eq? m1 m2) evaluates to false since m1 and m2 do not refer to the same object. But, (eq? (mcdr m1) m2) evaluates to true since the second cell of m1 points to the same object as m2. Evaluating (set-mcar! m2 3) changes the value of both m1 and m2 since the modified cell is common to both structures.

Exercise 9.6. Define an imperative-style procedure, mlist-inc! that takes as input a MutableList of Numbers and modifies the list by adding one to the value of each element in the list.

Exercise 9.7. $\left[\star \right]$ Define a procedure mlist-truncate! that takes as input a MutableList and modifies the list by removing the last element in the list. Specify carefully the requirements for the input list to your procedure.

Exercise 9.8. $\left[\star \right]$ Define a procedure mlist-make-circular! that takes as input a MutableList and modifies the list to be a circular list containing all the elements in the original list. For example, (mlist-make-circular! (mlist 3)) should produce the same structure as the circular pair shown in Figure 9.5.

Exercise 9.9. $\left[\star \right]$ Define an imperative-style procedure, mlist-reverse!, that reverses the elements of a list. Is it possible to implement a mlist-reverse! procedure that is asymptotically faster than the list-reverse procedure from Example 5.4?

Exercise 9.10. $\left[\star \right]$ $\left[\star \right]$ Define a procedure mlist-aliases? that takes as input two mutable lists and outputs true if and only if there are any mcons cells shared between the two lists.

  1. The mappend! library procedure in DrRacket takes a different approach: when the first input is null it produces the value of the second list as output in this case. This has unexpected behavior when an expression like (append! a b) is evaluated where the value of a is null since the value of a is not modified.