CODEWITHSUNDEEP
listschemeracket
Sebastian
Sebastian

Reputation: 27

boolean function for a sublist in scheme

I need make a boolean function for evaluating two list,for example:

   (define list1 '((1 2) (4 5) (8 6) (2 8)))
   (define list2 '((1 2) (8 6)))

list2 is a sublist of list1, and must returned #t, but I don't know how do it, I try with this function for comparing two list

(define (sublist? lst1 lst2) 
  (if (null? lst2)       
      #f                
      (if(list? (car lst2)) 
         (sublist? lst1 (car lst2))
         (if (and(equal? car(lst1) (car lst2)) (equal? cdr(lst1) (car lst2)))   
            #t (sublist? lst1 (cdr lst2))))))

help :(

Upvotes: 2

Views: 1306

Answers (2)

soegaard
soegaard

Reputation: 31147

This sublist? behaves as a "subset?".

; sublist? : list list -> "boolean"
;  return non-false if all elements of xs are in ys
(define (sublist? xs ys)
  (or (null? xs)                 ; the empty list is a sublist of ys
      (and                       ; for a non-empty list 
       (member   (car xs) ys)    ;   the first element must be in ys
       (sublist? (cdr xs) ys)))) ;   and the rest of the elements as well.

This sublist? behaves as a "substring?"

; prefix? : list list -> boolean
;   is xs a prefix of ys?
(define (prefix? xs ys)
  (or (null? xs)
      (and (equal?  (car xs) (car ys))
           (prefix? (cdr xs) (cdr ys)))))

; sublist? : list list -> boolean
;   is xs a consecutive sublist of ys?
(define (sublist? xs ys)
  (or (null? xs)
      (prefix? xs ys)
      (and (not (null? ys))
           (prefix? xs (cdr ys)))))

Upvotes: 1

Nir Alfasi
Nir Alfasi

Reputation: 53535

A suggested solution:

(define list1 '((1 2) (4 5) (8 6) (2 8)))
(define list2 '((4 5) (8 6)))

(define (sublist? lst1 lst2)        
      (if (null? lst2)
          #t
          (if (and (null? lst1) 
                   (not (null? lst2)))
              #f
              (if (list? (car lst2))
                  (or (and (sublist? (car lst1) (car lst2))
                       (sublist? (cdr lst1) (cdr lst2)))
                      (sublist? (cdr lst1) lst2))
                  (if (eq? (car lst1) (car lst2))
                    (sublist? (cdr lst1) (cdr lst2))
                    (sublist? (cdr lst1) lst2))))))

(sublist? list1 list2)

Explanation:
This is (not) simply handling all the edge-cases:
- If list2 is null - it is always a sublist of list1 - If we got to the end of list1 and list2 is not yet found - return false - If (car list2) is a list - we need to check recursively two cases: if (car list1) equals to (car list2) or if (car list2) is somewhere else in (cdr list1) - If (car list1) and (car list2) are the same - we'll check recursively with the rest of both lists: (cdr lst1) and (cdr lst2)

This answer was tested here

Upvotes: 0

Related Questions