recursion - LISP 中的 wheres-waldo 函数

Question

我正在尝试解决 LISP 上的问题，但我被这个问题困扰了很多天。

“编写一个名为 wheres-waldo 的函数，它以一个 lisp 对象(即从 conses 构建的数据结构)作为参数并返回一个 Lisp 表达式，该表达式从该对象中提取符号 waldo，如果它存在的话”

例如，

例如:(wheres-waldo '(emerson ralph waldo)) =

OUTPUT: (FIRST (REST (REST '(EMERSON RALPH WALDO))))

例如:(wheres-waldo '(mentor (ralph waldo emerson) (henry david thoreau))) =

OUTPUT: (FIRST (REST (FIRST (REST 
                 '(MENTOR (RALPH WALDO EMERSON)
                          (HENRY DAVID THOREAU))))))

我已经写了一些递归，例如，

(defun wheres-waldo(lispOBJ)
    (cond ((null lispOBJ) nil)
    (equalp (first lispOBJ) waldo)
    ( t (***stuck here how to write recursion for this***))
)

我从 http://ai.eecs.umich.edu/people/wellman/courses/eecs492/f94/MP1.html 找到了这个问题wheres-waldo.任何帮助，将不胜感激。谢谢。

Answer 1

您需要遍历一个列表，如果一个元素是一个列表，则递归到子列表中，就像您实现深度搜索一样。唯一的区别是，为了产生所需的输出，您需要执行 s-expression 回溯您用于到达那里的函数。

这是一种可能的实现方式。请注意，我使用了更传统的 car 和 cdr 而不是 first 和 rest - 它们是等价的。

(defun whereis (who obj &optional (sexp (list 'quote obj)))
  (cond
   ; we found the object - return the s-expr
   ((eq obj who) sexp)
   ; try car and the cdr
   ((and obj (listp obj)) 
    (or (whereis who (car obj) (list 'car sexp))
        (whereis who (cdr obj) (list 'cdr sexp))))))

然后:

? (whereis 'waldo '(emerson ralph waldo))
(CAR (CDR (CDR '(EMERSON RALPH WALDO))))

? (whereis 'waldo '(mentor (ralph waldo emerson) (henry david thoreau)))
(CAR (CDR (CAR (CDR '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))

? (whereis 'thoreau '(mentor (ralph waldo emerson) (henry david thoreau)))
(CAR (CDR (CDR (CAR (CDR (CDR '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))))

? (whereis 'scotty '(beam me up . scotty))
(CDR (CDR (CDR '(BEAM ME UP . SCOTTY))))

? (whereis 'waldo '(emerson ralph))
NIL

如果您的元素可以出现多次，您还可以构建一个结果列表:

? (whereis 'c '(a b c d c b a))
((CAR (CDR (CDR '(A B C D C B A)))) (CAR (CDR (CDR (CDR (CDR '(A B C D C B A)))))))

使用此代码:

(defun whereis (who obj)
  (let ((res nil)) ; the final result
    (labels
        ; sub-function: walks the whole list recursively
        ((sub (obj sexp)
           ; found it - add to result list
           (when (eq obj who) (setf res (cons sexp res)))
           ; try car and cdr
           (when (and obj (listp obj))
             (sub (cdr obj) (list 'cdr sexp))
             (sub (car obj) (list 'car sexp)))))
      ; call sub-function
      (sub obj (list 'quote obj)))
    res))