删除！R5RS函数

Question

我正在尝试编写一个delete!函数，它会改变一个列表并从它中移除一个指定的值。这是我到目前为止掌握的密码。

(define (extend! l . xs)
  (if (null? (cdr l))
      (set-cdr! l xs)
      (apply extend! (cdr l) xs)))

(define (delete! lis y)
  (define returnLis '())
  (for-each (lambda(x) (if(not(eq? x y))
                          (extend! returnLis x))) lis)
  returnLis)

我遇到的问题是，我试图添加到一个空的列表，这是不能做的计划。

预期结果：

(删去'(1 2 3 4 5) 3) => (1 2 4 5)

Answer 1

您的extend函数实际上会在一个新的对中生成每个元素的副本，但是由于初始值是'()，所以不能是set-cdr!。突变的全部意义在于，旧变量将继续指向已更改的数据，而复制则不能做到这一点。

你得看看那对。你想要删除3

[1,-]->[2,-]->[3,-]->[4,-]->[5,-]->()

因此，当您找到3时，您需要更改包含2的对的cdr，并将包含3s cdr的对按如下方式排列：

[1,-]->[2,-]->[4,-]->[5,-]->()

就像这样：

(define (delete lst e)
  (if (and (not (null? lst)) (not (null? (cdr lst))))
      (if (equal? (cadr lst) e)
          (set-cdr! lst (cddr lst))
          (delete (cdr lst) e))
      'undefined))

(define test (list 1 2 3 4 5)) 
(delete lst 3)
lst ; ==> (1 2 4 5)

注意，我使用的是list，因为这里不能使用引用的文字，因为不允许更改常量数据(如'(1 2 3 4 5) )。结果将是未定义的，否则会发出错误信号。

如果问题中的元素是第一个元素，它将无法工作。这是因为变量指向第一对，这只会成对地改变指针，而不是绑定。一个可以首先切换两个元素，然后删除第二个元素，但是如果您有一个元素列表，那么您仍然被卡住了。可变队列的方案实现通常有一个头，由一个不被认为是删除第一个元素的列表中的虚拟元素组成。

Answer 2

你所需要的只是一种前哨技术

(define (delete! lis y)
  (define returnLis (list 1))
  (for-each (lambda(x) (if(not(eq? x y))
                          (extend! returnLis x))) lis)
  (cdr returnLis))

不是所有的..。因为这是一种二次算法。它从顶部重新搜索returnLis，同时使用extend!添加每个新元素。最好只维护最后一个cell并更新它。

(define (delete! lis y)
  (define returnLis (list 1))
  (define last-cell returnLis)
  (for-each (lambda(x) (cond ((not(eq? x y))
                          ; (extend! last-cell x)
                          (set-cdr! last-cell (list x))
                          (set! last-cell (cdr last-cell)))))
            lis)
  (cdr returnLis))

但是，作为@Sylwester points out，使用这种方法，您不应该在名称中使用感叹号，因为这将返回一个新建的列表，而不是修改参数的结构。