Racket/Scheme - 检查一个列表是否是另一个列表的子列表

Question

我是 racket 编码的新手，但我想定义一个过程来检查给定列表是否是另一个列表的子列表（或一部分）。

到目前为止，这是我的代码：

(define prefix?
  (lambda (lst1 lst2)
    (cond 
      ((equal? lst1 lst2) #t)
      ((null? lst2) #f)
      (else (prefix? lst1 (reverse (rest (reverse lst2))))))))

(define sublist?
  (lambda (lst1 lst2)
    (cond
      ((prefix? lst1 lst2) #t)
      ((null? lst2) #f)
      (else (prefix? lst1 (rest lst2))))))

我已经尝试了大多数案例并且它按预期的方式工作但是当我尝试这个测试案例时：

(sublist? '(a b d) '(a b c a b d e))

它 returns #f 当它应该 return #t 我试过追踪子列表？程序，但它 return 没有给我任何有用的信息。

我的代码有逻辑错误吗？

Answer 1

存在逻辑错误。 sublist? 的默认情况应该调用 sublist?，而不是调用 prefix?，因此只有当匹配位于索引 0 或 1 中时，您的 prefix? 才会为真。

您还创建了一个相当复杂的 prefix?。不是逐个比较元素直到其中任何一个为空，而是 O(n) 删除最后一个元素，直到在返回 #f 之前有一个空列表，即使前两个元素不同也是如此。我会比较第一个元素，然后在两个参数中用 rest 重复出现，直到任一列表为空。哪一个取决于结果，例如。 (prefix '(a b) '(w a d f s)) 将在 a 和 w 之间的第一次检查后停止计算。

Answer 2

试试这个：

(define sub?
  (lambda (l sub)
    (define test (lambda (x) (equal? x sub)))
    ((lambda (s) (s s l test))
     (lambda (s l k)
       (or (k '())
           (and (pair? l)
                (s s (cdr l)
                   (lambda (r)
                     (or (test r)
                         (k (cons (car l) r)))))))))))


(sub? '(a b c a b d e) '(b d e) )
(sub? '(a b c a b d e) '(c a b) )
(sub? '(a b c a b d e) '(a b c) )
(sub? '(a b c a b x e) '(a b d) )

Racket/Scheme - 检查一个列表是否是另一个列表的子列表

Racket/Scheme - checking to see if a list is a sublist of another list

recursion

scheme

list

sublist

racket