Scheme Guile：仅从列表中删除第一次出现（非破坏性）

Question

我需要以非破坏性的方式从列表中删除第一次出现的元素。

根据 Guile Reference Manual，有一组函数可以以破坏性方式执行此操作（delq1！、delv1！、delete1！）。另一方面，非破坏性版本会删除所有出现的元素。

我知道我可以写一个函数（可能是通过过滤器）在几行中完成，但我想知道是否存在 better/standard 方法来完成它。

举个例子，给出列表

((1 2) (3 4) (1 2))

删除元素时

(1 2)

我希望结果是

((3 4) (1 2))

而原始列表仍然存在

((1 2) (3 4) (1 2)).

提前致谢！

Answer 1

在 Scheme 中，标准解决方案是创建一个新列表，但不包含元素。在 documentation 中，我们看到 delete 过程消除了元素的所有出现 - 因此我们必须推出自己的解决方案，但这很简单：

(define (delete-1st x lst)
  (cond ((null? lst) '())
        ((equal? (car lst) x) (cdr lst))
        (else (cons (car lst)
                    (delete-1st x (cdr lst))))))

例如：

(delete-1st '(1 2) '((1 2) (3 4) (1 2)))
=> '((3 4) (1 2))

Answer 2

这里有五个版本的delete1和一个版本的delete1!。每个从返回的列表中删除发现等于给定元素的第一个元素。后者更适合时间和 space。不使用破坏性函数，除非在最后一部分考虑了它们的正确使用。

首先是非尾递归：

(define (delete1a v l) 
  (let loop ((l l))
    (if (null? l) '()
        (if (equal? v (car l)) 
            (cdr l)
            (cons (car l) (loop (cdr l)))))))

然后第二个和第三个是尾递归但是效率低下他们复制了比需要更多的东西。例如，如果找不到该项目，则复制整个列表。

 (define (delete1b v l)
   (let loop ((l l) (a '()))
     (if (null? l) (reverse a)
         (if (equal? v (car l)) 
             (append (reverse a) (cdr l))
             (loop (cdr l) (cons (car l) a))))))

第三个包含 (append (reverse l) m) 的融合并在到达列表末尾时删除无用的 (reverse a) 但它仍然在 a 中累积列表的副本需要 (reverse a):

 (define (append-reverse l m) 
   (if (null? l)
       m
       (append-reverse (cdr l) (cons (car l) m))))

 (define (delete1c v ls)
   (let loop ((l ls) (a '()))
     (if (null? l) ls
         (if (equal? v (car l)) 
             (append-reverse a (cdr l))
             (loop (cdr l) (cons (car l) a))))))

在第四个版本中，累加器被计数器取代：

(define (delete1d v ls)
   (let loop ((l ls) (a 0))
     (if (null? l) ls
         (if (equal? v (car l)) 
             (append (take ls a) (cdr l))
             (loop (cdr l) (+ a 1))))))

当 take 以尾递归方式实现时，它必须颠倒它的结果，但是我们已经有了一个 append-reverse 那么为什么不 take-reverse 那个 returns 它的结果倒序所以 (append (take a b) c) 被 (append (reverse (take-reverse a b)) c) 替换，然后被 (append-reverse (take-reverse a b) c):

替换

(define (append-reverse l m) 
  (if (null? l)
      m
      (append-reverse (cdr l) (cons (car l) m))))

(define (take-reverse l n)
  (let loop ((l l) (n n) (a '()))
    (if (= n 0) a
        (if (null? l) a
            (loop (cdr l) (- n 1) (cons (car l) a))))))

(define (delete1e v ls)
  (let loop ((l ls) (a 0))
    (if (null? l) ls
        (if (equal? v (car l)) 
            (append-reverse (take-reverse ls a) (cdr l))
            (loop (cdr l) (+ a 1))))))

这样做的结果是，如果没有找到值，则只遍历列表一次，不进行复制，如果找到值，则仅遍历列表的前缀，然后再遍历和复制元素两次.一次在 take-reverse 然后一次在 append-reverse.

如果允许破坏性函数，则可以使用 append-reverse! 而不是 append-reverse 将列表前缀的复制安全地减少到一次，因为 (append-reverse (take-reverse ls a) (cdr l)) 是 (take-reverse ls a) 的结果是被(append-reverse r (cdr l))线性使用的副本。有类型系统可以证明这样是安全的：

(define (append-reverse! l m) 
  (if (null? l)
      m
      (let ((next (cdr l)))
        (begin (set-cdr! l m)
               (append-reverse next l)))))

但可以更进一步定义 delete1!:

(define (delete1! v l)
  (let loop ((left '()) (right l))
    (if (null? right) l
        (if (equal? (car right) v) 
            (if (null? left) (cdr right)
                (begin (set-cdr! left (cdr right)) 
                       l))
            (loop right (cdr right))))))

这会遍历列表一次并且不进行复制。

Scheme Guile：仅从列表中删除第一次出现（非破坏性）

Scheme Guile: remove only first occurrence from a list (non destructive)

list

scheme

guile