计划 - 从列表中删除子列表

Question

我有一个列表列表，例如。 ((x y z) (y z) (x y))，我想知道是否在R5RS Scheme有一种方法可以从列表中删除只有子列表：例如。 (y z)是一个子列表，因为它已经'在'(x y z))之内，在我们的示例中它将离开((x y z))。

这可能比我想象的更复杂，但我猜它会利用地图或过滤器，但我不知道如何以这种方式“清理”整个列表。

Answer 1

这个问题比看起来有点棘手。我将使用Racket，因此可能会出现一些非标准功能，但如果您坚持使用基本的R5RS程序（如果存在疑问，请参阅documentation），但实施起来并不难。另外值得警告的是，我更喜欢我的解决方案的功能编程风格，所以会有map s，filter s和其他更高阶的程序。

首先，我们需要一种方法来测试列表是否是另一个的子列表;我使用的是从this post想法产生所有可能的连续子列表：

(define (inits lst) 
    (let loop ((acc '()) 
      (n (length lst))) 
    (if (negative? n) 
     acc 
     (loop (cons (take lst n) acc) (sub1 n))))) 

(define (tails lst) 
    (let loop ((acc '()) 
      (n (length lst))) 
    (if (negative? n) 
     acc 
     (loop (cons (drop lst n) acc) (sub1 n))))) 

(define (contiguous-sublists lst) 
    (cons '() 
     (remove* '(()) 
       (append-map inits (tails lst))))) 

(define (sublist? l1 l2) 
    (if (member l1 (contiguous-sublists l2)) #t #f)) 

现在的实际过程中，请注意，我假设输入列表是重复的免费电话：

(define (remove-sublists lst) 
    (filter 
    (lambda (l1) 
    (andmap 
     (lambda (l2) 
     (not (sublist? l1 l2))) 
     (remove l1 lst))) 
    lst)) 

它的工作原理如预期的那样：

(remove-sublists '((x y z) (y z) (x y))) 
=> '((x y z))