list - 从方案中的列表中删除负值

Question

解决方案采用一个列表并从该列表中删除否定元素。否定形式由头部带有 not 的列表表示。例如，如果我有 '(a (not b) c (not f) (not a) b e) 我的输出应该是 '(c (not f) e) 。我编写了函数remove-x，它从列表中删除一个元素；match?，它接受一个值并返回列表中的匹配值。如果我的值是 'a ，它将从列表中返回 '(not a) 。

所以我的问题出在解析函数上。我想查找是否有任何否定元素，如果有，我想删除该元素及其否定。我还需要一种方法来弄清楚如果没有对我的列表进行任何更改，如何返回 false:

   (define (resolution? alist)
     (cond ((null? alist) '())
           ((not (equal? #f (match? (car alist) (cdr alist))))
               (and (remove-x (match? (car alist) (cdr alist)) alist) 
                    (remove-x (car alist) alist)))
           (else (cons (car alist) (resolution? cdr alist)))))

下面这两个函数有效:

   (define (match? value alist)
    (cond ((null? alist) #f)
          ((and (list? (car alist)) 
                (equal? value (car (cdr (car alist)))))
             (car alist))
          ((equal? value (car alist)) (car alist))
          (else (match? value (cdr alist)))))

    (define (remove-x x alist)
     (cond ((null? alist) '())
           ((equal? x (car alist)) (cdr alist))
           (else (cons (car alist) (remove-x x (cdr alist))))))

Answer 1

我认为你的解决方案需要更多的工作，我建议编写更多的帮助程序。核心要解决的问题是如何找到两个列表之间的集合差。这是我的镜头:

; obtain the non-negated variables in the list
(define (vars alist)
  (filter (lambda (e) (not (pair? e))) alist))

; obtain the negated variables in the list
(define (negated-vars alist)
  (map cadr (filter pair? alist)))

; find the set difference between two lists
(define (difference lst1 lst2)
  (cond ((null? lst1) '())
        ((member (car lst1) lst2)
         (difference (cdr lst1) lst2))
        (else
         (cons (car lst1) (difference (cdr lst1) lst2)))))

; build the resolution, traverse alist and for each member
; check if it's in the corresponding white list of variables
(define (build-resolution alist clean-vars clean-negs)
  (cond ((null? alist) alist)
        ((if (pair? (car alist))
             (member (cadar alist) clean-negs)
             (member (car alist) clean-vars))
         (cons (car alist) (build-resolution (cdr alist) clean-vars clean-negs)))
        (else
         (build-resolution (cdr alist) clean-vars clean-negs))))

; pre-calculate lists, call the procedure that does the heavy lifting
(define (resolution? alist)
  (let* ((vs (vars alist))
         (nv (negated-vars alist))
         (clean-vars (difference vs nv))
         (clean-negs (difference nv vs))
         (resp (build-resolution alist clean-vars clean-negs)))
    (if (equal? alist resp) #f resp)))

它的工作原理如广告所示:

(resolution? '(a (not b) c (not f) (not a) b e))
=> '(c (not f) e)

(resolution? '(a (not b) c (not d) (not e) f g))
=> #f