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. $