如何使用高阶函数解决这个 Racket 问题？

Question

我卡在第二季度了。

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.

这是我对问题 1 的回答。

(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)))

我可以想出一个只包含第二个列表的代码片段，它的作用与 Q1 的解决方案相同。

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

我尝试用 'map' 修改代码段，但无法使其按预期工作。我也看不出如何在这里使用 'foldr'。

Answer 1

在这种情况下，foldl 是正确的工具（foldr 也会给出正确的答案，尽管当除数为递增顺序时效率较低）。这个想法是获取输入列表并在其上重复应用 drop-divisible ，每个除数列表中的每个元素一次。因为我们在调用之间累积结果，所以最后我们将获得一个由 all 个除数过滤的列表。这就是我的意思：

(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

我用了一个lambda来明确参数名，但实际上你可以直接传递drop-divisible。我宁愿写这个更短的实现：

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

无论哪种方式，它都按预期工作：

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

如何使用高阶函数解决这个 Racket 问题？

How to solve this Racket problem using higher order functions?

scheme

primes

sieve

higher-order-functions

racket