Как решить эту проблему с помощью функций высшего порядка? - PullRequest
Новая
       42

Как решить эту проблему с помощью функций высшего порядка?

0 голосов
/ 21 сентября 2018

Я застрял на Q2.

Q1.Напишите функцию drop-divisible, которая принимает число и список чисел и возвращает новый список, содержащий только те числа, которые не являются «нетривиально делимыми» числом.

Это мой ответдо 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.Использование drop-делимых и (одной или нескольких) функций высшего порядка filter, map, foldl, foldr.(т.е. без явной рекурсии), напишите функцию, которая принимает список делителей, список чисел для проверки и применяет деление по каплям для каждого элемента списка делителей.Вот тест, который ваш код должен пройти 

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

Я пытался изменить фрагмент с помощью «карты», но не смог заставить его работать как задумано.Я также не понимаю, как здесь можно использовать 'foldr'.

1 Ответ

0 голосов
/ 21 сентября 2018

В этом случае foldl - правильный инструмент для использования (foldr также даст правильный ответ, хотя и менее эффективно, когда делители находятся в возрастающем порядке).Идея состоит в том, чтобы взять список ввода и многократно применять к нему drop-divisible, по одному разу для каждого элемента в списке делителей.Поскольку мы накапливаем результат между вызовами, в конце мы получим список, отфильтрованный по всем делителям.Вот что я имею в виду: 

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