使用尾递归的过滤函数

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)

但正确的 return 应该是 (2 3)

我想知道代码是否使用尾递归正确完成，如果是这样，那么我应该使用反向来更改答案吗？

Answer 1

I was wondering if the code is correctly done using tail-recursion.

是的，它使用了正确的尾调用。你有

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

内部递归地应用于

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

而且，它在外部应用于

(filter-tail f xs '())

这两个应用都在尾部位置

I should use a reverse to change the answer?

是的，没有办法绕过它，除非您在构建列表时改变列表的尾部（而不是在前面加上头部）。您收到的其中一条评论使用 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" technique and curried functions, we 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通过逐个组合consing函数，以尾递归的方式构建结果列表的差异列表表示；然后将结果函数应用于 '() 并再次以尾递归方式减少，凭借 comp 函数组合定义，因为组合函数嵌套在 left，因为 fold 是 left 折叠，处理列表 left-to-right:

( (((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)，就像临时列表一样，具有反转。

使用尾递归的过滤函数

filter function using tail recursion

scheme

filter

racket