[racket] Question about tail recursion

As far as I understand it, the vast majority of the benefit of tail
recursion is less the stack-frame business and more the ability to discard
values you're not using anymore at each step by combining partial results.
To clarify what I mean, for a function sum with a recursive and
tail-recursive version:

(define (sum xs)
  (if (empty? xs) 0 (+ (first xs) (sum (rest xs)))))

(define (sum-tailrec xs)
  (let loop ([xs xs] [s 0])
    (if (empty? xs) s (loop (rest xs) (+ s (first xs))))))

> (sum '(1 2 3))
=> (+ 1 (sum '(2 3)))
=> (+ 1 (+ 2 (sum '(3))))
=> (+ 1 (+ 2 (+ 3  (sum '()))))
=> (+ 1 (+ 2 (+ 3 0)))
=> (+ 1 (+ 2 3))
=> (+ 1 5)
6

> (sum-tailrec '(1 2 3))
=> (loop '(1 2 3) 0)
=> (loop '(2 3) 1)
=> (loop '(3) 3)
=> (loop '() 6)
6

The tail recursive version is much better because you can perform the
calculation on parts of the list and then ditch those parts and accumulate
your results as you go. But for functions which don't really have any means
of accumulating their results, is there any advantage to tail recursion? If
so, how much? For clarity, consider these two implementations of filter:

(define (my-filter p xs)
  (cond
    [(empty? xs) xs]
    [(p (first xs)) (cons (first xs) (my-filter p (rest xs)))]
    [else (my-filter (rest xs))]))

(define (my-filter-tail-rec p xs)
  (let loop ([xs xs] [filtered '()])
    (cond
      [(empty? xs) (reverse filtered)]
      [(p (first xs)) (loop (rest xs) (cons (first xs) filtered))]
      [else (loop (rest xs) filtered)])))

> (my-filter even? '(1 2 3 4))
=> (my-filter even? '(2 3 4))
=> (cons 2 (my-filter even? '(3 4)))
=> (cons 2 (my-filter even? '(4)))
=> (cons 2 (cons 4 (my-filter even? '())))
=> (cons 2 (cons 4 '()))
=> (cons 2 '(4))
'(2 4)

> (my-filter-tail-rec even? '(1 2 3))
=> (loop '(1 2 3 4) '())
=> (loop '(2 3 4) '())
=> (loop '(3 4) '(2))
=> (loop '(4) '(2))
=> (loop '() '(4 2))
=> (reverse '(4 2))
'(2 4)

The tail recursion doesn't really help much in this problem, because the
only real difference is that the tail recursive version holds the filtered
values in a list instead of consing them on the stack. With the summing,
you could take the values and combine them into something much more compact
in terms of space by just summing them and passing the partial sum, but
there is no logical "compacting" operation that can be done with filtering.
So is there much of any performance or algorithmic difference between tail
recursive and normal recursive functions when tail recursion is achieved
simply by storing intermediate values in a list argument instead of consing
them on the stack? And is that difference significant enough to justify the
cost of reversing the list and the added complexity of writing the code in
a tail recursive fashion?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140808/736c3deb/attachment.html>