named let ...

[Tim Meehan]

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)))

[George Neuner]

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

[Tim Meehan]

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!