Inconsistent use of seed.next in Cogen instances

[ceedubs]

The Cogen instances for Option and Either both use seed.next as an argument to perturb when they are delegating through to an underlying Cogen instance. See here.

It seems to me that there is inconsistent behavior here. For example, the Either instance uses seed when calling perturb for Lefts but seed.next when calling perturb for Rights. Also none of the other instances call seed.next when delegating to perturb (including the instance for Try, which is similar to Either).

I'm happy to submit a PR, but I don't think that I understand when seed.next should be called (if at all) in these instances. cc @non @rickynils

[adamgfraser]

@ceedubs I think the call to seed.next in either is necessary. The way to think about it is that a Cogen needs to produce a new seed given an input with the properties that the seed is the same if the inputs are the same and is different if the inputs are different. The issue with removing the call to seed.next on Left is that then Left(0) and Right(0) would generate the same seed even though those two are clearly different. I added a bunch of tests in CogenSpecification to verify these properties for the different Cogen instances and if you remove the call to seed.next in Either the tests fail for exactly this reason.

With regard to Option it does appear that the call could be eliminated. I think the idea may have been to try to distinguish a from Some(a) but as we're only working with values of the same type and are dealing with products and coproducts separately I don't think we need it here. And say you say it isn;t included in Try, which is similar to Option. All the Cogen tests pass if we remove the call to seed.next for Option.

[ceedubs]

@adamgfraser thanks for the explanation; that's really helpful.

I think that it steers me into a different conclusion than the one that you have presented. Given what you've said, it seems to me like the Cogen instance for Option should be able to distinguish between something like None and Some(()) in the case of Option[Unit]. Similarly it seems like Try[Throwable] should be able to distinguish between the exception being in a Failure or Success. To generalize this, it seems to me like a good guide would be to think of Either as the fundamental coproduct and that other sum types should generally behave the same. That is, Cogen[Option[A]] should likely behave the same as Cogen[Either[Unit, A]] and Cogen[Try[A]] should behave the same as Cogen[Either[Throwable, A]]. You can imagine the instances being implemented via contramap on the Cogen[Either[A, B]] instance.

Therefore I'm inclined to think that the Option instance should remain the same, but the Try instance should call seed.next in the Success case (and possibly even just delegate through to the Either instance). What do you think?

[adamgfraser]

@ceedubs I think that makes sense.

In the case of Option I don't think None and Some(()) would return the same result because the folding in the None case would return the seed unchanged whereas folding in the Some case would reseed the seed with a value of 0L. But I think you are definitely right about Try. I guess I was thinking about that as a weird corner case because the whole point of Try is to bottle up exceptions in the Failure case. But it is a very straightforward change to make to the Try instance and makes the code more robust so I would be good with it, though admittedly this is not my code.

[non]

I agree with @ceedubs -- Try needs to be differentiating the Success(_) and Failure(_) cases (e.g. for Try[Throwable] it means that Success(e) and Failure(e) result in different seeds).

I agree the seed.next is a little bit confusing. Another way to think about this is that we need to include 1-bit of extra information to differentiate a disjunction of two things. Calling seed.next on one side is an easy way to do that.

Another way to do it would be to instead do something like this:

implicit def cogenEither[A, B](implicit A: Cogen[A], B: Cogen[B]): Cogen[Either[A, B]] =
  Cogen((seed: Seed, e: Either[A,B]) => e.fold(
    a => A.perturb(seed.reseed(0L), a),
    b => B.perturb(seed.reseed(1L), b)))

For a single disjunction I don't think this is a huge deal, but to support arbitrary coproducts I think using .reseed is a lot clearer than potentially expensive or convoluted use of .next.

@ceedubs Does this all make sense?

[ceedubs]

@non yeah, thanks that makes sense to me. At least conceptually -- I won't claim to understand subtle implications that there might be between calling next and reseed.

Do you think we should go ahead and make this change to Either? And do you think that Option needs to change or not? I'm happy to submit a PR (probably tonight or this weekend).

[non]

So for now I would stick with the strategy of using .next and just fix Cogen[Try].

In the long-run it may make sense to move to using .reseed instead, but I'd rather think about that change a bit more first.