CODEWITHSUNDEEP
functional-programmingschemeside-effects
Francois
Francois

Reputation: 2066

scheme: element not removed after for-each / delete

Using the mit-scheme interpreter (v10.1.5-1), I was expecting this loop to remove each element of 'ls' except '2':

3 error> (define ls '(1 2 0 5))
;Value: ls
3 error> (for-each (lambda (n) (delq! n ls)) '(0 1 5))
;Unspecified return value
3 error> ls
;Value: (1 2)

Why has '1' not been removed? The result is the same using delete! or changing the order of '(0 1 5).

Upvotes: 1

Views: 51

Answers (2)

ad absurdum
ad absurdum

Reputation: 21318

You should not do destructive operations on literal data in Scheme (emphasis mine): R5RS 3.4 Storage Model

In many systems it is desirable for constants... to reside in read-only-memory.... In such systems literal constants and the strings returned by symbol->string are immutable objects, while all objects created by the other procedures listed in this report are mutable. It is an error to attempt to store a new value into a location that is denoted by an immutable object.

But there is another fundamental problem with the posted code. The MIT Scheme Reference Manual says of the procedures delq!, delv!, and delete!:

Returns a list consisting of the top-level elements of list with all entries equal to element removed.

This does not say that the original list is modified to the desired state; it says the the procedures return a list that has been modified to the desired state. The manual goes on to suggest:

Because the result may not be eq? to list, it is desirable to do something like (set! x (delete! x)).

You may wonder why you would use a destructive operation at all when you still have to use set! anyway. The non-destructive procedures del, delv, and delete return freshly allocated copies of the original list with the appropriate removals. These allocations have a cost which the destructive operations avoid.

The posted code can be amended to avoid using a list literal and to use set!:

1 ]=> (define ls (list 1 2 0 5))

;Value: ls

1 ]=> ls

;Value: (1 2 0 5)

1 ]=> (for-each (lambda (n) (set! ls (delq! n ls))) '(0 1 5))

;Unspecified return value

1 ]=> ls

;Value: (2)

Upvotes: 1

Sylwester
Sylwester

Reputation: 48745

According the, modifying literal data is not allowed. Page 31 in R7RS-small (PDF):

Since it is an error to modify constant objects (those re- turned by literal expressions), implementations may share structure between constants where appropriate. Thus the value of eqv? on constants is sometimes implementation- dependent.

MIT Scheme is a R5RS, but this part has not changed. The only thing that has changed is that while R7RS is supposed to fail, R5RS implementations can do ANYTHING as an accepted solution since the code isn't considered Scheme to begin with. Thus this is also accepted scenario:

(define ls '(1 2 0 5)) (for-each (lambda (n) (delq! n ls)) '(0 1 5)) ls ; ==> "BaNaNa!"

However I know that most Scheme implementations does mutate the data, with consequences. Eg. this is a hignly likely situation:

(define two '(1 2))
(define test '(3 4 1 2))

(set-car! two 9)
two  ; ==> (9 2)
test ; ==> (3 4 9 2)

Because it is literals implementation are allowed to share structure.

delq!, in good MIT Scheme style, returns the result. That way if the first element is the one to be removed it will have the object to be rebound.

(define ls (list 1 2 0 5))
(for-each (lambda (n) (set! ls (delq! n ls))) '(0 1 5))
ls ; ==> (2)

For every element that is not the first to be removed it returns the same value as before, but the one iteration where you remove 1, the first element, there is no way to circumvent the first element because th ebinding points at the pair that needs to go.

Upvotes: 2

Related Questions