[racket] Tail recursive module cons

From: Patrick Useldinger (uselpa.list at gmail.com)
Date: Sun Mar 16 14:55:56 EDT 2014

Greetings everybody,

Let's assume we want a procedure that doubles every even? number of a list.

The recursive way would be something like:

(require rackunit)
(define parms '(1 2 3 4 5))
(define result '(4 8))

(define (f-recursive lst)
   (if (null? lst)
       null
       (let ((c (car lst)))
         (if (even? c)
             (cons (* 2 c) (f-recursive (cdr lst)))
             (f-recursive (cdr lst))))))

(check-equal? (f-recursive parms) result)

Since this will build up a lot of stack for longer lists, we'd like it 
to be tail recursive for performance reasons:

(define (f-trecursive lst)
   (let loop ((lst lst) (res null))
     (if (null? lst)
         (reverse res)
         (let ((c (car lst)))
           (if (even? c)
               (loop (cdr lst) (cons (* 2 c) res))
               (loop (cdr lst) res))))))

(check-equal? (f-trecursive parms) result)

but this unfortunately needs an annoying call to reverse, as does the 
"for/fold" version

(define (f-frecursive lst)
   (reverse
    (for/fold ((res null)) ((c (in-list lst)))
      (if (even? c)
          (cons (* 2 c) res)
          res))))

(check-equal? (f-frecursive parms) result)

Some people like to use the head-sentinel trick unless the compiler is 
"tail recursive modulo cons"

(define (f-mcrecursive lst)
   (let ((res (mcons 'sentinel null)))
     (let loop ((lst lst) (p res))
       (if (null? lst)
           (mcdr res)
           (let ((c (car lst)))
             (if (even? c)
                 (begin
                   (set-mcdr! p (mcons (* 2 c) null))
                   (loop (cdr lst) (mcdr p)))
                 (loop (cdr lst) p)))))))

(define mresult (mcons 4 (mcons 8 null)))
(check-equal? (f-mcrecursive parms) mresult)

which will work fine but return a mlist which is unhandy and depreciated 
in Racket, so it will need an additional step to convert it to an 
non-mutable list (so we didn't gain anything by leaving out reverse)

Finally there is the "for/list" loop with "#:when" option:

(define (f-f2recursive lst)
   (for/list ((c (in-list lst))
              #:when (even? c))
     (* 2 c)))

(check-equal? (f-f2recursive parms) result)

My questions are:

(1) Is Racket "tail-recursive modulo cons"? If not, is there a reason 
for this?

(2) Is the last example "reverse free" or does it use reverse under the 
hood?

(3) finally, what is the recommended way to write this procedure in 
terms of performance?

Regards,
-Patrick


Posted on the users mailing list.