Question

you are required to use only the functional features of Scheme; functions with an exclamation point in their names (e.g., set!) and input/output mechanisms other than load and the regular read-eval-print loop are not allowed. (You may find imperative features useful for debugging. That’s ok, but get them out of your code before you hand anything in.)

Write a function sublist that takes two lists as arguments, and returns true if the first list appears as a contiguous sublist somewhere within the second list, and false otherwise.

> (sublist ’(c d e) ’(a b c d e f g))

#t

> (sublist ’(a c e) ’(a b c d e f g))

#f

using the programming language scheme

Answer 1

Code:

(define (sublist ls1 ls2) ;;MAIN_Function
(cond ((null? ls2) #f) ;;if second list empty returns false
((null? ls1) #t) ;;if first list is empty returns true
(else (sublist1 ls1 (check (car ls1) ls2)))))

;;Ex: (check '(c d e) '(c d c d e))returns ((c d c d e) (c d e))
(define (check n list) ;;returns list strting with first element of given sublist
(cond ((null? list) '())
((equal? n (car list)) (cons list (check n (cdr list))))
(else (check n (cdr list)))))

;;Ex:(sublist '(c d e) '((c d c d e) (c d e))) returns #t
(define (sublist1 ls1 ls2) ;;HELPER_FUNCTION
(cond ((null? ls2) #f)
((null? ls1) #t)
((equal? (sublist2 ls1 (car ls2)) #t) #t)
(else (sublist1 ls1 (cdr ls2)))))

;;Ex:(sublist '(c d e) '(c d c d e)) returns #t
(define (sublist2 ls1 ls2) ;;HELPER_FUNCTION
(cond ((null? ls2) #f) ;;if second list empty returns false
((null? ls1) #t) ;;if first list is empty returns true
((equal? (car ls1) (car ls2)) (sublist3 (cdr ls1) (cdr ls2))) ;;if first element of list 1 equal to first element
;;check rest of the elements of list1 are contigeous subset of list2
(else (sublist2 ls1 (cdr ls2))))) ;;else continue with rest of list2

(define (sublist3 ls1 ls2) ;;HELPER_FUNCTION
(cond ((null? ls1) #t) ;;if second list empty returns false
((null? ls2) #f) ;;if first list is empty returns true
((equal? (car ls1) (car ls2)) (sublist3 (cdr ls1) (cdr ls2))) ;;if first element of list 1 equal to first element check rest elements
(else #f))) ;;else sublist is not contigeous, so returns false.

Snapshot of Code and Output: