Why is my Scalacheck test with a custom Generator failing after discarding many cases, and how do I fix this?

Question

I am a newbie with Scala and I am writing my first Scalacheck suite.

I have a data structure in my program that essentially looks like a (List[Double], List[Double]) which is well-formed only if each element of _1 is strictly greater than the corresponding element of _2.

Since it's slightly more complicated in practice (although for the purpose of this MWE we can pretend there's all there is to it), I've written a custom generator for it.

I then added two trivial tests (including the most trivial of all, 1 == 1) and in both cases the tests fail, with the messageGave up after only XX passed tests. YYY tests were discarded.

Why is it, and how do I fix it?

Attached is my test suite and the output.

---

package com.foo.bar

import org.scalacheck._
import Prop._
import Arbitrary._

object FooSpecification extends Properties("FooIntervals") {

  type FooIntervals = (List[Double], List[Double])

  /* This is supposed to be a tuple of lists s.t. each element of _1
   *  is < the corresponding element of _2
   * 
   *  e.g. (List(1,3,5), List(2,4,6))
   */

  implicit def arbInterval : Arbitrary[FooIntervals] =
    Arbitrary {
      /**
        * Yields a pair (low, high) s.t. low < high
        */
      def GenPair : Gen[(Double, Double)] = for {
        low <- arbitrary[Double]
        high <- arbitrary[Double].suchThat(_ > low)
      } yield (low, high)

      /**
        * Yields (List(x_1,...,x_n), List(y_1,...,y_n))
        * where x_i < y_i forall i and 1 <= n < 20
        */
      for {
        n <- Gen.choose(1,20)
        pairs : List[(Double, Double)] <- Gen.containerOfN[List, (Double, Double)](n, GenPair)
      } yield ((pairs.unzip._1, pairs.unzip._2))
    }

  property("1 == 1") = forAll {
    (b1: FooIntervals)
    =>
    1 == 1
  }

  property("_1.head < _2.head") = forAll {
    (b1: FooIntervals)
    =>
    b1._1.head < b1._2.head
  }
}

---

[info] ! FooIntervals.1 == 1: Gave up after only 32 passed tests. 501 tests were discarded.
[info] ! FooIntervals._1.head < _2.head: Gave up after only 28 passed tests. 501 tests were discarded.
[info] ScalaTest
[info] Run completed in 1 second, 519 milliseconds.
[info] Total number of tests run: 0
[info] Suites: completed 0, aborted 0
[info] Tests: succeeded 0, failed 0, canceled 0, ignored 0, pending 0
[info] No tests were executed.
[error] Failed: Total 1, Failed 1, Errors 0, Passed 0
[error] Failed tests:
[error]     com.foo.bar.FooSpecification

Answer 1

arbitrary[Double].suchThat(_ > low) This is your problem. suchThat will discard all cases where the condition is false. You are taking two random values and discarding all cases where one of those values is greater than the other which will be a lot. You can use retryUntil instead of suchThat which will generate new values until the condition is satisfied instead of discarding values, but this has the downside of potentially taking a long time or even looping forever if the condition is very unlikely (imagine if you got a very high value for low, you might loop for a long time to get a high that is greater than it, or forever if you are unlucky enough to have the maximum possible double value as low.

What would work is Gen.choose(low, Double.MaxValue) which will select a value between low and Double.MaxValue (the biggest possible double).

Using methods like choose or oneOfand others to restrict your generator to select only values you want is usually better than generating any possible arbitrary value and discarding or retrying invalid cases. That should only be done if there are only very few cases that don't fit your criteria compared to the total possibilities, and the valid cases aren't easily defined using those methods.