| 1 |
;;; |
| 2 |
;;; data.random - Random data genarators |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2013-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
(define-module data.random |
| 35 |
(use scheme.list) |
| 36 |
(use scheme.charset) |
| 37 |
(use srfi.27) |
| 38 |
(use srfi.42) |
| 39 |
(use util.match) |
| 40 |
(use math.const) |
| 41 |
(use math.mt-random) |
| 42 |
(use gauche.uvector) |
| 43 |
(use gauche.generator) |
| 44 |
(use gauche.sequence) |
| 45 |
|
| 46 |
(export random-data-random-source |
| 47 |
|
| 48 |
integers$ integers-between$ fixnums$ chars$ |
| 49 |
samples$ booleans$ |
| 50 |
int8s$ uint8s$ int16s$ uint16s$ int32s$ uint32s$ int64s$ uint64s$ |
| 51 |
reals$ reals-between$ finite-flonums$ |
| 52 |
complexes-rectangular$ complexes-polar$ |
| 53 |
reals-normal$ reals-exponential$ reals-power-law$ |
| 54 |
integers-geometric$ integers-poisson$ |
| 55 |
regular-strings$ |
| 56 |
|
| 57 |
;; preconstructed |
| 58 |
fixnums booleans |
| 59 |
int8s uint8s int16s uint16s int32s uint32s int64s uint64s |
| 60 |
|
| 61 |
default-sizer |
| 62 |
samples-from pairs-of tuples-of lists-of vectors-of strings-of |
| 63 |
sequences-of |
| 64 |
permutations-of combinations-of weighted-samples-from |
| 65 |
|
| 66 |
;; Deprecated API |
| 67 |
random-data-seed with-random-data-seed |
| 68 |
)) |
| 69 |
(select-module data.random) |
| 70 |
|
| 71 |
;; API |
| 72 |
;; Use SRFI-27's default-random-source as the default, for the compatibility |
| 73 |
;; to SRFI-194. |
| 74 |
;; In the current implementation, this is <mersenne-twister> instance, and |
| 75 |
;; unless the user explicitly randomize it, it uses a fixed predetermined |
| 76 |
;; seed. It guarantees reproducibility. |
| 77 |
(define random-data-random-source |
| 78 |
(make-parameter default-random-source |
| 79 |
(^x (assume (random-source? x)) x))) |
| 80 |
|
| 81 |
;; Deprecated API |
| 82 |
;; This is no longer useful, for the construted generators capture the |
| 83 |
;; random source at the time of construction and won't be affected |
| 84 |
;; by the changes of random-data-random-source afterwards. |
| 85 |
(define random-data-seed |
| 86 |
(getter-with-setter |
| 87 |
(^[] (let1 rs (random-data-random-source) |
| 88 |
(if (is-a? rs <mersenne-twister>) |
| 89 |
(mt-random-get-seed rs) |
| 90 |
(undefined)))) |
| 91 |
(^[seed] (random-data-random-source |
| 92 |
(make <mersenne-twister> :seed seed))))) |
| 93 |
|
| 94 |
;; Deprecated API |
| 95 |
(define (with-random-data-seed seed thunk) |
| 96 |
;; create st here so that reentering thunk retains the state. |
| 97 |
(let1 st (make <mersenne-twister> :seed seed) |
| 98 |
(parameterize ([random-data-random-source st]) |
| 99 |
(thunk)))) |
| 100 |
|
| 101 |
(define (%rand-int n s) (mt-random-integer s n)) |
| 102 |
(define (%rand-real0 s) (mt-random-real0 s)) |
| 103 |
(define (%rand-real s) (mt-random-real s)) |
| 104 |
|
| 105 |
;;; |
| 106 |
;;; Primitive generators |
| 107 |
;;; |
| 108 |
|
| 109 |
;; |
| 110 |
;; Uniform distribution |
| 111 |
;; |
| 112 |
|
| 113 |
;; API. Generate integers uniformly in [start, start+size) |
| 114 |
(define (integers$ size :optional (start 0)) |
| 115 |
(let1 s (random-data-random-source) |
| 116 |
(^[] (+ (%rand-int size s) start)))) |
| 117 |
|
| 118 |
;; API. Generate integers uniformly in [lb ub] |
| 119 |
;; (We avoid 'integer-range', for 'range' API takes exclusive upper bound.) |
| 120 |
(define (integers-between$ lb ub) |
| 121 |
(let ([s (random-data-random-source)] |
| 122 |
[range (- ub lb -1)]) |
| 123 |
(^[] (+ (%rand-int range s) lb)))) |
| 124 |
|
| 125 |
;; API. |
| 126 |
(define (fixnums$) (integers-between$ (least-fixnum) (greatest-fixnum))) |
| 127 |
(define (int8s$) (integers$ 256 -128)) |
| 128 |
(define (uint8s$) (integers$ 256)) |
| 129 |
(define (int16s$) (integers$ 65536 -32768)) |
| 130 |
(define (uint16s$) (integers$ 65536)) |
| 131 |
(define (int32s$) (integers$ (expt 2 32) (- (expt 2 31)))) |
| 132 |
(define (uint32s$) (integers$ (expt 2 32))) |
| 133 |
(define (int64s$) (integers$ (expt 2 64) (- (expt 2 63)))) |
| 134 |
(define (uint64s$) (integers$ (expt 2 64))) |
| 135 |
(define (booleans$) (let1 g (integers$ 2) (cut zero? (g)))) |
| 136 |
|
| 137 |
;; API |
| 138 |
;; Preconstructed generators. They use default random source. |
| 139 |
(define fixnums (fixnums$)) |
| 140 |
(define int8s (int8s$)) |
| 141 |
(define uint8s (uint8s$)) |
| 142 |
(define int16s (int16s$)) |
| 143 |
(define uint16s (uint16s$)) |
| 144 |
(define int32s (int32s$)) |
| 145 |
(define uint32s (uint32s$)) |
| 146 |
(define int64s (int64s$)) |
| 147 |
(define uint64s (uint64s$)) |
| 148 |
(define booleans (booleans$)) |
| 149 |
|
| 150 |
;; API. |
| 151 |
;; The default value of cset is debatable. We play "safe" here, limiting |
| 152 |
;; ascii alphabets and digits, which would satisfy typical use cases without |
| 153 |
;; worrying character encodings too much. |
| 154 |
(define (chars$ :optional (cset #[A-Za-z0-9])) |
| 155 |
;; We map the integer within the total # of chars in CSET into |
| 156 |
;; the delimited ranges of characters in CSET. For example, if CSET |
| 157 |
;; is splitted into a ranges ((48 . 57) (65 . 90) (97 . 122)), |
| 158 |
;; the table has the following mappings: |
| 159 |
;; 0 -> 48 (for range 48-57) |
| 160 |
;; 10 -> (- 65 10) (for range 65-90) |
| 161 |
;; 36 -> (- 97 36) (for range 97-122) |
| 162 |
;; We generate a random integer in [0, 61], that is, the size same as |
| 163 |
;; the # of chars in the CSET, then use tree-map-floor to find where it |
| 164 |
;; belongs; that gives us an offset to add to the sample number to get |
| 165 |
;; the char code. |
| 166 |
;; |
| 167 |
;; If CSET has only one range, however, we use simpler sampling |
| 168 |
;; for optimization. |
| 169 |
(let ([ranges ((with-module gauche.internal %char-set-ranges) cset)] |
| 170 |
[s (random-data-random-source)]) |
| 171 |
(if (null? (cdr ranges)) |
| 172 |
;; simple case |
| 173 |
(let* ([lb (caar ranges)] |
| 174 |
[ub (cdar ranges)] |
| 175 |
[size (- (+ ub 1) lb)]) |
| 176 |
(^[] (integer->char (+ (%rand-int size s) lb)))) |
| 177 |
;; general case |
| 178 |
(let* ([tab (make-tree-map)] |
| 179 |
[total (do ([ranges ranges (cdr ranges)] |
| 180 |
[cumu 0 (+ cumu (- (+ (cdar ranges) 1) (caar ranges)))]) |
| 181 |
[(null? ranges) cumu] |
| 182 |
(tree-map-put! tab cumu (- (caar ranges) cumu)))]) |
| 183 |
(^[] (let1 p (%rand-int total s) |
| 184 |
(receive (_ off) (tree-map-floor tab p) |
| 185 |
(integer->char (+ p off))))))))) |
| 186 |
|
| 187 |
;; API. Choose one of the elements from collection randomly. |
| 188 |
;; NB: Not to be confused with samples-from below. |
| 189 |
(define (samples$ coll) |
| 190 |
(let* ([vs (coerce-to <vector> coll)] |
| 191 |
[index-gen (integers$ (vector-length vs))]) |
| 192 |
(^[] (vector-ref vs (index-gen))))) |
| 193 |
|
| 194 |
;; API. Extra clamp ensures fp errors won't cause out-of-range value. |
| 195 |
;; NB: We clamp instead of rejecting the out-of-range value---since such |
| 196 |
;; value can only be produced on the FP values on the edge, and we should |
| 197 |
;; regard it inappropriate rounding (for our purpose). If we reject them, |
| 198 |
;; it will skew the distribution. |
| 199 |
(define (reals$ :optional (size 1.0) (start 0.0)) |
| 200 |
(let ([ub (+ size start)] |
| 201 |
[s (random-data-random-source)]) |
| 202 |
(^[] (clamp (+ start (* size (%rand-real0 s))) start ub)))) |
| 203 |
(define (reals-between$ lb ub) |
| 204 |
(assume (<= lb ub)) |
| 205 |
(let1 s (random-data-random-source) |
| 206 |
;; lb + t*(ub-lb) = (1-t)*lb + t*ub |
| 207 |
;; The first way may overflow when lb << ub, and suffer precision |
| 208 |
;; loss if |lb| << |ub|. |
| 209 |
(^[] (let1 t (%rand-real0 s) |
| 210 |
(+ (* (- 1.0 t) lb) (* t ub)))))) |
| 211 |
|
| 212 |
;; API. Uniformly sample from all possible finite flonums. |
| 213 |
;; The distribution is not uniform in mathematical sense, since flonums |
| 214 |
;; are denser when it's closer to zero. |
| 215 |
;; The imlementation assumes IEEE double. |
| 216 |
;; NB: We generate zeros with non-zero exponents, but they are coerced |
| 217 |
;; to the canonical zeros internally. That makes zeros appear x2000 likely |
| 218 |
;; than other numbers. Whether it is an issue or not depends on the |
| 219 |
;; application; we leave it as it is for now. |
| 220 |
(define (finite-flonums$) |
| 221 |
(let ([expgen (integers-between$ -1074 971)] |
| 222 |
[sgngen (samples$ '#(1 -1))] |
| 223 |
[mntgen (integers$ (real-expt 2 52))]) |
| 224 |
(^[] |
| 225 |
(let ([exp (expgen)] |
| 226 |
[mantissa (mntgen)] |
| 227 |
[sign (sgngen)]) |
| 228 |
(if (or (= -1074 exp) (zero? mantissa)) |
| 229 |
(encode-float (vector mantissa exp sign)) ;denormalized or zero |
| 230 |
(encode-float (vector (+ (real-expt 2 52) mantissa) exp sign))))))) |
| 231 |
|
| 232 |
;; rational |
| 233 |
|
| 234 |
(define (complexes-rectangular$ re-lb re-ub im-lb im-ub) |
| 235 |
(assume (<= re-lb re-ub)) |
| 236 |
(assume (<= im-lb im-ub)) |
| 237 |
(let ([rgen (reals-between$ re-lb re-ub)] |
| 238 |
[igen (reals-between$ im-lb im-ub)]) |
| 239 |
(^[] (make-rectangular (rgen) (igen))))) |
| 240 |
|
| 241 |
(define complexes-polar$ |
| 242 |
(case-lambda |
| 243 |
[(mag-lb mag-ub) |
| 244 |
(complexes-polar$ 0 mag-lb mag-ub 0 (* 2 pi))] |
| 245 |
[(origin mag-lb mag-ub) |
| 246 |
(complexes-polar$ origin mag-lb mag-ub 0 (* 2 pi))] |
| 247 |
[(mag-lb mag-ub ang-lb ang-ub) |
| 248 |
(complexes-polar$ 0 mag-lb mag-ub ang-lb ang-ub)] |
| 249 |
[(origin mag-lb mag-ub ang-lb ang-ub) |
| 250 |
(assume (<= mag-lb mag-ub)) |
| 251 |
(assume (<= ang-lb ang-ub)) |
| 252 |
(let* ([b (square mag-lb)] |
| 253 |
[m (- (square mag-ub) b)] |
| 254 |
[maggen (reals$ m b)] |
| 255 |
[anggen (reals-between$ ang-lb ang-ub)]) |
| 256 |
(^[] (+ origin (make-polar (sqrt (maggen)) (anggen)))))])) |
| 257 |
|
| 258 |
;; |
| 259 |
;; Nonuniform distributions |
| 260 |
;; |
| 261 |
|
| 262 |
;; Normal distribution (continuous - generates real numbers) |
| 263 |
;; Box-Muller algorithm |
| 264 |
;; NB: We tested Ziggurat method, too (see git repo for the code), |
| 265 |
;; only to find out Box-Muller is faster about 12% - presumably |
| 266 |
;; the overhead of each ops is larger in Gauche than C/C++, and |
| 267 |
;; so the difference of cost of log or sin from the primitive |
| 268 |
;; addition/multiplication are negligible. |
| 269 |
(define (reals-normal$ :optional (mean 0) (deviation 1)) |
| 270 |
(let1 s (random-data-random-source) |
| 271 |
(^[] (let ([r (real-sqrt (* -2 (real-ln (%rand-real s))))] |
| 272 |
[theta (* 2pi (%rand-real s))]) |
| 273 |
(+ mean (* deviation r (real-sin theta))))))) |
| 274 |
|
| 275 |
#| |
| 276 |
Simple test of gaussian sampling: Generate some data with this: |
| 277 |
|
| 278 |
(with-output-to-file "tmp" |
| 279 |
(^[] (let1 g (normal$ 2 3) (dotimes [i 1000000] (print (g)))))) |
| 280 |
|
| 281 |
Then plot with gnuplot: |
| 282 |
|
| 283 |
binwidth=0.025 |
| 284 |
bin(x,width)=width*floor(x/width) |
| 285 |
plot 'tmp' using (bin($1,binwidth)):(1.0) smooth freq with boxes |
| 286 |
|# |
| 287 |
|
| 288 |
;; Exponential distribution - continuous |
| 289 |
(define (reals-exponential$ m) |
| 290 |
(let1 s (random-data-random-source) |
| 291 |
(^[] (- (* m (log (%rand-real s))))))) |
| 292 |
|
| 293 |
;; Power-law distribution |
| 294 |
;; p(x) = (α-1)/xmin (x/xmin)^{-α} x >= xmin, α > 1 |
| 295 |
;; We use method described in Appendix D of |
| 296 |
;; Aaron Clauset, Cosma Rohilla Shalizi, M.E.J.Newman, Power-Law Distributions |
| 297 |
;; in Empirical Data, SIAM Review, 51(4) pp.661--703, Dec. 2009. |
| 298 |
;; Preprint https://arxiv.org/abs/0706.1062 |
| 299 |
(define (reals-power-law$ xmin power) |
| 300 |
(assume (positive? xmin)) |
| 301 |
(assume (> power 1)) |
| 302 |
(let ([s (random-data-random-source)] |
| 303 |
[exponent (- (/ (- power 1)))]) |
| 304 |
(^[] (* xmin (expt (- 1 (%rand-real s)) exponent))))) |
| 305 |
|
| 306 |
|
| 307 |
;; Draw from geometric distribution, with success probability p. |
| 308 |
;; Mean is 1/p, variance is (1-p)/p^2 |
| 309 |
(define (integers-geometric$ p) |
| 310 |
(let ([c (/ (log (- 1.0 p)))] |
| 311 |
[s (random-data-random-source)]) |
| 312 |
(^[] (ceiling->exact (* c (log (%rand-real s))))))) |
| 313 |
|
| 314 |
;; Draw from poisson distribution with mean L, variance L. |
| 315 |
;; For small L, we use Knuth's method. For larger L, we use rejection |
| 316 |
;; method by Atkinson, The Computer Generation of Poisson Random Variables, |
| 317 |
;; J. of the Royal Statistical Society Series C (Applied Statistics), 28(1), |
| 318 |
;; pp29-35, 1979. The code here is a port by John D Cook's C++ implementation |
| 319 |
;; (http://www.johndcook.com/stand_alone_code.html ) |
| 320 |
(define (integers-poisson$ L) |
| 321 |
(define s (random-data-random-source)) |
| 322 |
(if (< L 36) |
| 323 |
(^[] (do ([exp-L (exp (- L))] |
| 324 |
[k 0 (+ k 1)] |
| 325 |
[p 1.0 (* p (%rand-real s))]) |
| 326 |
[(<= p exp-L) (- k 1)])) |
| 327 |
(let* ([c (- 0.767 (/ 3.36 L))] |
| 328 |
[beta (/ pi (sqrt (* 3 L)))] |
| 329 |
[alpha (* beta L)] |
| 330 |
[k (- (log c) L (log beta))]) |
| 331 |
(rec (loop) |
| 332 |
(let* ([u (%rand-real s)] |
| 333 |
[x (/ (- alpha (log (/ (- 1.0 u) u))) beta)] |
| 334 |
[n (floor->exact (+ x 0.5))]) |
| 335 |
(if (< n 0) |
| 336 |
(loop) |
| 337 |
(let* ([v (%rand-real s)] |
| 338 |
[y (- alpha (* beta x))] |
| 339 |
[t (+ 1.0 (exp y))] |
| 340 |
[lhs (+ y (log (/ v (* t t))))] |
| 341 |
[rhs (+ k (* n (log L)) (- (lgamma (+ n 1))))]) |
| 342 |
(if (<= lhs rhs) |
| 343 |
n |
| 344 |
(loop))))))))) |
| 345 |
|
| 346 |
#| |
| 347 |
;; This generates histograms of samples |
| 348 |
;; e.g. (gen-hist 1000 (poisson$ 5) (poisson$ 10) (poisson$ 20) (poisson$ 50)) |
| 349 |
(define (gen-hist count . thunks) |
| 350 |
(let ([bins (map (^_ (make-hash-table 'eqv?)) thunks)] |
| 351 |
[maxkey 0]) |
| 352 |
(dotimes [n count] |
| 353 |
(do-ec (:parallel (: thunk thunks) |
| 354 |
(: bin bins)) |
| 355 |
(let1 key (thunk) |
| 356 |
(when (> key maxkey) (set! maxkey key)) |
| 357 |
(hash-table-update! bin key (cut + <> 1) 0)))) |
| 358 |
(dotimes [n (+ maxkey 1)] |
| 359 |
(print |
| 360 |
(string-join (cons (x->string n) |
| 361 |
(map (^[bin] (x->string (hash-table-get bin n 0))) |
| 362 |
bins)) |
| 363 |
" "))))) |
| 364 |
|# |
| 365 |
|
| 366 |
;; API. |
| 367 |
;; Generate strings that is accepted with a regular expression regex |
| 368 |
;; |
| 369 |
;; We construct NFA from regex AST. Each node is a closure that emits |
| 370 |
;; character(s), and optionally calls other node. |
| 371 |
|
| 372 |
(define (regular-strings$ regex) |
| 373 |
(assume-type regex <regexp>) |
| 374 |
(let1 nfa (%regex->nfa (regexp-ast regex)) |
| 375 |
(^[] (with-output-to-string (cut nfa #f))))) |
| 376 |
|
| 377 |
(define (%regex->nfa ast) |
| 378 |
(define s (random-data-random-source)) |
| 379 |
(define (%emit c case-fold) |
| 380 |
(let1 cc (if (and case-fold (zero? (%rand-int 2 s))) |
| 381 |
(cond [(char-lower-case? c) (char-upcase c)] |
| 382 |
[(char-upper-case? c) (char-downcase c)] |
| 383 |
[else c]) |
| 384 |
c) |
| 385 |
(display cc)) |
| 386 |
#t) |
| 387 |
(define (rec a) |
| 388 |
(match a |
| 389 |
[(? char?) (cut %emit a <>)] |
| 390 |
[(? char-set?) (let1 g (chars$ a) (cut %emit (g) <>))] |
| 391 |
['any (let1 g (chars$ char-set:full) (cut %emit (g) <>))] |
| 392 |
[(or 'bol 'wb 'nwb) (^[case-fold] #t)] |
| 393 |
['eol (^[case-fold] #f)] |
| 394 |
[('seq . as) (let1 nodes (map rec as) |
| 395 |
(^[case-fold] (every (cut <> case-fold) nodes)))] |
| 396 |
[('seq-uncase . as) (let1 nodes (map rec as) |
| 397 |
(^_ (every (cut <> #t) nodes)))] |
| 398 |
[('seq-case . as) (let1 nodes (map rec as) |
| 399 |
(^_ (every (cut <> #f) nodes)))] |
| 400 |
[('alt . as) (let1 choice-gen (samples$ (map rec as)) |
| 401 |
(^[case-fold] ((choice-gen) case-fold)))] |
| 402 |
[((or 'rep 'rep-min 'rep-while) m n . as) |
| 403 |
(let1 nodes (map rec as) |
| 404 |
(^[case-fold] |
| 405 |
(let loop ([k 1]) |
| 406 |
(and (every (cut <> case-fold) nodes) |
| 407 |
(cond [(< k m) (loop (+ k 1))] |
| 408 |
[(or (not n) (< k n)) |
| 409 |
(if (zero? (%rand-int 2 s)) |
| 410 |
(loop (+ k 1)) |
| 411 |
#t)] |
| 412 |
[else #t])))))] |
| 413 |
[('comp . cs) (let1 g (chars$ (char-set-complement cs)) |
| 414 |
(cut %emit (g) <>))] |
| 415 |
[('cpat _ _ _) |
| 416 |
(error "Conditional regexp can't be used (yet) to generate strings:" |
| 417 |
(regexp-unparse ast))] |
| 418 |
[('once . as) (let1 nodes (map rec as) |
| 419 |
(^[case-fold] (every (cut <> case-fold) nodes)))] |
| 420 |
[((or 'assert 'nassert) . _) |
| 421 |
(error "Lookahead/behind assertion can't be used (yet) to \ |
| 422 |
generate strings:" (regexp-unparse ast))] |
| 423 |
[((? integer? n) _ . as) |
| 424 |
(let1 nodes (map rec as) |
| 425 |
(^[case-fold] (every (cut <> case-fold) nodes)))] |
| 426 |
[_ (error "Unsupported regexp to generate strings:" |
| 427 |
(regexp-unparse ast))])) |
| 428 |
|
| 429 |
(rec ast)) |
| 430 |
|
| 431 |
;;; |
| 432 |
;;; Generator combinators |
| 433 |
;;; |
| 434 |
|
| 435 |
;; API |
| 436 |
(define (samples-from seq-of-gen) |
| 437 |
(let* ([sources (coerce-to <vector> seq-of-gen)] |
| 438 |
[num-sources (vector-length sources)]) |
| 439 |
(case num-sources |
| 440 |
[(0) eof-object] |
| 441 |
[(1) (~ sources 0)] |
| 442 |
[else |
| 443 |
(let ([num-active num-sources] |
| 444 |
[exhausted (make-vector num-sources #f)] |
| 445 |
[s (random-data-random-source)]) |
| 446 |
(^[] |
| 447 |
(let loop () |
| 448 |
(if (zero? num-active) |
| 449 |
(eof-object) |
| 450 |
(let* ([choice (%rand-int num-sources s)] |
| 451 |
[r ((vector-ref sources choice))]) |
| 452 |
(if (eof-object? r) |
| 453 |
(begin |
| 454 |
(unless (vector-ref exhausted choice) |
| 455 |
(vector-set! exhausted choice #t) |
| 456 |
(dec! num-active)) |
| 457 |
(loop)) |
| 458 |
r))))))]))) |
| 459 |
|
| 460 |
;; API |
| 461 |
;; weight&gens :: ((<real> . <generator>) ...) |
| 462 |
(define (weighted-samples-from weight&gens) |
| 463 |
(let* ([tab (make-tree-map)] |
| 464 |
[total (do [(w&g weight&gens (cdr w&g)) |
| 465 |
(cumu 0 (+ cumu (caar w&g)))] |
| 466 |
[(null? w&g) cumu] |
| 467 |
(tree-map-put! tab cumu (cdar w&g)))] |
| 468 |
[s (random-data-random-source)]) |
| 469 |
(^[] (receive (_ gen) (tree-map-floor tab (* (%rand-real0 s) total)) |
| 470 |
(gen))))) |
| 471 |
|
| 472 |
;; API |
| 473 |
(define (pairs-of car-gen cdr-gen) (^[] (cons (car-gen) (cdr-gen)))) |
| 474 |
|
| 475 |
;; API |
| 476 |
(define (tuples-of . gens) (^[] (map (^g (g)) gens))) |
| 477 |
|
| 478 |
;; We accept constant integer or generator |
| 479 |
(define-syntax %with-sizer |
| 480 |
(syntax-rules () |
| 481 |
[(_ sizer . body) |
| 482 |
(let1 sizer (if (integer? sizer) (^[] sizer) sizer) |
| 483 |
. body)])) |
| 484 |
|
| 485 |
(define default-sizer (make-parameter (integers-poisson$ 4))) |
| 486 |
|
| 487 |
;; API |
| 488 |
(define lists-of |
| 489 |
(case-lambda |
| 490 |
[(item-gen) (lists-of (default-sizer) item-gen)] |
| 491 |
[(sizer item-gen) |
| 492 |
(%with-sizer sizer (^[] (list-tabulate (sizer) (^_ (item-gen)))))])) |
| 493 |
|
| 494 |
;; API |
| 495 |
(define vectors-of |
| 496 |
(case-lambda |
| 497 |
[(item-gen) (vectors-of (default-sizer) item-gen)] |
| 498 |
[(sizer item-gen) |
| 499 |
(%with-sizer sizer |
| 500 |
(^[] (let1 len (sizer) |
| 501 |
(rlet1 vec (make-vector len) |
| 502 |
(do-ec (: i len) (vector-set! vec i (item-gen)))))))])) |
| 503 |
|
| 504 |
;; API |
| 505 |
(define strings-of |
| 506 |
(case-lambda |
| 507 |
[() (strings-of (default-sizer) (chars$))] |
| 508 |
[(item-gen) (strings-of (default-sizer) item-gen)] |
| 509 |
[(sizer item-gen) |
| 510 |
(%with-sizer sizer |
| 511 |
(^[] (let1 len (sizer) |
| 512 |
(with-output-to-string |
| 513 |
(^[] (do-ec (: i len) (display (item-gen))))))))])) |
| 514 |
|
| 515 |
;; API |
| 516 |
(define sequences-of |
| 517 |
(case-lambda |
| 518 |
[(class item-gen) (sequences-of class (default-sizer) item-gen)] |
| 519 |
[(class sizer item-gen) |
| 520 |
(%with-sizer sizer |
| 521 |
(^[] (let1 len (sizer) |
| 522 |
(with-builder (class add! get :size len) |
| 523 |
(dotimes [len] (add! (item-gen))) |
| 524 |
(get)))))])) |
| 525 |
|
| 526 |
;; API |
| 527 |
(define (permutations-of seq) |
| 528 |
(let1 s (random-data-random-source) |
| 529 |
(cut shuffle seq s))) |
| 530 |
|
| 531 |
;; API |
| 532 |
(define (combinations-of len seq) |
| 533 |
(let1 indices (list->vector (iota (size-of seq))) |
| 534 |
(^[] (let1 ix (shuffle indices) |
| 535 |
(coerce-to (class-of seq) |
| 536 |
(list-ec (: i len) (ref seq (vector-ref ix i)))))))) |