Add `Decidable`

[stephen-lazaro]

Resolves https://github.com/typelevel/cats/issues/1935 and https://github.com/typelevel/cats/issues/2604.

Seeing an issue with binary compatibility I'm not sure how to resolve correctly. Maybe someone can help me out? I'm probably misunderstanding the intended function of the BinCompat traits.

Included a very barebones doc page.

Since the laws are not formalized in ekmett's original, I've done a bit of guesswork / intiuitioneering on what the right laws look like. Open to discussion.

[stephen-lazaro]

Thanks for the feedback @LukaJCB ! It may take me a day or two to incorporate, but good points all.

[stephen-lazaro]

Just an update, due to work I haven't had much time to work on this, but I hope in the coming weekend to hammer out the remaining issues.

[stephen-lazaro]

Finally had time to return to this, I'll be merging and resolving conflicts and incorporating any feedback I missed.

[julienrf]

Why would Decideable be useful only on contravariant structures? I think it is orthogonal to variance. I personally use it with covariant and invariant structures. The minimal interface is:

trait Decideable[F[_]] {
  def choose[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]
}

Semigroupal is another example of type class which is orthogonal to variance. Incidentally, Decideable is dual to Semigroupal.

Edit: Sorry, I didn’t see that there was already a discussion about it in #2620

[kubukoz]

Hey @stephen-lazaro, do you think you'll have a chance to get back to this anytime soon? If not, I would like to take over, this looks really nice.

[matil019]

Should this be named Decidable instead of Decideable (note the e)? I think it should have the same name as Haskell's equivalent to avoid confusion.

[stephen-lazaro]

@kubukoz I can definitely come back to this this weekend, I mostly just got distracted and was under the impression it might not be binary compatible. If I don't get to it, I'll let you know and we can hand it off.

EDIT: Cough guess it'll be this week actually, but I promise I am getting to it!! (7/20)

[stephen-lazaro]

Tests seem to pass for me locally, but I have to give quite a lot of memory and it still hangs, which is odd. Everything else except dotty compilation is a go, OTOH. Believe most feedback has been incorporated.

[armanbilge]

I haven't looked in depth, but from the comments it seems like this PR is in nice shape and just needs to be revived :) let's see if we can land it in 2.9.0.

[stephen-lazaro]

Cool, I merged and updated this a bit - I imagine there are a few things I'll have to fix trailing off of that (not least any MIMA exceptions since I just gave up on merging the build definition, and the repo has changed quite a bit since I first authored this!), but I'll try and keep this polished and in approvable state in the near future.

[armanbilge]

@stephen-lazaro nice, thank you so much for refreshing this! Yes, MiMa exceptions are now moved to mima.sbt, sorry about that. Let me know if I can help with anything!

[stephen-lazaro]

I believe all checks pass and I've managed to get existing feedback - please let me know if I've overlooked anything. This is my last day of vacation - I'll be back on PST starting tomorrow ;)

[armanbilge]

Thanks for all your work on this!!

[stephen-lazaro]

I do find myself missing the validate command. ;)

[armanbilge]

Ah, it's been replaced by prePR :)

[armanbilge]

I see there's some discussion on laws in:

• https://github.com/ekmett/contravariant/issues/53
• https://github.com/scalaz/scalaz/pull/1881

[stephen-lazaro]

Yeah, I'd read that Kmett thread back when opening this - it's true that it's a bit difficult to say what exactly the right choices are. I think we vaguely our choices here largely on the principle of lifting Rig laws when we were doing this a few years ago (since this is sort of a contravariant categorification of a Rig if I'm remembering things well). Luka also suggested some options here IIRC: https://github.com/typelevel/cats/pull/2607#discussion_r232940785

[stephen-lazaro]

It gets pretty difficult to actually run some of the laws even once they are expressed, because generating things with Nothing in their type gets pretty hard, and much worse when the law can be run but there is no view to Prop from IsEq[F[Nothing]]. E.g. this candidate for right absorption (the best I can come up with for what that ought to look like): F.contramap(F.product(fa, F.zero))((n: Nothing) => (n: A, n)) <-> F.zero or this candidate for testing lose: F.lose(f) <-> F.contramap(F.zero)(f) EDIT: I've added the tests anyway, I had to sort of rig the instances but it's hard to imagine what a meaningful instance would be in these cases anyway (e.g. Eq[F[Nothing]]? strange concept).

[stephen-lazaro]

@armanbilge This is probably as complete as it's going to get at this stage - let me know if there are thoughts on it.

[armanbilge]

Ah, great, thanks for the bump and all your work! I will try to take a look this weekend.

[armanbilge]

Does anyone else have thoughts on my latest comments? Specifically https://github.com/typelevel/cats/pull/2607#discussion_r993029098. I am happy to try and push this across the finish line if Stephen is busy atm.

This is phenomenal work, and I'd really like to land it before another 4 years pass 😄

[stephen-lazaro]

Apologies! I have been preoccupied with my wedding. Seeing that there are comments here, I will endeavor to resolve them this weekend. If there is other feedback, I would appreciate having that up front so I can do them all in a few iterations, that said if it takes a few over that I understand - we all have constraints.