使用 foldr 编写过滤功能？

Question

目前正在尝试编写一个过滤函数，该函数接受一个过程列表和一个数字列表，删除在数字列表的每个元素上都不 return 正确的过程。

我所做的是以下内容，目前采用单个过程并遍历列表以创建一个列表，说明每个元素的过程是真还是假。

如果需要，使用 foldr 或 map（非递归）

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

太棒了！

如果您想查看 "pretty" 过程名称而不是 #<procedure:...> 内容，您可以将 object-name 映射到结果数组

(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

您可以使用 Racket 的内置 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

请注意，我们不"delete"输出列表中的函数，而是在每一步决定是否将它们添加到输出列表中。

foldr is that it preserves the same order as the input list, if that's not a requirement, foldl的优点是效率更高，因为它内部使用了尾递归。无论哪种方式，它都按预期工作：

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

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

使用 foldr 编写过滤功能？

writing filter function using foldr?

scheme

filterfunction

fold

racket