list - 暂停和恢复对两个列表的迭代？

Question

我是 Common Lisp 的新手，并且一直致力于将简单的模式匹配器作为第一个项目。我在使用星号 (*) 运算符表示列表中任何元素的 0 个或多个时遇到问题。所以模式 (x * z) 和匹配器 (x y y y z) 将返回 true，但模式 (x * z) 和匹配器 (x y) 将返回 false。

我的第一个想法:

(loop for x in pattern-list
  (eq x '*)
  ;if x is *, pause iterating through this list
  (loop for y in matcher-list
        ;somehow iterate one more value in the pattern list
        (eq x y) ;does the value just after the * in the pattern list equal the value in y?
        ;if they aren't the same symbol, just iterate matcher until they match, then resume incrementing though the pattern list
))

抱歉，如果我的语法和括号有一点偏差。

这是我正在处理的较大模式匹配器的一小部分。到目前为止，这是我所拥有的(在这种情况下，list1 是模式列表，list2 是匹配器列表):

此代码的大部分源自此 SO 帖子:

Setting up a equal function in common lisp using only "eq"

(defun comp-q (list1 list2) ;defun
  (if (and (not (null list1)) ;if list1 is not null AND
       (not (null list2))) ;if list2 is not null
  (let ((a (car list1)) (b (car list2))) ;a is the car (front) of list1 and b is the car of list 2
    (cond ((and (listp a) (listp b)) ;cond, evaluate the first thing in the list - are a and b lists?
           (and (comp-q a b) ;recursive call on a and b
                (comp-q (cdr list1) (cdr list2)))) ;recursive call on the cdr (tail) of a and b
          (t ;like an else for cond
           (and (or (eq a b) (eq a '?)) ;are a and b equal OR is a a '?'
                (comp-q (cdr list1) (cdr list2)))))) ;recursive call on the cdr of a and b
  (= (length list1) (length list2)))) ;are the lists equal?  only triggered if the null test fails (are they both not null)

使用 loop 宏是我最好的选择吗？是否可以“暂停”或跟踪列表的迭代(我知道这是数组式的)？还是我应该尝试通过调用正在 comp-q defun 中实现的每个列表的 car 和 cdr 来继续递归工作？

谢谢。

Answer 1

由于还没有人给出任何答案，并且建议使用递归方法，因此我在 Racket 中提出了一个示例来帮助您入门。转换为 Common Lisp 应该很简单。

(define (match pattern matcher)

  ; is the symbol a wildcard (i.e. does it end with an asterisk?
  ;   yes -> return true + the symbol without the asterisk
  ;   no  -> return false + the symbol itself
  (define (is-wildcard sym)
    (let ((str (symbol->string sym)))
      (if (string=? (substring str (sub1 (string-length str))) "*")
          (values #t (string->symbol (substring str 0 (sub1 (string-length str)))))
          (values #f sym))))

  ; we know wi is a wildcard; let's loop over matcher until done
  (define (match-wildcard wi pattern matcher)
    (if (empty? matcher)
        (list (cdr pattern) matcher)
        (if (eq? wi (car matcher))
            (match-wildcard wi pattern (cdr matcher))
            (list (cdr pattern) matcher))))

  ; main loop
  (if (or (empty? pattern) (empty? matcher))
      (and (empty? pattern )(empty? matcher))
      (let ((pa (car pattern)) (ma (car matcher)))
        (if (eq? pa ma)
            (match (cdr pattern) (cdr matcher))
            (let-values (((wildcard wi) (is-wildcard pa)))
              (if wildcard
                  (apply match (match-wildcard wi pattern matcher))
                  #f))))))

例子:

(match '(x y* z) '(x y y y z))
=> #t

(match '(x z* y) '(x y))
=> #t

(match '(x y* z) '(x y))
=> #f

(match '(x y*) '(x y))
=> #t

喂!