从列表和子列表中删除成员的方案功能

Question

首先，如果任何人都可以在已经回答的地方找到问题，请告诉我。我能找到的所有功能都是删除重复项。

无论如何，我正在尝试编写一个方案函数(delete V L)，它将一个值和一个列表作为参数，并从列表及其所有子列表中删除该值。例如，给出下面的输入：

> (deep-delete 3 '(1 2 3 (4 3) 5 (6 (3 7)) 8)) 

它会产生：

(1 2 (4) 5 (6 (7)) 8) 

到目前为止，这是我自己写的，但我知道，if语句（即进行检查，看如果该元素是一个子列表，这意味着它也必须被操作）必须被错误地放置。此外，我无法将自己的大脑包围在我应该使用的位置cons以及我不应该在的位置，因为我仍然对追踪递归的返回值感到困惑。有人可以看看并解释我做错了什么吗？

(define (delete V L) 
    (if (list? (car L)) (cons (delete V (car L) (cdr L)))  
    (cond 
     ((null? L) L) 
     ((equal? V (car L)) (delete V (cdr L))) 
     (else (cons (car L) (delete V (cdr L)))))))) 

Answer 1

我对你的代码的一些评论：您使用(car L)任何检查L是空

• 首先，在你if声明。
• 此外，在您的代码的第2行中，您执行：(delete V (car L) (cdr L)), 但cons需要两个参数，而不是三个。并且您忘记递归调用cdr上的delete。 你想： (cons (delete V (car L)) (delete V (cdr L)))
• 为什么不使用一个cond？由于有几种情况，使用cond会使算法的递归结构更加明显，并且容易发现错误。

见下文。

(define (del V L) 
    (cond ((null? L) L) 
     ((list? (car L)) 
     (cons (del V (car L)) (del V (cdr L)))) 
     ((equal? V (car L)) (del V (cdr L))) 
     (else (cons (car L) (del V (cdr L)))))) 

这将递归从L删除V。

(del 3 '(1 2 3 (4 3) 5 (6 (3 7)) 8)) 
==> (1 2 (4) 5 (6 (7)) 8) 

Answer 2

这很容易实现与折叠;下面是使用foldr在拍一个例子：

(define (deep-delete elt lst (test equal?)) 
    (foldr (lambda (e r) 
      (if (list? e) 
       (cons (deep-delete elt e test) r) 
       (if (test elt e) r (cons e r)))) 
     null 
     lst)) 

测试

> (deep-delete 3 '(1 2 3 (4 3) 5 (6 (3 7)) 8)) 
'(1 2 (4) 5 (6 (7)) 8) 

Answer 3

这从一个树（包括原子）删除子树：

(define (remove-element needle haystack) 
    (let rec ((haystack haystack)) 
    (cond 
     ((equal? needle haystack) '()) 
     ((not (pair? haystack)) haystack) 
     ((equal? needle (car haystack)) (rec (cdr haystack))) 
     ((equal? needle (cdr haystack)) (cons (rec (car haystack)) '())) 
     (else (cons (rec (car haystack)) 
        (rec (cdr haystack))))))) 

(remove-element 'atom 'atom)    ; =>()  
(remove-element '(1 2 3) '((1 2 3) 1 2 3)) ; =>() 
(remove-element '(1 2 3) '((1 2 3) 4 5 6)) ; => (4 5 6) 
(remove-element '(1 2 3) '(3 2 1 2 3))  ; ==> (3 2) 
(remove-element '3 '((1 2 3) 1 2 3))  ; ==> ((1 2) 1 2) 
(remove-element '(1 2 3) '(1 2 3 4))  ; ==> (1 2 3 4)