[racket] Tail recursive module cons
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