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

Question

目的是编写过滤器函数，只使用一个没有递归的foldr调用或任何其他高阶过程(map、map、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)

只需一次呼救

Answer 1

我认为您误解了foldr是如何工作的，您必须将列表作为最后一个参数进行处理，为了实现过滤器，对要测试的每个元素应用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相比有明显的优势，因为它是通过适当的尾调用来实现的。