recursion - LISP 中的 Wheres-waldo 函数

我正在尝试解决 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 找到了这个问题。
任何帮助，将不胜感激。谢谢你。

最佳答案

你需要遍历一个列表，如果一个元素是一个列表，那么递归到子列表中，就像你实现深度搜索一样。唯一的区别是，为了产生所需的输出，您需要继续使用 s 表达式来回溯您用来到达那里的函数。

这是一种可能的实现方式。请注意，我使用了更传统的 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))

关于recursion - LISP 中的 Wheres-waldo 函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21958502/

Waldo

recursion - LISP 中的 Wheres-waldo 函数