reservoir sampling


Write a procedure that randomly samples k elements from an arbitrarily large collection of elements.

 $ cat rs.scm 
 (use-modules 
   ((srfi srfi-41) #:renamer (symbol-prefix-proc 'srfi41:))) 
  
 (include-from-path "srfi-78/srfi-78.scm") 
 (check-set-mode! 'summary) 
  
 (define (reservoir-sample stream k) 
   (if (< k 1) 
     (vector) 
     (let ((r (list->vector (srfi41:stream->list k stream)))) 
       (let loop ((i (+ k 1)) (s (srfi41:stream-drop k stream))) 
           (unless (srfi41:stream-null? s) 
             (let ((j (random i))) 
               (when (< j k) 
                 (vector-set! r j (srfi41:stream-car s))) 
               (loop (+ i 1) (srfi41:stream-cdr s))))) 
       r))) 
  
 (check (reservoir-sample srfi41:stream-null 0) => (vector)) 
 (check (reservoir-sample srfi41:stream-null 10) => (vector)) 
 (check (reservoir-sample (srfi41:stream-cons 1 srfi41:stream-null) 10) => #(1)) 
  
 (define (stream-iota n) 
   (letrec ((si (srfi41:stream-lambda (i) 
                  (if (< i n) 
                    (srfi41:stream-cons i (si (+ i 1))) 
                    srfi41:stream-null)))) 
     (si 0))) 
  
 (check (reservoir-sample (stream-iota 10) 10) => #(0 1 2 3 4 5 6 7 8 9)) 
 (check (reservoir-sample (stream-iota 8) 10) => #(0 1 2 3 4 5 6 7)) 
  
 (check-report) 
  
 $ guile rs.scm 
  
 ; *** checks *** : 5 correct, 0 failed. 
  
 $