Ok - I think I get it: the "unless" can be thought of as inside of an implicit "begin," and isn't in tail position anymore. If I move the "display" statement right before the line with "result" I can watch my results evaporating when the stack is unwinding.
Thanks for finding that! On Fri, Nov 27, 2020 at 12:01 AM George Neuner <[email protected]> wrote: > > On 11/26/2020 11:22 PM, Tim Meehan wrote: > > I was trying to turn one of Knuth's random number sampling without > replacement algorithms. It seems to be working, but when it comes time to > return my prize ... nothing :( > > I thought that since I was returning from inside of the named let, that > I'd get back my collection of numbers sampled without replacement. > > ;; algorithm taken from: > ;; > https://stackoverflow.com/questions/311703/algorithm-for-sampling-without-replacement > (define (sample-without-replacement n N) > (let loop ([num-seen 0] > [num-stored 0] > [result '()]) > (let ([u (random)]) > (display (format "~a\n" result)) > (unless (>= num-stored n) > (if (>= (* u (- N num-seen)) (- n num-stored)) > (loop (add1 num-seen) num-stored result) > (loop (add1 num-seen) (add1 num-stored) (cons num-seen > result)))) > result))) > > > How to explain this ... > > The problem is that 'unless' does not end the function - the calls to > 'loop' are *not* in tail position, so although you are recursing, you are > not tail-recursing. Your code doesn't exit at the bottom but rather > unwinds the call stack, returning from 'loop' and and evaluating 'result' > every time. At the top level, 'result' is the empty list (passed as the > argument) and that is what is being returned. > > Contrast with: > (if (>= num-stored n) > result > (if (>= (* u (- N num-seen)) (- n num-stored)) > (loop (add1 num-seen) num-stored result) > (loop (add1 num-seen) (add1 num-stored) (cons num-seen > result)))) > > When you have this kind of multiple test logic, 'cond' is your friend: > (cond > ((>= num-stored n) > result) > ((>= (* u (- N num-seen)) (- n num-stored)) > (loop (add1 num-seen) num-stored result)) > (else > (loop (add1 num-seen) (add1 num-stored) (cons num-seen result)))) > > Hope this helps, > George > -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CACgrOxKrOE6PUnDKwpT%3DM02T-fByxxEbC50o-enBSWi6uxMdAw%40mail.gmail.com.
