滤波函数

Question

目前我有

(define filter 
    (λ (f xs) 
     (letrec [(filter-tail 
       (λ (f xs x) 
        (if (empty? xs) 
         x 
         (filter-tail f (rest xs) 
             (if (f (first xs)) 
              (cons (first xs) x) 
              '() 
              )))))] 
     (filter-tail f xs '())))) 

应当具有作为过滤器的功能

然而，它输出作为

(filter positive? '(-1 2 3)) 
>> (3 2) 

但正确的返回应为（2 3）

我想知道如果代码是正确使用尾递归，如果是的话，我应该使用反向改变答案？

Answer 1

我想知道代码是否正确使用尾递归。

是的，它使用了正确的尾部呼叫。你已经

(define (filter-tail f xs x) ...) 

其中，在内部被递归地应用于

(filter-tail f 
      (some-change-to xs) 
      (some-other-change-to x)) 

，对外它应用到

(filter-tail f xs '()) 

这两个应用程序都在尾部位置

我应该用相反的方式来改变答案？

是的，除非你在构建它时突变列表的尾部（而不是头部），否则没有办法解决它。您收到的评论中有一条使用set-cdr!提及（请参阅：Getting rid of set-car! and set-cdr!）。可能还有其他技术，但我不知道它们。我很乐意听到他们。

---

这是尾递归，要求输出反转。这个使用一个名为let。

(define (filter f xs) 
    (let loop ([ys '()] 
      [xs xs]) 
    (cond [(empty? xs) (reverse ys)] 
      [(f (car xs)) (loop (cons (car xs) ys) (cdr xs))] 
      [else (loop ys (cdr xs))]))) 

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

这是另一个使用左折叠的。产出仍然必须扭转。

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

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

Answer 2

随着"difference-lists"技术和curried functions，我们can have

(define (fold c z xs) 
    (cond ((null? xs) z) 
     (else (fold c (c (car xs) z) (cdr xs))))) 

(define (comp f g) (lambda (x)  ; ((comp f g) x) 
    (f (g x)))) 

(define (cons1 x) (lambda (y)  ; ((cons1 x) y) 
    (cons x y))) 

(define (filter p xs) 
    ((fold (lambda (x k) 
      (if (p x) 
       (comp k (cons1 x)) ; nesting's on the left 
       k)) 
     (lambda (x) x)   ; the initial continuation, IC 
     xs) 
    '())) 

(display (filter (lambda (x) (not (zero? (remainder x 2)))) (list 1 2 3 4 5))) 

这建立

    comp 
      /   \ 
      comp   cons1 5 
     /  \ 
    comp  cons1 3 
    / \ 
    IC  cons1 1 

，并适用'()它，在快捷从右到构建结果列表左边顺序，所以没有必要扭转它。

首先，fold通过逐个构造包含函数，以尾递归的方式构建结果列表的差异列表表示;然后将所得的函数被施加到'()和减小时，再次，在尾递归方式，由comp功能的组合物定义的优点，这是因为由函数的嵌套在左侧，作为fold是左倍，处理列表左到右：

((((IC+k1)+k3)+k5) '())  ; writing `+` for `comp` 
    => (((IC+k1)+k3) (k5 '())) ; and `kI` for the result of `(cons1 I)` 
    <= (((IC+k1)+k3) l5)   ; l5 = (list 5) 
    => ((IC+k1) (k3 l5)) 
    <= ((IC+k1) l3)    ; l3 = (cons 3 l5) 
    => (IC (k1 l3)) 
    <= (IC l1)     ; l1 = (cons 1 l3) 
    <= l1 

由fold内置功能的大小是O（n）的，就像临时名单会有，与逆转。