3

I am trying to solve problems on LISP and I am stuck with this problem for many days.

"Write a function, called wheres-waldo, that takes a lisp object (i.e., a data structure built from conses) as argument and returns a Lisp expression that extracts the symbol waldo from this object, if it is present"

For example,

E.g: (wheres-waldo '(emerson ralph waldo)) = 

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

E.g: (wheres-waldo '(mentor (ralph waldo emerson) (henry david thoreau))) = 

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

I have written some recursion for example, 

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

I found this question from http://ai.eecs.umich.edu/people/wellman/courses/eecs492/f94/MP1.html wheres-waldo. Any help would be appreciated. Thank you.

4

4 回答 4

3

您的方法的主要问题是，如果第一个元素等于 waldo，您打算如何生成答案？waldo 可能存在许多可能的路径，因此我们需要一种方法来指示迭代中我们所处的路径，如果我们处于死胡同，我们需要回溯。

(defun wheres-waldo (o)
  (labels                                          ; labels is to make local functions 
   ((aux (cur acc)                                 ; define loacl function aux with args cur and acc
      (or                                          ; or stops at the first non NIL value
       (and (eq cur 'waldo) acc)                   ; if (eq cur 'waldo) we return acc 
       (and (consp cur)                            ; (else) if object is a cons 
            (or                                    ; then one of the followin
             (aux (car cur) (list 'first acc))     ; answer might be in the car
             (aux (cdr cur) (list 'rest acc))))))) ; or the cdr of the cons 
    (aux o (list 'quote o))))                      ; call aux with original object and the same object quoted. (list 'quote x) ==> 'x (as data)

如您所见，主要工作是由aux一个对象和一个指示路径和报价数据的累加器完成的。如果你找到waldo了，那么结果就是累加器。

如果 waldo 存在于多个位置，它总是car首先出现，因此不一定是最短的答案，而是它找到的第一个。

我在这里使用and/ or。这些类似于if返回的表达式的值。例如(and (eq cur 'waldo) acc)，将确保我们返回accif curis waldosinceand评估为最后一个真值。如果有一个 NIL 值，它将成为表单的结果。因为如果所有表达式都挂载到or，它将评估为第一个真值（所有不是）或 NIL 。在您的链接的练习 2 中，您将以类似的方式重写一个函数。NILNIL

于 2014-02-22T22:24:21.673 回答
3

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

这是一种可能的实现。请注意，我使用了更传统的carandcdr而不是firstand 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))
于 2014-02-22T22:10:57.117 回答
1

有时处理一个稍微更一般的问题会更容易一些，然后弄清楚如何将其专门用于手头的特定问题。在这种情况下，您将获得某种结构，以及一些可以访问该结构的子结构的访问器。给定一个要查找的元素和要搜索的事物，您可以通过检查该事物是否是该元素进行搜索，如果是，则返回到目前为止的路径（以适当的格式），如果不是，那么如果它是您可以使用访问器分解的结构，尝试每个分解的部分。

(defun find-element (element structure structure-p accessors &key (test 'eql))
  (labels ((fe (thing path)
             "If THING and ELEMENT are the same (under TEST), then 
              return PATH.  Otherwise, if THING is a structure (as 
              checked with STRUCTURE-P),  then iterate through 
              ACCESSORS and recurse on the result of each one
              applied to THING."
             (if (funcall test thing element)
                 ;; return from the top level FIND-ELEMENT
                 ;; call, not just from FE.
                 (return-from find-element path)
                 ;; When THING is a structure, see what 
                 ;; each of the ACCESSORS returns, and 
                 ;; make a recursive call with it.
                 (when (funcall structure-p thing)
                   (dolist (accessor accessors)
                     (fe (funcall accessor thing)
                         (list* accessor path)))))))
    ;; Call the helper function 
    ;; with an initial empty path
    (fe structure '())))

这将返回我们需要的访问器序列，与它们需要应用于结构的相反顺序。例如：

(find-element 'waldo '(ralph waldo emerson) 'consp '(car cdr))
;=> (CAR CDR)

因为(car (cdr '(ralph waldo emerson)))是waldo。相似地

(find-element 'emerson '(ralph (waldo emerson)) 'consp '(first rest))
;=> (FIRST REST FIRST REST)

因为(first (rest (first (rest '(ralph (waldo emerson))))))是emerson。所以我们已经解决了获取访问器函数列表的问题。现在我们需要构建实际的表达式。这实际上是一个相当简单的任务，使用reduce：

(defun build-expression (accessor-path structure)
   (reduce 'list accessor-path
           :initial-value (list 'quote structure)
           :from-end t))

只要我们还提供结构，它就可以按照我们需要的方式工作。例如：

(build-expression '(frog-on bump-on log-on hole-in bottom-of) '(the sea))
;=> (FROG-ON (BUMP-ON (LOG-ON (HOLE-IN (BOTTOM-OF '(THE SEA))))))

(build-expression '(branch-on limb-on tree-in bog-down-in) '(the valley o))
;=> (BRANCH-ON (LIMB-ON (TREE-IN (BOG-DOWN-IN '(THE VALLEY O)))))

现在我们只需要把这些放在一起：

(defun where-is-waldo? (object)
  (build-expression
   (find-element 'waldo object 'consp '(first rest))
   object))

这就像我们想要的那样工作：

(where-is-waldo? '(ralph waldo emerson))
;=> (FIRST (REST '(RALPH WALDO EMERSON)))

(where-is-waldo? '(mentor (ralph waldo emerson) (henry david thoreau)))
;=> (FIRST (REST (FIRST (REST '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))
于 2014-02-23T00:09:59.217 回答
1

那不是你被困的地方。你被困在制定策略，而不是编写代码。

您将不得不进行树搜索（您称之为“lisp 对象”的东西实际上只是一个 cons 树——“lisp 对象”是一个误导性术语，因为在 Lisp 中，很多东西都是对象，而不仅仅是 conses）。决定是进行广度优先还是深度优先搜索，如何累积访问器路径，以及如何在调用树上传递匹配或不匹配。

于 2014-02-22T19:37:49.190 回答