001 package fj.test; 002 003 import static fj.Bottom.error; 004 import fj.Effect; 005 import fj.F; 006 import fj.Function; 007 import static fj.Function.flip; 008 import static fj.Function.curry; 009 import fj.P2; 010 import static fj.P2.__1; 011 import fj.Unit; 012 import fj.F2; 013 import static fj.data.Array.array; 014 import fj.data.List; 015 import static fj.data.List.nil; 016 import static fj.data.List.replicate; 017 import fj.data.Option; 018 import static fj.pre.Monoid.intAdditionMonoid; 019 import static fj.pre.Ord.intOrd; 020 021 import static java.lang.Math.max; 022 import static java.lang.Math.min; 023 024 /** 025 * <p> A generator for values of the type of the given type parameter (<code>A</code>). Generation 026 * of a value accepts a general 'size' argument (integer), a {@link Rand random generator} and 027 * returns an {@link Option optional value} of the type parameter. Several generators are provided, 028 * allowing various forms of composition of generators. </p> <p> A user typically creates an {@link 029 * Arbitrary arbitrary} to return a generator using the 'combinator methods' below. For example, 030 * suppose a <code>class Person</code>: 031 <pre> 032 class Person { 033 final int age; 034 final String name; 035 final boolean male; 036 037 Person(final int age, final String name, final boolean male) { 038 this.age = age; 039 this.name = name; 040 this.male = male; 041 } 042 } 043 </pre> 044 * </p> <p> In a case like this one, a user may create a generator over <code>Person</code> by 045 * invoking the {@link #bind(F)} methods — in this case, {@link #bind(Gen , Gen , F)} the one 046 * that takes two generator arguments}, since the class has one more than two fields (the bind 047 * method is invoked on a generator adding the extra one to the count as they are composed). The 048 * class fields are of types for which there exist generators (on {@link Arbitrary} so those can be 049 * used to compose a generator for <code>Person</code>: </p> 050 <pre> 051 static Arbitrary<Person> personArbitrary() { 052 final Gen<Person> personGenerator = arbInteger.gen.bind(arbString().gen, arbBoolean().gen, 053 // compose the generators 054 {int age => {String name => {boolean male => new Person(age, name, male)}}}; 055 return arbitrary(personGenerator); 056 } 057 </pre> 058 * <p/> 059 * The example above uses Java 7 closure syntax. Here is the same example using objects instead: 060 <pre> 061 static Arbitrary<Person> personArbitrary() { 062 final Gen<Person> personGenerator = arbInteger.gen.bind(arbString.gen, arbBoolean.gen, 063 // compose the generators 064 new F<Integer, F<String, F<Boolean, Person>>>() { 065 public F<String, F<Boolean, Person>> f(final Integer age) { 066 return new F<String, F<Boolean, Person>>() { 067 public F<Boolean, Person> f(final String name) { 068 return new F<Boolean, Person>() { 069 public Person f(final Boolean male) { 070 return new Person(age, name, male); 071 } 072 }; 073 } 074 }; 075 } 076 }); 077 return arbitrary(personGenerator); 078 } 079 </pre> 080 * 081 * @version %build.number%<br> 082 * <ul> 083 * <li>$LastChangedRevision: 286 $</li> 084 * <li>$LastChangedDate: 2009-10-01 23:41:37 +1000 (Thu, 01 Oct 2009) $</li> 085 * <li>$LastChangedBy: tonymorris $</li> 086 * </ul> 087 */ 088 public final class Gen<A> { 089 private final F<Integer, F<Rand, A>> f; 090 091 private Gen(final F<Integer, F<Rand, A>> f) { 092 this.f = f; 093 } 094 095 /** 096 * Applies the given size and random generator to produce a value. 097 * 098 * @param i The size to use to produce the value. 099 * @param r The random generator to use to produce the value.. 100 * @return A generated value. 101 */ 102 public A gen(final int i, final Rand r) { 103 return f.f(i).f(r); 104 } 105 106 /** 107 * Maps the given function across this generator. 108 * 109 * @param f The function to map across this generator. 110 * @return A new generator after applying the mapping function. 111 */ 112 public <B> Gen<B> map(final F<A, B> f) { 113 return new Gen<B>(new F<Integer, F<Rand, B>>() { 114 public F<Rand, B> f(final Integer i) { 115 return new F<Rand, B>() { 116 public B f(final Rand r) { 117 return f.f(gen(i, r)); 118 } 119 }; 120 } 121 }); 122 } 123 124 /** 125 * Returns a generator that produces values that meet the given predicate. 126 * 127 * @param f The predicate to meet for the values produced by the generator. 128 * @return A generator that produces values that meet the given predicate. 129 */ 130 public Gen<A> filter(final F<A, Boolean> f) { 131 return gen(curry(new F2<Integer, Rand, A>() { 132 public A f(final Integer i, final Rand r) { 133 A a; 134 135 do { 136 a = gen(i, r); 137 } while(!f.f(a)); 138 139 return a; 140 } 141 })); 142 } 143 144 /** 145 * Executes a side-effect for each generated result using the given arguments. 146 * 147 * @param i The size to generate the result to apply the side-effect to. 148 * @param r The random generator to generate the result to apply the side-effect to. 149 * @param f The side-effect to execute on the generated value. 150 * @return The unit value. 151 */ 152 public Unit foreach(final Integer i, final Rand r, final F<A, Unit> f) { 153 return f.f(this.f.f(i).f(r)); 154 } 155 156 /** 157 * Executes a side-effect for each generated result using the given arguments. 158 * 159 * @param i The size to generate the result to apply the side-effect to. 160 * @param r The random generator to generate the result to apply the side-effect to. 161 * @param f The side-effect to execute on the generated value. 162 */ 163 public void foreach(final Integer i, final Rand r, final Effect<A> f) { 164 f.e(this.f.f(i).f(r)); 165 } 166 167 /** 168 * Binds the given function across this generator to produce a new generator. 169 * 170 * @param f The function to bind across this generator. 171 * @return A new generator after binding the given function. 172 */ 173 public <B> Gen<B> bind(final F<A, Gen<B>> f) { 174 return new Gen<B>(new F<Integer, F<Rand, B>>() { 175 public F<Rand, B> f(final Integer i) { 176 return new F<Rand, B>() { 177 public B f(final Rand r) { 178 return f.f(gen(i, r)).f.f(i).f(r); 179 } 180 }; 181 } 182 }); 183 } 184 185 /** 186 * Binds the given function across this generator and the given generator to produce a new 187 * generator. 188 * 189 * @param gb The second generator to bind the given function across. 190 * @param f The function to bind across this generator and the given generator. 191 * @return A new generator after binding the given function. 192 */ 193 public <B, C> Gen<C> bind(final Gen<B> gb, final F<A, F<B, C>> f) { 194 return gb.apply(map(f)); 195 } 196 197 /** 198 * Binds the given function across this generator and the given generators to produce a new 199 * generator. 200 * 201 * @param gb The second generator to bind the given function across. 202 * @param gc The third generator to bind the given function across. 203 * @param f The function to bind across this generator and the given generators. 204 * @return A new generator after binding the given function. 205 */ 206 public <B, C, D> Gen<D> bind(final Gen<B> gb, final Gen<C> gc, final F<A, F<B, F<C, D>>> f) { 207 return gc.apply(bind(gb, f)); 208 } 209 210 /** 211 * Binds the given function across this generator and the given generators to produce a new 212 * generator. 213 * 214 * @param gb The second generator to bind the given function across. 215 * @param gc The third generator to bind the given function across. 216 * @param gd The fourth generator to bind the given function across. 217 * @param f The function to bind across this generator and the given generators. 218 * @return A new generator after binding the given function. 219 */ 220 public <B, C, D, E> Gen<E> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final F<A, F<B, F<C, F<D, E>>>> f) { 221 return gd.apply(bind(gb, gc, f)); 222 } 223 224 /** 225 * Binds the given function across this generator and the given generators to produce a new 226 * generator. 227 * 228 * @param gb The second generator to bind the given function across. 229 * @param gc The third generator to bind the given function across. 230 * @param gd The fourth generator to bind the given function across. 231 * @param ge The fifth generator to bind the given function across. 232 * @param f The function to bind across this generator and the given generators. 233 * @return A new generator after binding the given function. 234 */ 235 public <B, C, D, E, F$> Gen<F$> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final F<A, F<B, F<C, F<D, F<E, F$>>>>> f) { 236 return ge.apply(bind(gb, gc, gd, f)); 237 } 238 239 /** 240 * Binds the given function across this generator and the given generators to produce a new 241 * generator. 242 * 243 * @param gb The second generator to bind the given function across. 244 * @param gc The third generator to bind the given function across. 245 * @param gd The fourth generator to bind the given function across. 246 * @param ge The fifth generator to bind the given function across. 247 * @param gf The sixth generator to bind the given function across. 248 * @param f The function to bind across this generator and the given generators. 249 * @return A new generator after binding the given function. 250 */ 251 public <B, C, D, E, F$, G> Gen<G> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final F<A, F<B, F<C, F<D, F<E, F<F$, G>>>>>> f) { 252 return gf.apply(bind(gb, gc, gd, ge, f)); 253 } 254 255 /** 256 * Binds the given function across this generator and the given generators to produce a new 257 * generator. 258 * 259 * @param gb The second generator to bind the given function across. 260 * @param gc The third generator to bind the given function across. 261 * @param gd The fourth generator to bind the given function across. 262 * @param ge The fifth generator to bind the given function across. 263 * @param gf The sixth generator to bind the given function across. 264 * @param gg The seventh generator to bind the given function across. 265 * @param f The function to bind across this generator and the given generators. 266 * @return A new generator after binding the given function. 267 */ 268 public <B, C, D, E, F$, G, H> Gen<H> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final Gen<G> gg, final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, H>>>>>>> f) { 269 return gg.apply(bind(gb, gc, gd, ge, gf, f)); 270 } 271 272 /** 273 * Binds the given function across this generator and the given generators to produce a new 274 * generator. 275 * 276 * @param gb The second generator to bind the given function across. 277 * @param gc The third generator to bind the given function across. 278 * @param gd The fourth generator to bind the given function across. 279 * @param ge The fifth generator to bind the given function across. 280 * @param gf The sixth generator to bind the given function across. 281 * @param gg The seventh generator to bind the given function across. 282 * @param gh The eighth generator to bind the given function across. 283 * @param f The function to bind across this generator and the given generators. 284 * @return A new generator after binding the given function. 285 */ 286 public <B, C, D, E, F$, G, H, I> Gen<I> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final Gen<G> gg, final Gen<H> gh, final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, F<H, I>>>>>>>> f) { 287 return gh.apply(bind(gb, gc, gd, ge, gf, gg, f)); 288 } 289 290 /** 291 * Function application within this generator to produce a new generator. 292 * 293 * @param gf The generator over the function to apply to this generator. 294 * @return A new generator after function application. 295 */ 296 public <B> Gen<B> apply(final Gen<F<A, B>> gf) { 297 return gf.bind(new F<F<A, B>, Gen<B>>() { 298 public Gen<B> f(final F<A, B> f) { 299 return map(new F<A, B>() { 300 public B f(final A a) { 301 return f.f(a); 302 } 303 }); 304 } 305 }); 306 } 307 308 /** 309 * Resizes this generator with the given size. 310 * 311 * @param s The new size of the generator. 312 * @return A new generator that uses the given size. 313 */ 314 public Gen<A> resize(final int s) { 315 return new Gen<A>(new F<Integer, F<Rand, A>>() { 316 public F<Rand, A> f(final Integer i) { 317 return new F<Rand, A>() { 318 public A f(final Rand r) { 319 return f.f(s).f(r); 320 } 321 }; 322 } 323 }); 324 } 325 326 /** 327 * Returns a generator that uses the given function. 328 * 329 * @param f The function to use for this generator. 330 * @return A new generator that uses the given function. 331 */ 332 public static <A> Gen<A> gen(final F<Integer, F<Rand, A>> f) { 333 return new Gen<A>(f); 334 } 335 336 /** 337 * Sequence the given generators through a {@link #bind(F)} operation. 338 * 339 * @param gs The generators to sequence. 340 * @return A generator of lists after sequencing the given generators. 341 */ 342 public static <A> Gen<List<A>> sequence(final List<Gen<A>> gs) { 343 return gs.foldRight(new F<Gen<A>, F<Gen<List<A>>, Gen<List<A>>>>() { 344 public F<Gen<List<A>>, Gen<List<A>>> f(final Gen<A> ga) { 345 return new F<Gen<List<A>>, Gen<List<A>>>() { 346 public Gen<List<A>> f(final Gen<List<A>> gas) { 347 return ga.bind(gas, List.<A>cons()); 348 } 349 }; 350 } 351 }, value(List.<A>nil())); 352 } 353 354 /** 355 * Sequences the given generator the given number of times through a {@link #bind(F)} operation. 356 * 357 * @param n The number of times to sequence the given generator. 358 * @param g The generator sequence. 359 * @return A generator of lists after sequencing the given generator. 360 */ 361 public static <A> Gen<List<A>> sequenceN(final int n, final Gen<A> g) { 362 return sequence(replicate(n, g)); 363 } 364 365 /** 366 * Constructs a generator that can access its construction arguments — size and random 367 * generator. 368 * 369 * @param f The function that constructs the generator with its arguments. 370 * @return A new generator. 371 */ 372 public static <A> Gen<A> parameterised(final F<Integer, F<Rand, Gen<A>>> f) { 373 return new Gen<A>(curry(new F2<Integer, Rand, A>() { 374 public A f(final Integer i, Rand r) { 375 return f.f(i).f(r).gen(i, r); 376 } 377 })); 378 } 379 380 /** 381 * Constructs a generator that can access its size construction arguments. 382 * 383 * @param f The function that constructs the generator with its size argument. 384 * @return A new generator. 385 */ 386 public static <A> Gen<A> sized(final F<Integer, Gen<A>> f) { 387 return parameterised(flip(Function.<Rand, F<Integer, Gen<A>>>constant(f))); 388 } 389 390 /** 391 * Returns a generator that always produces the given value. 392 * 393 * @param a The value to always produce. 394 * @return A generator that always produces the given value. 395 */ 396 public static <A> Gen<A> value(final A a) { 397 return new Gen<A>(new F<Integer, F<Rand, A>>() { 398 public F<Rand, A> f(final Integer i) { 399 return new F<Rand, A>() { 400 public A f(final Rand r) { 401 return a; 402 } 403 }; 404 } 405 }); 406 } 407 408 /** 409 * Returns a generator that produces values between the given range (inclusive). 410 * 411 * @param from The value for the generator to produce values from. 412 * @param to The value for the generator to produce values from. 413 * @return A generator that produces values between the given range (inclusive). 414 */ 415 public static Gen<Integer> choose(final int from, final int to) { 416 final int f = min(from, to); 417 final int t = max(from, to); 418 return parameterised(curry(new F2<Integer, Rand, Gen<Integer>>() { 419 public Gen<Integer> f(final Integer i, final Rand r) { 420 return value(r.choose(f, t)); 421 } 422 })); 423 } 424 425 /** 426 * Returns a generator that produces values between the given range (inclusive). 427 * 428 * @param from The value for the generator to produce values from. 429 * @param to The value for the generator to produce values from. 430 * @return A generator that produces v 431 */ 432 public static Gen<Double> choose(final double from, final double to) { 433 final double f = min(from, to); 434 final double t = max(from, to); 435 return parameterised(new F<Integer, F<Rand, Gen<Double>>>() { 436 public F<Rand, Gen<Double>> f(final Integer i) { 437 return new F<Rand, Gen<Double>>() { 438 public Gen<Double> f(final Rand r) { 439 return value(r.choose(f, t)); 440 } 441 }; 442 } 443 }); 444 } 445 446 /** 447 * Returns a generator that never returns a value. 448 * 449 * @return A generator that never returns a value. 450 */ 451 public static <A> Gen<A> fail() { 452 return new Gen<A>(new F<Integer, F<Rand, A>>() { 453 public F<Rand, A> f(final Integer i) { 454 return new F<Rand, A>() { 455 public A f(final Rand r) { 456 throw error("Failing generator"); 457 } 458 }; 459 } 460 }); 461 } 462 463 /** 464 * Joins the generator of generators through a {@link #bind(F)} operation. 465 * 466 * @param g The generator of generators to join. 467 * @return A new generator after joining the given generator. 468 */ 469 public static <A> Gen<A> join(final Gen<Gen<A>> g) { 470 return g.bind(Function.<Gen<A>>identity()); 471 } 472 473 /** 474 * Returns a generator that uses values from the given frequency and generator pairs. The returned 475 * generator will produce values from the generator in a pair with a higher frequency than a lower 476 * frequency generator. 477 * 478 * @param gs The pairs of frequency and generator from which to return values in the returned 479 * generator. 480 * @return A new generator that uses the given pairs of frequency and generator. 481 */ 482 public static <A> Gen<A> frequency(final List<P2<Integer, Gen<A>>> gs) { 483 final class Pick { 484 <A> Gen<A> pick(final int n, final List<P2<Integer, Gen<A>>> gs) { 485 if(gs.isEmpty()) 486 return fail(); 487 else { 488 final int k = gs.head()._1(); 489 return n <= k ? gs.head()._2() : pick(n - k, gs.tail()); 490 } 491 } 492 } 493 494 final F<P2<Integer, Gen<A>>, Integer> f = __1(); 495 496 return choose(1, intAdditionMonoid.sumLeft(gs.map(f))).bind(new F<Integer, Gen<A>>() { 497 public Gen<A> f(final Integer i) { 498 return new Pick().pick(i, gs); 499 } 500 }); 501 } 502 503 /** 504 * Returns a generator that produces values from the given frequency and value pairs. The returned 505 * generator will produce the value with a higher frequency than a lower one. 506 * 507 * @param as The pairs of frequency and value from which to produce values. 508 * @return A new generator that uses the given pairs of frequency and value. 509 */ 510 public static <A> Gen<A> elemFrequency(final List<P2<Integer, A>> as) { 511 return frequency(as.map(new F<P2<Integer, A>, P2<Integer, Gen<A>>>() { 512 public P2<Integer, Gen<A>> f(final P2<Integer, A> p) { 513 return p.map2(new F<A, Gen<A>>() { 514 public Gen<A> f(final A a) { 515 return value(a); 516 } 517 }); 518 } 519 })); 520 } 521 522 /** 523 * Returns a generator that produces values from the given arguments. 524 * 525 * @param as The values that the returned generator may produce. 526 * @return A generator that produces values from the given arguments. 527 */ 528 public static <A> Gen<A> elements(final A... as) { 529 return array(as).isEmpty() ? Gen.<A>fail() : choose(0, as.length - 1).map(new F<Integer, A>() { 530 public A f(final Integer i) { 531 return as[i]; 532 } 533 }); 534 } 535 536 /** 537 * Returns a generator that produces values from one of the given generators on subsequent 538 * requests. 539 * 540 * @param gs The list of generators to produce a value from. 541 * @return A generator that produces values from one of the given generators on subsequent 542 * requests. 543 */ 544 public static <A> Gen<A> oneOf(final List<Gen<A>> gs) { 545 return gs.isEmpty() ? Gen.<A>fail() : choose(0, gs.length() - 1).bind(new F<Integer, Gen<A>>() { 546 public Gen<A> f(final Integer i) { 547 return gs.index(i); 548 } 549 }); 550 } 551 552 /** 553 * Returns a generator of lists whose values come from the given generator. 554 * 555 * @param g The generator to produce values from for the returned generator. 556 * @param x An adjuster of size to apply to the given generator when producing values. 557 * @return A generator of lists whose values come from the given generator. 558 */ 559 public static <A> Gen<List<A>> listOf(final Gen<A> g, final int x) { 560 return sized(new F<Integer, Gen<List<A>>>() { 561 public Gen<List<A>> f(final Integer size) { 562 return choose(x, size).bind(new F<Integer, Gen<List<A>>>() { 563 public Gen<List<A>> f(final Integer n) { 564 return sequenceN(n, g); 565 } 566 }); 567 } 568 }); 569 } 570 571 /** 572 * Returns a generator of lists whose values come from the given generator. 573 * 574 * @param g The generator to produce values from for the returned generator. 575 * @return A generator of lists whose values come from the given generator. 576 */ 577 public static <A> Gen<List<A>> listOf(final Gen<A> g) { 578 return listOf(g, 0); 579 } 580 581 /** 582 * Returns a generator of lists whose values come from the given generator. 583 * 584 * @param g The generator to produce values from for the returned generator. 585 * @return A generator of lists whose values come from the given generator. 586 */ 587 public static <A> Gen<List<A>> listOf1(final Gen<A> g) { 588 return listOf(g, 1); 589 } 590 591 /** 592 * Returns a generator of lists that picks the given number of elements from the given list. If 593 * the given number is less than zero or greater than the length of the given list, then the 594 * returned generator will never produce a value. 595 * 596 * @param n The number of elements to pick from the given list. 597 * @param as The list from which to pick elements. 598 * @return A generator of lists that picks the given number of elements from the given list. 599 */ 600 public static <A> Gen<List<A>> pick(final int n, final List<A> as) { 601 return n < 0 || n > as.length() ? Gen.<List<A>>fail() : sequenceN(n, choose(0, as.length() - 1)).map(new F<List<Integer>, List<A>>() { 602 public List<A> f(final List<Integer> is) { 603 List<A> r = nil(); 604 605 List<Integer> iis = is.sort(intOrd); 606 List<P2<A, Integer>> aas = as.zipIndex(); 607 608 //noinspection ForLoopWithMissingComponent 609 for(; iis.isNotEmpty() && aas.isNotEmpty(); aas = aas.tail()) 610 if(iis.head().equals(aas.head()._2())) 611 iis = iis.tail(); 612 else 613 r = r.snoc(aas.head()._1()); 614 615 return r; 616 } 617 }); 618 } 619 620 /** 621 * Returns a generator of lists that produces some of the values of the given list. 622 * 623 * @param as The list from which to pick values. 624 * @return A generator of lists that produces some of the values of the given list. 625 */ 626 public static <A> Gen<List<A>> someOf(final List<A> as) { 627 return choose(0, as.length()).bind(new F<Integer, Gen<List<A>>>() { 628 public Gen<List<A>> f(final Integer i) { 629 return pick(i, as); 630 } 631 }); 632 } 633 634 /** 635 * Promotes the given function to a generator for functions. 636 * 637 * @param f The function to promote to a generator of functions. 638 * @return A generator for functions. 639 */ 640 public static <A, B> Gen<F<A, B>> promote(final F<A, Gen<B>> f) { 641 return new Gen<F<A, B>>(new F<Integer, F<Rand, F<A, B>>>() { 642 public F<Rand, F<A, B>> f(final Integer i) { 643 return new F<Rand, F<A, B>>() { 644 public F<A, B> f(final Rand r) { 645 return new F<A, B>() { 646 public B f(final A a) { 647 return f.f(a).f.f(i).f(r); 648 } 649 }; 650 } 651 }; 652 } 653 }); 654 } 655 }