Basically, avoiding growing the stack when building a list, by
compiling this program:
(define (list-id l)
(if (null? l) l
(cons (car l) (list-id (cdr l)))))
into this one:
(define (list-id* l acc)
(if (null? l)
(set-cdr! acc null)
(let ([p (cons (car l) #f)])
(set-cdr! acc p)
(list-id (cdr l) p))))
There's a pretty good discussion on Wikipedia:
http://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons
Note that this doesn't run in constant space, since we're allocating a
pair at each step, but it changes the complexity from 2n to n.
Sam
On Sun, Mar 16, 2014 at 5:13 PM, Matthias Felleisen
<matth...@ccs.neu.edu> wrote:
>
> What does tail-recursion modulo cons mean?
>
>
> On Mar 16, 2014, at 3:38 PM, Sam Tobin-Hochstadt wrote:
>
>> On Sun, Mar 16, 2014 at 2:55 PM, Patrick Useldinger
>> <uselpa.l...@gmail.com> wrote:
>>>
>>>
>>> My questions are:
>>>
>>> (1) Is Racket "tail-recursive modulo cons"? If not, is there a reason for
>>> this?
>>
>> Racket is not "tail-recursive modulo cons".
>>
>>> (2) Is the last example "reverse free" or does it use reverse under the
>>> hood?
>>
>> `for/list` uses `reverse` internally -- you can see for yourself how
>> this works by using the Macro Stepper.
>>
>>> (3) finally, what is the recommended way to write this procedure in terms of
>>> performance?
>>
>> I took your program, and made all the functions run on much longer
>> lists. Here are the timings:
>>
>> $ r /tmp/even-list.rkt
>> 'plain
>> cpu time: 1288 real time: 1294 gc time: 936
>> 't
>> cpu time: 440 real time: 441 gc time: 320
>> 'for/fold
>> cpu time: 484 real time: 485 gc time: 328
>> 'mcons
>> cpu time: 204 real time: 204 gc time: 148
>> 'mcons-convert
>> cpu time: 632 real time: 631 gc time: 416
>> 'for/list
>> cpu time: 460 real time: 460 gc time: 332
>>
>> 'mcons-convert is one that uses `mcons`, but converts back to plain
>> `cons` at the end.
>>
>> Sam
>> ____________________
>> Racket Users list:
>> http://lists.racket-lang.org/users
>
____________________
Racket Users list:
http://lists.racket-lang.org/users
