writing filter function using foldr?

Question

Currently trying to write a filter function that takes a list of procedures and a list of numbers, deletes the procedures that does not return true on every element of the list of numbers.

What I have done is the following, currently taking a single procedure and runs through the list to create a list stating whether the procedure is true or false for each element.

Using foldr, or map if required (non recursive)

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

How do I delete the procedure if it has at lease one #f?

i.e. currently

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

want

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

Answer 1

Start with some wishful thinking. Say we have a know of knowing if all xs return #t for any given f

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

Now let's define every?

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

Let's check it out for (list even?)

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

Let's add another test in the mix

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

Cool !

---

If you want to see "pretty" procedure names instead of the #<procedure:...> stuff, you can map object-name over the resulting array

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

Even though foldl will give you a reversed output, I still think it would be better to use foldl in this case. Just my 2 cents.

Answer 2

You can solve this by using Racket's built-in andmap procedure, which tests if a condition is true for all elements in a list - like this:

(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

Notice that we do not "delete" functions from the output list, instead at each step we decide whether or not we should add them to the output list.

The advantage of foldr is that it preserves the same order as the input list, if that's not a requirement, foldl is more efficient because internally it uses tail recursion. Either way, it works as expected:

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

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