Scalacheck generators that distribute the size parameter across the generated structure

deepSized.scala

  /** Generator that distributes the available size to two component generators,
    * and then combines the results. Can be used to generate nested structures 
    * where the total number of component/leaf elements is effectively controlled
    * by the size parameter.
    */
  def deepSized[A, B, C](ga: Gen[A], gb: Gen[B])(f: (A, B) => C): Gen[C] =
    for {
      n <- Gen.size
      x <- Gen.choose(0, n)
      a <- Gen.resize(x, ga)
      b <- Gen.resize(n - x, gb)
    } yield f(a, b)

  /** Generator for lists of non-atomic components, where the size parameter is
    * spread across all the generated elements so that the aggregate size of 
    * component/leaf elements is effectively controlled by the size parameter.
    */
  def deepSizedListOf[A](g: Gen[A]): Gen[List[A]] =
    Gen.size.flatMap { n => 
      if (n < 1) Gen.const(Nil)
      else 
        for {
          l <- Gen.choose(0, n)
          r = n - l - 1  // NB: the cons costs one unit of size
          h <- Gen.resize(l, g)
          t <- if (r > 0) Gen.resize(r, deepSizedListOf(g)) else Gen.const(Nil)
        } yield (h :: t)
    }

  /** Generator for lists of non-atomic components, where the size parameter is
    * spread across all the generated elements so that the aggregate size of 
    * component/leaf elements is effectively controlled by the size parameter.
    * No element is ever generated with a size parameter of less than 1.
    */
  def deepSizedListOfNonEmpty[A](g: Gen[A]): Gen[List[A]] =
    Gen.size.flatMap { n => 
      if (n < 1) Gen.const(Nil)
      else if (n < 3) g.map(_ :: Nil)
      else 
        for {
          l <- Gen.choose(1, n)    // NB: always at least one on each side
          r = n - l - 1            // NB: the cons costs one unit of size
          h <- Gen.resize(l, g)
          t <- if (r > 0) Gen.resize(r, deepSizedListOfNonEmpty(g)) else Gen.const(Nil)
        } yield (h :: t)
    }

  def deepSizedNonEmptyListOf[A](g: Gen[A]): Gen[List[A]] =
    deepSized(g, deepSizedListOf(g))(_ :: _)

Note: only a couple of these (deepSized, deepSizedListOfNonEmpty) have been tested much. This was tricky to get right because generators do not always react well to a modified size parameter. For example, Gen.nonEmptyListOf fails if size is 0; hence the extra effort to avoid that case.