filter function using tail recursion

Question

Currently I have

  (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 '() ))))

It should be have as a filter function

However it outputs as

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

but correct return should be (2 3)

I was wondering if the code is correctly done using tail-recursion, if so then I should use a reverse to change the answer?

It is possible to implement a head sentinel or tail-modulo cons as you add to an accumulator, however just reversing it at the end is the most straightforward solution of the problem. — WorBlux, Feb 23 '16 at 08:10
Lists are iterated from beginning to end and created from end to beginning. Thus a tail recursive copy would reverse the input. — Sylwester, Feb 23 '16 at 14:00
"Does that apply to all tail-recursions?" no; you can use "surgical" list structure-mutating `set-cdr!` and keep adding new nodes at the growing list's end. see [this](http://stackoverflow.com/a/14952631/849891) or [this](http://stackoverflow.com/a/13256555/849891) for some example code, or [tag:tailrecursion-modulo-cons] in general. — Will Ness, Feb 23 '16 at 16:13
This question is tagged . Racket has no (really usable) mutable lists so the alternatives mentioned in the comments are not easily available and certainly not recommended. — uselpa, Feb 23 '16 at 19:51
@uselpa it is also tagged [tag:scheme]. -- Why aren't Racket's mutable lists usable? — Will Ness, Feb 23 '16 at 23:07
In Racket, there's [`mlist->list`](https://docs.racket-lang.org/compatibility/mlists.html#%28def._%28%28lib._compatibility%2Fmlist..rkt%29._mlist-~3elist%29%29). So you can tail-recurse along the list, adding each element at the end of the interim mutable list (with `set-cdr!` and `set!`), and then convert that mutable list back with an `mlist->list` call. — Will Ness, Mar 25 '16 at 12:26

Mulan · Accepted Answer · 2016-02-23T20:03:06.980

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

Yes, it is using a proper tail call. You have

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

Which, internally is recursively applied to

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

And, externally it's applied to

(filter-tail f xs '())

Both of these applications are in tail position

I should use a reverse to change the answer?

Yep, there's no way around it unless you're mutating the tail of the list (instead of prepending a head) as you build it. One of the comments you received alluded to this using set-cdr! (see also: Getting rid of set-car! and set-cdr!). There may be other techniques, but I'm unaware of them. I'd love to hear them.

This is tail recursive, requires the output to be reversed. This one uses a named 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)

Here's another one using a left fold. The output still has to be reversed.

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

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

Will Ness · Answer 2 · 2018-02-09T00:44:45.503

With the "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)))

This builds

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

and applies '() to it, constructing the result list in the efficient right-to-left order, so there's no need to reverse it.

First, fold builds the difference-list representation of the result list in a tail recursive manner by composing the consing functions one-by-one; then the resulting function is applied to '() and is reduced, again, in tail-recursive manner, by virtues of the comp function-composition definition, because the composed functions are nested on the left, as fold is a left fold, processing the list 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

The size of the function built by fold is O(n), just like the interim list would have, with the reversal.

filter function using tail recursion

2 Answers2