schemeracketfoldfilterfunction

writing filter function using foldr?


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

Solution

  • 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.