計劃 - 從列表中刪除子列表

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))