scalafunctional-programmingmonad-transformersscala-catsscalacheck

Is it possible to write a Distributive Instance for ScalaCheck's Gen type?


I'm trying to write a Monad Transformer instance for ScalaCheck's Gen Type.

That is: a type such as the following, which could be used as a Monad, for provided that the underlying functor F is a Monad.

case class GeneratorT[F[_], A](generator: Gen[F[A]])

object GeneratorT {
  implicit def monadForGeneratorT[F[_]: Monad]: Monad[GeneratorT[F, *]] = new Monad[GeneratorT[F, *]] {
        ...
    }
}

While writing this, I realized that it would be useful if I was able to write a Distributive instance for Gen, because then I'd be able to write flatMap for GeneratorT in the following (somewhat convoluted) way:

    override def flatMap[A, B](ga: GeneratorT[F, A])(fun: A => GeneratorT[F, B]): GeneratorT[F, B] = {
      GeneratorT[F, B](ga.generator.flatMap(fa => fa.map(a => fun(a).generator).distribute(identity).map(_.flatten)))
    }

Instinctively, I feel like I should be able to write a Distributive instance for Gen because Gen is more or less just a function from some configuration, and a seed, onto a value, and functions are distributive.

With that said, I've failed to find an example of anyone doing this, and I'm struggling to write it, because ScalaCheck doesn't expose the internals of Gen.

Is this possible?


Solution

  • I think I understand why this isn't quite possible; it's because Gen supports filtering, and as such, it's possible to end out with a Gen that has no valid values.

    I was thinking of Gen as a function (Properties, Seed) => A, but actually, this should be more like (Properties, Seed) => Option[A].

    The first type distributes, the second doesn't.

    For example an IO[Gen[A]] can't be converted to a Gen[IO[A]] if the Gen might fail, because there's no way to know about the failure without evaluating the IO.

    If you pretend that any Generator will produce a value if evaluated enough times, and you're willing to encounter exceptions when this isn't the case, it's possible to implement Distributive like so:

      implicit val distributiveForGen: Distributive[Gen] = new Distributive[Gen] {
        override def distribute[G[_]: Functor, A, B](ga: G[A])(f: A => Gen[B]): Gen[G[B]] =
          Gen.parameterized(params => ga.map(a => f(a).pureApply(params, params.initialSeed.getOrElse(Seed(0)))))
    
        override def map[A, B](fa: Gen[A])(f: A => B): Gen[B] = fa.map(f)
      }