使用单个 foldr 调用编写过滤器？

Question

Objective 是只用一个 foldr 调用来编写过滤器函数，没有递归或任何其他高阶过程（map、andmap、apply 等）。

目前我正在使用

  (define (filter ps xs)
    (if (empty? xs)
        ps
        (foldr (lambda (p y)
                 (if (andmap p xs)
                     (cons p y)
                     y))
               '()
               ps)))

但是它使用的是 andmap 被认为是高阶过程的函数

目标是拥有

(filter positive? '(-1 2 3 4 -5 -6)) 
=> '(2 3 4)

只需调用一次 foldr

Answer 1

我认为你误解了 foldr 的工作原理，你必须将 list 作为最后一个参数传递给处理，并且为了实现过滤器，应用 ps 在您要测试的每个元素上。最好尝试这样的事情：

(define (filter ps xs)
  (foldr (lambda (p y)
           (if (ps p)
               (cons p y)
               y))
         '()
         xs))

它按预期工作：

(filter positive? '(-1 2 3 4 -5 -6)) 
=> '(2 3 4)

Answer 2

这听起来像是家庭作业。我明白为什么选择了 foldr，但是为了看到它是用 foldl 实现的，你去

(define (filter f xs)
  (reverse (foldl (λ (x ys) (if (f x) (cons x ys) ys))
                  null
                  xs)))

(filter positive? '(-1 2 3 4 -5 -6)) 
;=> '(2 3 4)

foldl 与 foldr 相比有明显的优势，因为它是通过适当的尾调用实现的。

使用单个 foldr 调用编写过滤器？

writing filter using a single foldr call?

scheme

filter

fold

racket