Kotest: Arb flatmap with A -> Arb<B> transformation type

[myuwono]

Which version of Kotest are you using

Kotest Version: 4.1.3

The provided flatMap type signature of fun <A, B> Arb<A>.flatMap(fn: A -> List<B>): Arb<B> is not exactly very pleasant to use currently. I've been using another flatMap with this signature fun <A, B> Arb<A>.flatMap(fn: (A) -> Arb<B>): Arb<B> in one of our kotlin projects internally. So far it seems to work nicely and doesn't seem to suffer from the sequence.flatMap issues described in https://github.com/kotest/kotest/issues/1500 (if i understand the problem correctly).

Here's my current implementation

import io.kotest.property.Arb
import io.kotest.property.RandomSource
import io.kotest.property.Sample
import io.kotest.property.arbitrary.next

fun <A, B> Arb<A>.flatMap(fn: (A) -> Arb<B>): Arb<B> = object : Arb<B>() {
    override fun edgecases(): List<B> = [email protected]().flatMap { fn(it).edgecases() }
    override fun values(rs: RandomSource): Sequence<Sample<B>> =
        [email protected](rs).zip(generateSequence { rs.random.nextLong() }) { sample, nextLong ->
            Sample(fn(sample.value).next(RandomSource.seeded(nextLong)))
        }
}

@sksamuel what do you think? I'm keen to contribute this to the library if this implementation makes sense to you?

[myuwono]

Thanks @sksamuel

By using .next() inside the implementation this really boils down to a signature like Arb..flatMap(f: A -> B) since you are pulling a single value from the arb returned by the function., which is invoked every time.

I was leveraging the initial random seed passed inside of the parent arb for getting a sequence of long values, and then sort of Arb.bind-ing them together. I believe it's equivalent to Arb.bind(arbA, Arb.long()) { a, nextLong -> f(a).next(RandomSeed.seeded(nextLong)) }. In a sense the experiment is repeatable given a random seed, with uniform sampling of both a and long. Since we can recover a single of b = f(a).single(long) for each long, the flatMap yields something like so:

Sequence<A>    : a0,               a1,               a2
Sequence<Long> : l0,               l1,               l2
Sequence<B>    : f(a0).single(l0), f(a1).single(l1), f(a2).single(l2) // this is basically Arb.bind(a, long) { f(a).single(long) }

Yes it would probably work for most arbs, but not for things like Arb.distinct() where each invoking fn() each time would throw away memory of previous values.

Yeah given that the behaviour is more like a derivative, i don't know how to make it work with distinct. Interestingly I don't think distinct would work for Arb.bind either. We're not currently using Arb.distinct() in our tests, so we haven't hit that wall yet.

Would you have any other suggestions? i believe i've seen the flatMap function in scalacheck as well, I wonder how that library does it? Maybe we can borrow some inspirations to further better kotest.

We have some dependent arbs that really need this function.

[sksamuel]

Seems scalacheck returns a single value at a time from their Gens, so then they can do flatMap easily.

[sksamuel]

I wonder if we changed Arb to return a single value (in a backwards compatible way) if it would be better because we could do flatmap like scalacheck does it. How would we do distinct in this case.

[myuwono]

Seems scalacheck returns a single value at a time from their Gens, so then they can do flatMap easily.

Yeah that makes a lot of sense. I needed to use of the single-emission model to make flatMap work.

I wonder if we changed Arb to return a single value (in a backwards compatible way) if it would be better because we could do flatmap like scalacheck does it.

I believe that'll be nice - still thinking on how we can do that while maintaining backward compatibility because we're pretty entrenched in Sequence at the moment. I like the idea because conceptually (nextLong: Long) -> Sample<A> signature would make it more workable to compose. The long values can be translated into a sequence of samples Sequence<Long> -> Sequence<Sample<A>> synchronously / asynchronously which mean parallelization can start as early as sample generation. I'm imagining replacing the property test machinery at proptest, i.e. genA.generate(random).take(iterations).forEach to seed.take(iterations).map { seed -> async { test(genA.forSeed(seed)) } }. These deferreds can then be awaited at the end. This in itself might be a separate discussion.

How would we do distinct in this case.

I'm not entirely sure, I have a few rudimentary ideas in mind that might work but it's more like approximateDistinct() more than true distinct(). One very simplistic idea that came to mind is using a HashSet<T> that kept getting appended to, and then after some iterations we declare convergence when the size of the set doesn't grow anymore or maximum iterations is reached. (maybe a topic for separate discussion)

Back to the problem at hand, at the moment I am still trying to understand if the current Arb.distinct() really is working as intended. It seems for any arbs that uses generateSequence, Arb.distinct() never resolves. Sequence.distinct() internally has a while loop on Iterable.hasNext() which always yields true for infinite sequence. It may be obvious but it just clicked for me on what consequence that entails as our Arb model uses sequence. I guess this explains why Arb.bind(...).distinct() hangs.

fun main() {
    val arbFoo: Arb<String> = arb {
        generateSequence { "foo" }
    }

    val foos: List<String> = arbFoo.distinct().take(10).toList() // hangs
    println(foos)
}

On the topic of flatMap, it does seem to call for the single emission model.

On the topic of distinct, we seem to have opened a pandora's box.

[sksamuel]

Seems Scalacheck doesn't do distinct. One way it could be done is to keep state in the arb.

As for backwards compatibility, we can do some something like:

abstract class Arb<out A> : Gen<A>() {

   /**
    * Edgecase values for this type A.
    */
   abstract fun edgecases(): List<A>

   open fun value(rs: RandomSource): Sample<A> = values(rs).first()

   @Deprecated("implement one value at a time via value(rs)")
   open fun values(rs: RandomSource): Sequence<Sample<A>> = emptySequence()

   companion object
}

The prop test code can change to detect if values is implemented by checking for the empty sequence, and if it is not empty, then it will use that. Otherwise, it would use value.

[myuwono]

fixed via #1688