CODEWITHSUNDEEP
schemeracketprimeshigher-order-functionssieve-algorithm
Zoe Sun
Zoe Sun

Reputation: 89

How to solve this Racket problem using higher order functions?

I am stuck on Q2.

Q1. Write a function drop-divisible that takes a number and a list of numbers, and returns a new list containing only those numbers not "non-trivially divisible" by the the number.

This is my answer to Q1.

(define (drop-divisible x lst)
    (cond [(empty? lst) empty] 
    ; if the number in the list is equal to the divisor 
    ; or the number is not divisible, add it to the result list 
    [(or (= x (first lst))(< 0 (remainder (first lst) x))) (cons (first lst) (drop-divisible x (rest lst)))] 
    [else (drop-divisible x (rest lst))]))


(module+ test
(check-equal? (drop-divisible 3 (list 2 3 4 5 6 7 8 9 10)) (list 2 3 4 5 7 8 10)))

Q2. Using drop-divisible and (one or more) higher order functions filter, map, foldl, foldr. (i.e. no explicit recursion), write a function that takes a list of divisors, a list of numbers to test, and applies drop-divisible for each element of the list of divisors. Here is a test your code should pass

(module+ test
    (check-equal? (sieve-with '(2 3) (list 2 3 4 5 6 7 8 9 10)) (list 2 3 5 7)))

I can come up with a snippet that only takes the second list, which does the same work as the solution to Q1.

(define (sieve-with divisors lst) 
    (filter (lambda (x) ((lambda (d)(or (= d x)(< 0 (remainder x d)))) divisors)) lst))

I tried to modify the snippet with 'map' but couldn't make it work as intended. I also can't see how 'foldr' may possibly be used here.

Upvotes: 1

Views: 691

Answers (1)

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236034

In this case, foldl is the right tool to use (foldr will also give a correct answer, albeit less efficiently, when the divisors are in increasing order). The idea is to take the input list and repeatedly applying drop-divisible on it, once per each element in the divisors list. Because we accumulate the result between calls, in the end we'll obtain a list filtered by all of the divisors. This is what I mean:

(define (sieve-with divisors lst)
  ; `e` is the current element from the `divisors` list
  ; `acc` is the accumulated result
  (foldl (lambda (e acc) (drop-divisible e acc))
         lst        ; initially, the accumulated result
                    ; is the whole input list
         divisors)) ; iterate over all divisors

I used a lambda to make explicit the parameter names, but in fact you can pass drop-divisible directly. I'd rather write this shorter implementation:

(define (sieve-with divisors lst)
  (foldl drop-divisible lst divisors))

Either way, it works as expected:

(sieve-with '(2 3) '(2 3 4 5 6 7 8 9 10))
=> '(2 3 5 7)

Upvotes: 3

Related Questions