Why doesn't the set! function modify the original list in Scheme (r5rs)?

Question

I am trying to write a function which takes a list (x) and a number (y) and deletes every occurance of that number in the list. Ex. (deepdeleting '(0 0 1 2 0 3 0) 0) ===> '(1 2 3) Here's what I have so far:

 (define (deepdeleting x y)
      (if (pair? x)
          (if (eqv? (car x) y)
              (begin
                (set! x (cdr x))
                (deepdeleting x y)
               )
               (deepdeleting (cdr x) y) ; else
           )
          x ; else
       )
    )

The code works, but my problem is I want it to modify the original list, not just return a new list. Right now this is what happens:

> (define list '(0 0 1 2 0 3 0))
> (deepdeleting list 0)
(1 2 3)
> list
(0 0 1 2 0 3 0) ; <<< I want this to be (1 2 3)

This seems strange to me since both the set-car! and set-cdr! functions seem to change the input list, whereas set! does not...

Any insight would be much appreciated!

Answer 1

When you use set! you are redefining the innermost binding:

(define test 10)

(set! test 11) ; changes global test to 11

(define (change-test value)
  (set! test value))

(change-test 12) ; changes global test to 12

(define (change-test! value new-value)
  (display value)
  (set! value new-value) ; changes the local binding value
  (display value))

(change-test! test 13) ; changes nothing outside of change-test, prints 12 then 13

Variable bindings are totally different than list structure mutation. Here a binding is used to point to a pair that is altered:

(define lst '(1 2 3))
(define lst2 (cdr lst)) ; lst2 shares structure with lst

(set-cdr! lst2 '(8 7 6 5))
lst2 ; ==> (2 8 7 6 5)
lst  ; ==> (1 2 8 7 6 5) the original binding share structure thus is changed too

(set-cdr! lst lst)  ; makes a circular never ending list (1 1 1 1 ...)
(eq? lst (cdr lst)) ;==> #t

(set-car! lst 2)    ; changes lst to be never ending list (2 2 2 2 ...)

So you can mutate pairs with set-cdr! and set-car! and a binding to the original list will point to the first pair. Thus you need the result to start with the same pair as the first. With that you can make your mutating procedure this way:

#!r6rs 
(import (rnrs) (rnrs mutable-pairs))

(define (remove! lst e)
  (if (pair? lst)
    (let loop ((prev lst)(cur (cdr lst)))
      (if (pair? cur)
          (if (eqv? (car cur) e)
              (begin
                (set-cdr! prev (cdr cur))
                (loop prev (cdr cur)))
              (loop cur (cdr cur)))
          (if (eqv? (car lst) e)
            (if (pair? (cdr lst))
                (begin
                  (set-car! lst (cadr lst))
                  (set-cdr! lst (cddr lst)))
                (error 'first-pair-error "Not possible to remove the first pair"))
            #f)))
    #f))
(define test '(0 0 1 2 0 3 0))
(define test2 (cdr test))
test2 ;==> (0 1 2 0 3 0)
(remove! test 0)
test  ; ==> (1 2 3)
test2 ; ==> (0 1 2 0 3 0)
(remove! '(0) 0)
; ==> first-pair-error: Not possible to remove the first pair

(remove! '(1 2 3) 2) ; this works too but you have no way of checking

While lst is bound to the list during removal and the same list has one element less there was not binding to it outside of the remove! procedure so the result is forever lost.

EDIT For R5RS remove the first two lines and add error:

;; won't halt the program but displays the error message
(define (error sym str)
  (display str)
  (newline))