2

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

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

我知道我可以编写一个函数（可能是通过过滤器）在几行中完成它，但我想知道是否存在更好/标准的方法来做到这一点。

例如，给出列表

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

移除元素时

(1 2)

我希望结果是

((3 4) (1 2))

而原始列表仍然存在

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

提前致谢！

4

2 回答 2

2

在 Scheme 中，标准解决方案是创建一个新列表，但没有元素。在文档中，我们看到该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))
于 2015-03-26T15:00:29.170 回答
1

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

第一个是非尾递归：

(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以递归方式实现 tail 时，它必须反转其结果，但我们已经有了一个append-reverse，所以为什么不 atake-reverse以相反的顺序返回其结果，所以(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))))))

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

于 2015-04-03T05:13:11.333 回答