Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.

This lab will provide practice with side-effects on structures. We'll use the built-in structures of cons-cells, which combine to form lists.

Toy examples on lists

Exercises 
(define mylist (list 1 3 5 7))
(define yourlist (rest mylist))

(set-first! yourlist 10)
; What is mylist now?
; What is yourlist now?
; Can you draw each as boxes and arrows?

(set-rest! mylist (list 2 4))
; What is mylist now?
; What is yourlist now?
; Can you draw each as boxes and arrows?

(set-rest! (rest mylist) mylist)
; What is mylist now?
; What is yourlist now?
; Can you draw each as boxes and arrows?
Some of the previous output should have used the shared syntax. If you didn't, in DrScheme, go to "Language / Choose Language", click on "Show Details", and select "Show sharing in values". The shared syntax is similar to local, but it only ever appears in printed output. 
(define a (list 1 2))
(define b (list 1 2))
(define c b)

(eq?    a b)  ⇒  ?
(equal? a b)  ⇒  ?
(eq?    b c)  ⇒  ?
(equal? b c)  ⇒  ?

(set-first! b 3)

(eq?    a b)  ⇒  ?
(equal? a b)  ⇒  ?
(eq?    b c)  ⇒  ?
(equal? b c)  ⇒  ?

(set! c a)

(eq?    a b)  ⇒  ?
(equal? a b)  ⇒  ?
(eq?    b c)  ⇒  ?
(equal? b c)  ⇒  ?

Bigger examples on lists

Insertion exercises
We'll define functions to destructively insert a number into a sorted list so that the result is sorted. For simplicity, we'll allow the insertion of numbers already in the list. Before writing any code, let's think about the problem some.
  1. First, we need to understand what our function should return. Why is it interesting to distinguish the case when the new number goes at the front?
  2. Consider a version of the the insertion function that assumes the new number does not belong at the front. What does that imply about the input list? What is the contract for this function?
  3. Develop this function. (Still assume the new number doesn't belong at the front.)
  4. Let's examine your just-written code. To insert 4 correctly into (cons 2 (cons 6 …)), you had to be able to look at the 6 while still having access to the first cons-cell. Did you have code like (first (rest alist))? We've always considered looking ahead into a nested structure to be bad style, so how can we avoid that?
  5. Now, we still need to address the possibility that the new number goes at the beginning of the list. We will write another, more general inserting routine. What should its contract be?
  6. Develop this function. It should use your previous one.
Sample solution
Deletion exercises
Destructive deletion from a sorted list is very similar. Develop the function(s), keeping in mind the same ideas.
Sample solution

Lists vs. vectors

Exercise
Do exercise 43.1.6.

If you have time… Lists as objects

With destructive insertion and deletion of sorted lists, changing the first element and dealing with empty lists are both problematic. In those cases, we have to have a separate set! to change a variable to the new first element. (See their sample solutions above for examples.)

One solution to this problem is to package the list, together with its insertion and deletion functions (and any other desired functions) into an "object".

Lists as "objects" exercises
Define a list-object and its associated make-list "factory" function that has the following behavior. 
(define l (make-list))    ; Makes an empty list-object.
((l 'insert) 3)           ; Inserts the number in sorted order.
((l 'insert) 2)
((l 'insert) 8)
(l 'min)                  ; Returns the minimum elt.
   ⇒   2
((l 'delete) 2)           ; Deletes the number.
(l 'empty?)               ; Returns whether the list is empty.
   ⇒   false
This will incorporate your previous code for insertion and deletion. Returning the equivalent Scheme-list should be easy, since you should have that representation already stored within the list-object.
If you want, add more "messages" that it understands.
Sample solution

What's an alternate solution to the problem described above? We could define a "ref-list" as a structure of one component: a list. Your insertion/deletion algorithm would be passed a ref-list, would change the list, and also change the component of the ref-list. This general technique is called indirection. Draw this as a box-and-arrows diagram, and you'll see that we've added one more arrow.

If you have time… Circular lists

Above in the toy examples, we saw an example of a circular list, one of the many variants of lists. Circular lists are sometimes useful. For example, you could have a circular list of your friends. Whenever you have a piece of candy to share, you give it to the next friend. The notion of "next" just moves forever around the circle. This is one way to evenly and fairly distribute the candy among your friends. Change "friend" to "process", and "candy" to "processor time", and you have a simple implementation of an operating system's process scheduler.

Non-empty circular lists have no empty at the end, since there is no end! In general, circular lists can be empty, but that has to be treated as an entirely separate special case. Frequently, circular lists are used where they can be assumed to be non-empty.

As an extra wrinkle, with circular lists you might choose not to care where the "front" of the list is. For example, we could define an equality relation (different from equal? and eq?) that considers the following to be "equal": 

      (define l1 (cons 1 (cons 2 empty)))
      (set-rest! (rest l1) l1)
      ; l1 = [1 2 1 2 1 2 ...]

      (define l2 (cons 2 (cons 1 empty)))
      (set-rest! (rest l2) l2)
      ; l2 = [2 1 2 1 2 1 ...]
Circular list exercises
  1. Since (non-empty) circular lists never end, functions on them can't use empty? to test when to stop. Instead, if we are writing functions to look at each element, when do we want to stop? What extra piece of information do we need to keep track of for this?
  2. Write a template for (non-empty) circular lists that uses this previous idea.
  3. Like regular lists, circular lists can optionally keep their elements in sorted order. Define insertion on a non-empty circular list of number. Assume that the "front" of the list is the least element, and that the new number doesn't belong at the "front". Thus, this should be very similar to the very first insertion algorithm of the lab.
  4. Develop a circular list object, analogous to those described in the previous set of exercises.