запись фильтр функция используя foldr?

Question

В настоящее время пытается написать функцию фильтра, которая принимает список процедур и список номеров, удаляет процедуры, которые не возвращают true для каждого элемента списка чисел.

Что я сделал, это следующее, в настоящее время выполняется одна процедура и проходит через список, чтобы создать список, указывающий, истинна или ложна процедура для каждого элемента.

Использование foldr или карту, если это необходимо (не рекурсивный)

(define (my-filter ps xs) 
    (foldr (λ (x y) 
      (cons (ps x) y)) '() xs)) 

Как удалить процедуру, если она имеет по крайней мере одного #F?

т.е. в настоящее время

> (my-filter even? '(1 2 3 4)) 
(#f #t #f #t) 
> (my-filter even? (2 4)) 
(#t #t) 

хотят

> (my-filter (list even?) '(1 2 3 4)) 
(list) 
> (my-filter (list even?) '(2 4)) 
(list even?) 

Answer 1

Начните с какой-то желаемое за действительное. Скажем, у нас есть ноу знать, если все xs возвращение #t для любого заданного f

(define (my-filter fs xs) 
    (foldr (λ (f y) 
      (if (every? f xs) 
       (cons f y) 
       y)) 
     '() 
     fs)) 

Теперь давайте определим every?

(define (every? f xs) 
    (cond [(null? xs) #t] 
     [(f (car xs)) (every? f (cdr xs))] 
     [else #f])) 

Давайте проверим это для (list even?)

(my-filter (list even?) '(1 2 3 4)) ; ⇒ '() 
(my-filter (list even?) '(2 4))  ; ⇒ '(#<procedure:even?>) 

Давайте добавим еще один испытание в смеси

(define (gt3? x) (> x 3)) 

(my-filter (list even? gt3?) '(2 4)) ; ⇒ '(#<procedure:even?>) 
(my-filter (list even? gt3?) '(4 6)) ; ⇒ '(#<procedure:even?> #<procedure:gt3?>) 

Прохладный!

---

Если вы хотите увидеть имена «довольно» процедуры вместо этого #<procedure:...> вещей, вы можете отобразить object-name над результирующим массивом

(map object-name (my-filter (list even? gt3?) '(4 6))) ; ⇒ '(even? gt3?) 

Даже если foldl даст вам перевернутый выход, Я все еще думаю, что в этом случае было бы лучше использовать foldl. Только мои 2 цента.

Answer 2

Вы можете решить эту проблему с помощью ракеток встроенного andmap процедуры, которая проверяет, если условие истинно для всех элементов в списке - как это:

(define (my-filter ps xs) 
    (foldr (lambda (f acc) 
      (if (andmap f xs) ; if `f` is true for all elements in `xs` 
       (cons f acc) ; then add `f` to the accumulated output 
       acc))   ; otherwise leave the accumulator alone 
     '()     ; initially the accumulator is an empty list 
     ps))    ; iterate over the list of functions 

Обратите внимание, что мы не «удалить "из выходного списка, вместо этого на каждом шаге мы решаем, следует ли добавлять их в выходной список.

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

(my-filter (list even?) '(1 2 3 4)) 
=> '() 

(my-filter (list even?) '(2 4)) 
=> '(#<procedure:even?>)