Scheme - Removing Sublists from Lists of Lists

Question

I've a list of lists, eg. ((x y z) (y z) (x y)), and I was wondering if in R5RS Scheme there might be a way to remove only the sublists from this list: eg. (y z) is a sublist as it is already 'inside' (x y z)), which in our example would leave ((x y z)).

This may be more complicated than I imagine, but I'm guessing it would make use of map or filter, but I'm not sure how you'd 'clean' the whole list in this way.

Answer 1

The problem is a bit trickier than it seems. I'll be using Racket, so some non-standard functions may appear, but nothing terribly difficult to implement yourself if you're stuck with basic R5RS procedures (take a look at the documentation in case of doubts). Also be warned that I prefer a functional-programming style for my solutions, so there'll be maps, filters and other higher-order procedures.

First, we need a way for testing if a list is a sublist of another in any position; I'm using ideas from this post for generating all possible contiguous sublists:

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

Now the actual procedure, notice that I'm assuming that the input list is duplicate-free:

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

It works as expected:

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