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 <gneun...@comcast.net> 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 racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CACgrOxKrOE6PUnDKwpT%3DM02T-fByxxEbC50o-enBSWi6uxMdAw%40mail.gmail.com.
