CODEWITHSUNDEEP
listrecursionschemeracketsublist
Kiley
Kiley

Reputation: 39

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

I'm new to coding in racket, but I wanted to define a procedure that checks to see if a given list is a sublist (or part of) another list.

This is my code so far:

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

I've tried most cases and it works the way it's supposed to but when I tried this test case:

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

It returns #f when it's supposed to return #t I tried tracing the sublist? procedure but it isn't returning me any useful information.

Is there a logic error in my code?

Upvotes: 0

Views: 629

Answers (2)

alinsoar
alinsoar

Reputation: 15793

try this:

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

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

There is a logic error. The default case of sublist? should call sublist?, but instead calls prefix? so your prefix? will only be true if the match is either in index 0 or 1.

Also you have created a rather complex prefix?. Instead of comparing one by one element until any of them are empty you do a O(n) removal of the last element until you have a empty list before returning #f even if the two first elements are different. I would have compared the first elements and then recurred with rest in both args until either list is empty. Which one depends on the result and eg. (prefix '(a b) '(w a d f s)) will stop computing after the very first check between a and w.

Upvotes: 2

Related Questions