Racket 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. This is essentially the same as Racket’s ormap function, so don’t use ormap (or andmap) anywhere in your answers.

   Implement this two different ways:

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

   Sample solution:

   ;; 1.
   (define (some1? pred lst)
     (cond
       ((empty? lst)
        #f)
       ((pred (first lst))
        #t)
       (else
        (some1? pred (rest lst)))))
   
   
   ;; 2.
   (define (some2? pred lst)
     (foldr (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. This is essentially the same as Racket’s andmap function, so don’t use andmap (or ormap) anywhere in your answers. Implement this three different ways:

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

   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 Racket functions.
   2. Using a single call to the standard Racket foldr function (and no recursion).
   3. Using the some? and/or all? functions from the previous question, and no recursion, and no use of other high-order functions such as foldr.

   Sample solution:

   ;; 1.
   (define (none1 pred lst)
     (or (empty? lst)
         (and (not (pred (first lst)))
              (none1 pred (rest lst)))))
   
   ;; 2.
   (define (none2 pred lst)
     (foldr (lambda (a acc) (and (not (pred a)) acc))
            #t lst))
   
   ;; 3.
   (define (none3 pred lst)
     (all? (lambda (x) (not (pred x))) 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? pred n lst)
     (cond
       ((null? lst)
        (= n 0))
       ((pred (first lst))
        (sat-n? pred (- n 1) (rest lst)))
       (else
        (sat-n? pred n (rest lst)))))
   

5. Implement a function called (sat-count pred lst) that returns the total number of elements of lst that satisfy pred. As an extra constraint, there should be, at most, one call to sat-count in the body of sat-count.

   Sample solution:

   (define (sat-count1 pred lst)
     (if (empty? lst)
         0
         (+ (if (pred (first lst)) 1 0)
            (sat-count1 pred (rest lst)))))
   
   (define (sat-count2 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? pred lst)
     (> (sat-count1 pred lst) 0))
   
   (define (all? pred lst)
     (= (sat-count1 pred lst) (length lst)))
   
   (define (none? pred lst)
     (= (sat-count1 pred lst) 0))
   
   (define (sat-n? pred n lst)
     (= n (sat-count1 pred lst)))
   

7. Racket has 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.

   Implement your own version of negate.

   Sample solution:

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

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

   Implement your own version of conjoin.

   Sample solution:

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

9. Implement a function called (conjoin-all plist), where plist is a non-empty list of predicate functions, that returns a new predicate that is logically equivalent to the conjunction of all the predicates on plist.

   For example:

   (define f
     (conjoin-all (list (lambda (n) (> n 0))
                        (lambda (n) (<= n 10))
                        odd?)))
   

   f is a predicate such that (f x) is true when x is bigger than 0, less than or equal to 10, and odd. So (f 0) and (f 4) are false, and (f 1) and (f 7) are true.

   Sample solution:

   (define (conjoin-all plist)
     (cond ((empty? plist)
            (error "need at least one predicate"))
           ((empty? (rest plist))
            (first plist))
           (else
            (my-conjoin (first plist)
                        (conjoin-all (rest plist))))))