In Unit 2, we used pairs as the foundation of the data structures that store data. We have seen that we are now walking in a realm where it's possible to mutate data. There will also be times when we want to mutate what is stored in our data structures.
(define x (cons 1 2))
x represent the number of times I fall down the stairs and the
x represent the number of times I went to the wrong bathroom. I fell down a flight of stairs just now, so I should update the
2. How can we achieve this without creating a new pair? Scheme allows us to
set! the value of some item using the following function:
(set-car! x 2)
As the name suggests,
set-car! takes in a pair and a value, and changes its
car to point to the specified value of the second argument.
The general form is
(set-car! <pair> <value>)
As you might expect, Scheme also provides us with the function
set-cdr!, which takes in a pair and a value, and changes the pointer of the pair's
cdr to point to the value. Going with the previous example, calling
(set-cdr! x 3)
will change the pair as shown below.
The general syntax is
(set-cdr! <pair> <value>)
Let us see how
set-cdr! work with more complicated lists. We are given the following pairs:
(define x (cons (list a b) (list c d))) (define y (list e f))
The next few calls on
set-cdr! are independent and will be
based on this original configuration. For the next few questions, drawing the
box-pointer is highly recommended.
The effect of calling
(set-car! x y)
to the original configuration will give the resulting box-and-pointer diagram:
The call changes the car-pointer on
x, which initially points to
(list a b), to wherever
y is pointing:
(list e f). What happens to the list with
b? Nothing actually happens to it, but since it has no pointers that reference it, the list is no longer reachable.
(set-car! (car x) 'z)
From the original configuration, we now call
(define z (cons y (cdr x)))
This gives us the following box-and-pointer diagram:
x will print
((a b) c d)
y will print
z will print
((e f) c d)
(set-cdr! (cdr z) nil)
((e f) b)?
set-cdr! modifies existing pairs. Procedures like
list on the other hand, creates a new pair. What about
Does it 'merge' two lists by changing the
cdr pointer of one of them?
Remember the definition of
append we have been using:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))
append forms a new list by
cons-ing elements of
y. This tells us
append returns a new list.
The `last-pair` procedure accepts a list and returns the last pair of the list:
(define (append! x y) (set-cdr! (last-pair x) y) x)
Now, let's take a look at this piece of code:
(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
> (define x (list 'a 'b)) x > (define y (list 'c 'd)) y > (define z (append x y)) z > z (a b c d)
(cdr x)return? Try it out by yourself before putting it into STk.
> (define w (append! x y)) w > w (a b c d)
(cdr x)return now?
The previous exercises raises a big sign that knowing when a pair is shared and created is important. In the code above,
y refer to the same pairs, while
z makes a different pair with the same elements.
(define x (cons 1 2)) (define y x) (define z (cons 1 2))
equal? predicate? It can check if two pairs contain the same
(equal? x y),
(equal? x z),
(equal? y z) all return
#t, because they all hold the same elements at the same place. Is it possible to differentiate that
z point to different structures? Yes! Scheme has the
eq? predicate which takes 2 arguments and checks if the 2 arguments refer to the same pair.
> (eq? x y) #t > (eq? x z) #f > (eq? y z) #f
set-cdr! change the respective
cdr pointers. Procedures like
append create new pairs. Knowing which pairs are shared between different lists is crucial to determining whether mutating one will influence the other. Drawing box-and-pointer diagrams will be very helpful.