Scheme Practice Questions (Solutions)

In the following questions, pred is a predicate, i.e. a function that takes one input and returns either #t or #f. If (pred x) is #t, then we say that x satsifies pred.

1. Implement a function called (some? pred lst) that returns #t if 1, or more, elements of lst satisfy pred, and #f otherwise. Implement this two different ways:

   1. Recursively using basic Scheme functions.
   2. Using a single call to the standard Scheme fold function (and no recursion).

   Sample solution:

   ;; 1.
   (define some1?
       (lambda (pred lst)
           (cond
               ((null? lst)
                   false)
               ((pred (car lst))
                   true)
               (else
                  (some1? pred (cdr lst)))
           )
       )
   )
   
   
   ;; 2.
   (define some2?
       (lambda (pred lst)
           (fold (lambda (a b) (or (pred a) b)) #f lst)
       )
   )
   

2. Implement a function called (all? pred lst) that returns #t if all the elements of lst satisfy pred, and #f otherwise. Implement this three different ways:

   1. Recursively using basic Scheme functions.
   2. Using a single call to the standard Scheme fold function (and no recursion).
   3. Using the some? function from the previous question, and no recursion, and no use of fold.

   Sample solution:

   ;; 1.
   (define all1?
       (lambda (pred lst)
           (cond
               ((null? lst)
                   #t)
               (else
                   (and (pred (car lst))
                        (all1? pred (cdr lst))))
           )
       )
   )
   
   ;; 2.
   (define all2?
       (lambda (pred lst)
           (fold (lambda (a b) (and (pred a) b)) #t lst)
       )
   )
   
   ;; 3.
   (define all3?
       (lambda (pred lst)
           (not (some? (lambda (x) (not (pred x)))
                       lst
                )
           )
       )
   )
   

3. Implement a function called (none? pred lst) that returns #t if 0 elements of lst satisfy pred, and #f otherwise. Implement this three different ways:

   1. Recursively using basic Scheme functions.
   2. Using a single call to the standard Scheme fold function (and no recursion).
   3. Using the some? and/or all? functions from the previous question, and no recursion, and no use of fold.

   Sample solution:

   ;; 1.
   (define none?
       (lambda (pred lst)
           (cond
               ((null? lst)
                   #t)
               (else
                   (and (not (pred (car lst)))
                        (none? pred (cdr lst))))
           )
       )
   )
   
   ;; 2.
   (define none2?
       (lambda (pred lst)
           (fold (lambda (a b) (and (not (pred a)) b))
                 #t lst)
       )
   )
   
   ;; 3.
   (define none3?
       (lambda (pred lst)
           (not (some? pred lst))
       )
   )
   

4. Implement a function called (sat-n? pred n lst) that returns #t if exactly n elements of lst satisfy pred, and #f otherwise.

   Sample solution:

   (define sat-n?
       (lambda (pred n lst)
           (cond
               ((null? lst)
                   (= n 0))
               ((pred (car lst))
                   (sat-n? pred (- n 1) (cdr lst)))
               (else
                   (sat-n? pred n (cdr lst)))
           )
       )
   )
   

5. Implement a function called (sat-count pred lst) that returns the total number of elements of lst that satisfy pred.

   Sample solution:

   (define sat-count
       (lambda (pred lst)
           (cond
               ((null? lst)
                   0)
               ((pred (car lst))
                   (+ 1 (sat-count pred (cdr lst))))
               (else
                   (sat-count pred (cdr lst)))
           )
       )
   )
   
   ;; or
   (define (sat-count pred lst) (length (filter pred lst)))
   

6. Re-implement some?, all?, none?, and sat-n? using a single call to sat-count for each.

   Sample solution:

   (define some?
       (lambda (pred lst)
           (> (sat-count pred lst) 0)
       )
   )
   
   (define all?
       (lambda (pred lst)
           (> (sat-count pred lst) (length lst))
       )
   )
   
   (define none?
       (lambda (pred lst)
           (= 0 (sat-count pred lst))
       )
   )
   
   (define sat-n?
       (lambda (pred n lst)
           (= n (sat-count pred lst))
       )
   )
   

7. Write a function called (negate pred) that returns a new predicate that is the negation of pred. For example (negate zero?) returns a new function that returns #t when it is passed a non-zero input, and #f if it is passed 0. The function (zero? n) is built-in and returns #t just when n is 0.

   Sample solution:

   (define negate
       (lambda (pred)
           (lambda (x) (not (pred x)))
       )
   )
   

8. Write a function called (conjoin pred1 pred2) that returns a new predicate that behaves the same as pred1 and pred2 and-ed together.

   Sample solution:

   (define conjoin
       (lambda (pred1 pred2)
           (lambda (x) (and (pred1 x) (pred2 x)))
       )
   )
   

9. Write a function called (disjoin pred1 pred2) that returns a new predicate that behaves the same as pred1 and pred2 or-ed together.

   Sample solution:

   (define disjoin
       (lambda (pred1 pred2)
           (lambda (x) (or (pred1 x) (pred2 x)))
       )
   )