list - 使用通配符比较列表

Question

我正在尝试编写一个比较两个家庭作业列表的函数。当函数运行时，它应该是这样的 ;(cmp '(cat ?x mat ?x) '(cat bat mat bat)) => t ;(cmp '(cat ?x mat ?x) '(cat bat mat坐））=> 无。这意味着在第一个列表中等于 ?x 和第二个 ?x 如果两者都指向相同的值，则返回 true。当我现在运行程序时，出现“将参数解析为特殊形式时出错：如果元素数量无效”，如果您能给我一些反馈，这是我的代码。谢谢。

;cmp algorithm
;1 if the both lists are empty return true
;2 if only one of the lists is empty return fasle
;3 compare first of the list1 and the first of list2
;if equal go on to the rest of the list with recursive call else return false   

(defun cmp (list1 list2)
(setq y '())
(setq z '())
(defparameter *counter* 0)
  (cond 
   ((and (null list1) (null list2))
    t 
    )
   ((or (null list1) (null list2))
    nil
    )
    ((or (eq (first list1) (first list2)) 
         (eq (first list1) '?x)  )
     (cmp (rest list1) (rest list2) )

        ;if (first list is equal to '?x)
        ;set the counter to 1
        ;give the value of (first(rest list2)) to y 
        ;if (first list is equal to '?x) again
        ;set the counter to 2
        ;give the value of (first (rest list2)) to z
        ;i need to compare y and z if eq return true

     (if (eq (first list1) '?x) 
        (princ (first list1 ))
        (princ (first(rest list2)))

        (1+ *counter*)
        (set y (first(rest list2)))

        (if (= *counter* 2)
        (set z (first (rest list2)))    
            )       
        )

        (if (= y z) t)      
     )
   (t
    nil)
   )
  )





;(cmp ‘(cat ?x mat ?x) ‘(cat bat mat bat))  =>  t 
  ;(cmp ‘(cat ?x mat ?x) ‘(cat bat mat sat))  =>  nil

Answer 1

虽然阅读书籍或文档肯定会有所帮助，但有时查看示例代码，尤其是在您已经了解问题之后也会有所帮助。所以这是一个朴实无华的直接解决方案：

(defun compare-using-wildcards (pattern matched)
  (loop for p in pattern
     for m in matched
     with keys = (make-hash-table)
     do (unless (eql p m)               ; Doesn't matter
                                        ; if it starts with ?
                                        ; we still don't consider
                                        ; it a wildcart symbol, if
                                        ; it matches the symbol in
                                        ; the other list.
          (if (and (symbolp p)
                   (char= (aref (symbol-name p) 0) #\?))
              (multiple-value-bind (registered exists)
                  (gethash p keys)
                (if exists
                    (unless (eql registered m)
                      (return))
                    (setf (gethash p keys) m)))
              (return)))
     finally (return t)))

(compare-using-wildcards '(cat ?x mat ?x) '(cat bat mat bat)) ; T
(compare-using-wildcards '(cat ?x mat ?x) '(cat bat mat sat)) ; NIL
(compare-using-wildcards '(cat ?x mat ?y) '(cat bat mat sat)) ; T
(compare-using-wildcards '(cat ?x max ?y) '(cat bat mat sat)) ; NIL

但是有很多很多方法可以做到这一点！例如，如果已知列表很短，则可以通过destructuring-bind. 或者，您可以编写一个“zip”函数（一个高阶函数，它将多个列表中的单元格提供给其他函数，直到它返回非零结果）等等。

---

还有一个有些人为的例子。好吧，它看起来应该可以工作，除非我错过了一些极端情况。它将使用通配符将多个列表与列表进行比较：

(every (let ((keys (make-hash-table)))
       #'(lambda (&rest elements)
           (let ((wildcard (car elements)))
             (if (and (symbolp wildcard)
                      (char= (aref (symbol-name wildcard) 0) #\?))
                 (let ((replacement (gethash wildcard keys))
                       (i -1))
                   (if replacement
                       (every #'(lambda (x)
                                  (eql x (aref replacement (incf i))))
                              (cdr elements))
                       (setf (gethash wildcard keys)
                             (coerce (cdr elements) 'vector))))
                 (every #'(lambda (x) (eql x wildcard)) elements)))))
     '(cat ?x mat ?x)
     '(cat bat mat bat)
     '(cat bar mat bar)
     '(cat bank mat bank)
     '(cat bass mat boss))

Answer 2

您快到了。您缺少如何在第一个字符为的任何符号上进行一般匹配?以及如何将匹配传递给递归调用。

您需要在通话之间的某处保存匹配项。一种可能的方法是将它们传递到可选的匹配关联列表中：

(defun cmp (list1 list2 &optional matches)
  (cond ((and (null list1) (null list2))
         t)
        ((or (null list1) (null list2))
         nil)
        ((and (symbolp (first list1))
              (plusp (length (symbol-name (first list1))))
              (eql (char (symbol-name (first list1)) 0) #\?))
         (let ((assoc (assoc (first list1) matches)))
           (cond ((null assoc)
                  (cmp (rest list1) (rest list2)
                       (list* (cons (first list1) (first list2))
                              matches)))
                 ((eql (cdr assoc) (first list2))
                  (cmp (rest list1) (rest list2) matches)))))
        ((eql (first list1) (first list2))
         (cmp (rest list1) (rest list2) matches))))

一种与使用动态变量的方法非常相似的方法：

(defvar *matches* '())

(defun cmp (list1 list2)
  (cond ((and (null list1) (null list2))
         t)
        ((or (null list1) (null list2))
         nil)
        ((and (symbolp (first list1))
              (plusp (length (symbol-name (first list1))))
              (eql (char (symbol-name (first list1)) 0) #\?))
         (let ((assoc (assoc (first list1) matches)))
           (cond ((null assoc)
                  (let ((*matches* (list* (cons (first list1) (first list2))
                                          *matches*)))
                    (cmp (rest list1) (rest list2))))
                 ((eql (cdr assoc) (first list2))
                  (cmp (rest list1) (rest list2))))))
        ((eql (first list1) (first list2))
         (cmp (rest list1) (rest list2)))))

两者都可以这样调用：

> (cmp '(?x b ?x d ?y f ?y h)
       '(a  b c  d  e f g  h))
nil
> (cmp '(?x b ?x d ?y f ?y h)
       '(a  b a  d  e f e  h))
t

但是，如果您已经从匹配的关联列表开始，则第一个匹配项的调用方式如下：

> (cmp '(?x ?y)
       '(a  b)
       '((?x . a)))
t

而第二个是这样使用的：

> (let ((*matches* '((?x . a))))
    (cmp '(?x ?y)
         '(a  b)))
t

---

练习：cmp总是匹配'?任何东西（一个名字只是问号的符号）。

如果您希望某个元素存在但您想忽略它，这可能很有用。

---

练习：cmp变得更有用并返回找到的关联列表，而不是t：

> (cmp '(?x ?y)
       '(a  b))
((?x . a)
 (?y . b))

;;; Assuming option one
> (cmp '(?x ?y)
       '(a  b)
       '((?x . a)
         (?z . c)))
((?x . a)
 (?y . b))
> (cmp '(?x ?y)
       '(c  b)
       '((?x . a)
         (?z . c)))
nil

这个想法是只返回找到的关联，而不是未使用的关联。因此，即使第二个测试返回 non- nil，?z也不会出现在结果中。