方案:元素在 for-each / delete 后未删除

scheme: element not removed after for-each / delete

使用 mit-scheme 解释器 (v10.1.5-1), 我期待这个循环删除 'ls' 的每个元素,除了 '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)

为什么“1”没有被删除? 使用 delete 结果是一样的!或更改 '(0 1 5).

的顺序

根据,不允许修改文字数据。 R7RS-small 中的第 31 页 (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是R5RS,但这部分没变。唯一发生变化的是,虽然 R7RS 应该会失败,但 R5RS 实现可以作为公认的解决方案做任何事情,因为代码不被认为是 Scheme。因此这也是可以接受的场景:

(定义 ls '(1 2 0 5)) (for-each (lambda (n) (delq! n ls)) '(0 1 5)) ls ; ==>“BaNaNa!”

但是我知道大多数 Scheme 实现确实会改变数据,并产生后果。例如。这是极有可能的情况:

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

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

因为它是文字实现,所以允许共享结构。

delq!,以良好的 MIT Scheme 风格,returns 结果。这样,如果第一个元素是要删除的元素,它将具有要反弹的对象。

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

对于每个不是第一个被删除的元素,它 returns 与以前相同的值,但是您删除第一个元素 1 的一次迭代,没有办法绕过第一个元素,因为绑定指向需要去的对。

你不应该对 Scheme 中的文字数据进行破坏性操作(强调我的):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.

但是发布的代码还有另一个根本问题。 MIT Scheme Reference Manual 说到程序 delq!delv!delete!:

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

不是说原来的列表被修改成想要的状态;它表示程序 return 已修改为所需状态的列表。手册继续建议:

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

您可能想知道为什么您仍然必须使用 set! 而完全使用破坏性操作。非破坏性过程 deldelvdelete return 新分配了原始列表的副本,并进行了适当的删除。这些分配具有破坏性操作避免的成本。

可以修改发布的代码以避免使用列表文字并使用 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)