只使用基本的lisp在列表中递归查找并返回模式

Question

我需要编写的函数有两个参数：模式(p)和列表(L)。我想找到列表中包含模式以及模式之后的所有内容的部分。如果该模式不在列表中，则返回nil。

示例：

输入：(find_pattern'(h e l p)'(i n e e d h e l p p l e a s e)

输出：'(h e l p p l e a s e)

我只能使用基本的lisp函数(cond，car，cdr，cons，null，eq，/=)。它需要是递归的，不能使用诸如setq之类的东西。

我的策略：

我推断这些案例是：

p=nil，L=nil：如果模式在列表的末尾，就会发生这种情况，因此，返回nil

p=nil，L=(none-nil值)：如果模式位于列表的中间，则会发生这种情况，因此返回L

p=(非零值)，L=零：在返回零之前未找到模式

p=(非零值)，L=(非负值)：如果p和L的car相同，则递归调用p和L.的cdr。如果它们不相同，则用p和L.的cdr递归调用

我的尝试：

(defun find_pattern (p L)
(cond((null p) 
(cond ((null L) nil) ; p = nil, L = nil
(T L)))        ; p = nil, L != nil
((T 
(cond ((null L) nil) ; p != nil, L = nil
((eq (car p), (car L)) ; p!= nil, L != nil
(cons ((car L) (find_pattern (cdr p) (cdr L))))))
)

如果不运行这个，我已经看到一些问题：

如果我找到部分模式匹配，我将永远不会返回到完整模式。因此，诸如"(a b c)"(d a b d a b c)之类的输入会得到不正确的结果。部分结果也被附加到列表中。

有人能给我指引正确的方向吗？当我遇到部分模式时，我该如何返回到搜索完整模式？

Answer 1

这应该在Common Lisp中工作——我在这里使用的技术是在助手中传递src的副本，以跟踪当前搜索位置

(defun find-pattern-helper (xs ys src)
(cond ((null xs)
src)
((null ys)
nil)
((eq (car xs) (car ys))
(find-pattern-helper (cdr xs) (cdr ys) src))
(T
(find-pattern-helper pat (cdr src) (cdr src)))))
(defun find-pattern (pat src)
(find-pattern-helper pat src src))

或者它在拉基特。。。我有点不懂Lisp，所以这是我唯一能在中测试它的东西

#lang racket
(define (find-pattern pat src)
(let loop ((xs pat) (ys src) (src src))
(cond ((null? xs)
src)
((null? ys)
'())
((eq? (car xs) (car ys))
(loop (cdr xs) (cdr ys) src))
(#t
(loop pat (cdr src) (cdr src))))))
(find-pattern '(h e l p) '(i n e e d h e l p p l e a s e))
;; => '(h e l p p l e a s e)
(find-pattern '() '(h a y s t a c k))
;; => '(h a y s t a c k)
(find-pattern '(h a y s t a c k) '(h a y))
;; => '()