Invariant super class of Alternative and Decidable

[LukaJCB]

This ties into #1935, but also #2400 and #1932.

I think we could do a lot better with the Alternative hierarchy and the Decidable PR shows, it might need some binary breaking changes.

Ideally we could replicate the *Monoidal hierarchy, but using sum types instead. Then at the end we'd have InvariantSemiringal and have Alternative and Decidable extend from that.

Some code I came up with (names are not final by any means):

// Invariant hierarchy

@typeclass
trait InvariantAddSemigroupal[F[_]] {
  def invariant: Invariant[F]
  def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]
}

@typeclass
trait InvariantAddMonoidal[F[_]] extends InvariantAddSemigroupal[F] {
  def empty[A]: F[A]
}

@typeclass 
trait InvariantSemiringal[F[_]] extends InvariantAddMonoidal[F] with InvariantMonoidal[F]

// Covariant hierarchy

@typeclass
trait SemigroupK[F[_]] extends InvariantAddSemigroupal[F] {
  def combineK[A](x: F[A], y: F[A]): F[A]
  def functor: Functor[F]

  override def invariant: Invariant[F] = functor
  override def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]] =
     combineK(functor.map(fa)(Left(_)), functor.map(fb)(Right(_)))
}

@typeclass
trait MonoidK[F[_]] extends SemigroupK[F] with InvariantAddMonoidal[F]

@typeclass
trait Alternative[F] extends MonoidK[F] with InvariantSemiringal[F]

// Contravariant hierarchy

@typeclass
trait ContravariantAddSemigroupal[F[_]] extends InvariantAddSemigroupal[F] {
  def contravariant: Contravariant[F]

  override def invariant: Invariant[F] = contravariant
}

@typeclass
trait ContravariantAddMonoidal[F[_]] extends ContravariantAddSemigroupal[F] with InvariantAddMonoidal[F] 

@typeclass
trait Decidable[F] extends ContravariantAddMonoidal[F] with InvariantSemiringal[F]

I've also written about this quite a bit in this blog post: https://typelevel.org/blog/2018/11/02/semirings.html

I made a funky looking diagram real quick:

As to why this is useful, I think this offers a really great API for codec combinators when working with e.g. circe, scodec or recently skunk.

[LukaJCB]

/cc @stephen-lazaro

[stephen-lazaro]

Yeah, +1. After I (finally) finish the Decideable PR, I can take a shot at this. Though do we get a genuine MonoidK in the Decideable case? I thought that symmetry didn't quite land.

[LukaJCB]

I think this will have to wait until 2.0, so no need to hurry, we've got tons of time :)

[LukaJCB]

I fixed the hierarchy, not sure what I was thinking there :smile:

[stephen-lazaro]

That diagram has some actually delightful symmetry, sort of reminds me of the Zassenhaus Butterfly Lemma

[LukaJCB]

To keep breakage as small as possible it might be good to either

1. Wait with the Decidable PR until 2.0 Or
2. Add the invariant super classes now and only change the covariant ones (Alternative, MonoidK and SemigroupK) for the 2.0 release.

[catostrophe]

@LukaJCB There's no place for def empty[A]: F[A] in InvariantAddMonoidal, because it's a covariant combinator.

Invariant add monoidal should have nothing:

@typeclass
trait InvariantAddSemigroupal[F[_]] {
  def invariant: Invariant[F]
  def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]
  // associativity law: sum(sum(fa, fb), fc) ≃ sum(fa, sum(fb, fc))
}

@typeclass
trait InvariantAddMonoidal[F[_]] extends InvariantAddSemigroupal[F] {
  def nothing: F[Nothing]
  // identity law: sum(fa, nothing) ≃ sum(nothing, fa) ≃ fa
}

Then, for the covariant monoidals we can derive the following (preserving arrow direction):

def pure[A](a: A): F[A] = functor.map(unit)(_ => a)
// (() -> a) -> (f () -> f a)

def empty[A]: F[A] = functor.map(nothing)(absurd[A])
// (Void -> a) -> (f Void -> f a)

For the contravariant monoidals we can derive (inverting arrows):

def trivial[A]: F[A] = contravariant.contramap(unit)(_ => ())     // or conquer[A]: F[A]
// (a -> ()) -> (f () -> f a)

def lose[A](f: A => Nothing): F[A] = contravariant.contramap[Nothing, A](nothing)(f)
// (a -> Void) -> (f Void -> f a)

So empty can be derived from nothing, provided that we have covariant map. ContravariantAddMonoidal doesn't have such a combinator.

I also think we probably need to adopt naming for Divisible/Decideble and their functions from Data.Functor.Contravariant.Divisible for consistency.

[stephen-lazaro]

That's a good call @catostrophe. Good catch. Is it really worth switching to Divisible though, and changing the method names? We went back and forth on the naming a bit on the first pass, and I felt at the end these weren't really well known enough by their traditional name, which doesn't describe things that well anyway (at least to me). Obviously, when I say "that well known" I'm skewed by my sample, none of my team really knew these type classes existed!

EDIT: Note we're quickly becoming committed to having absurd available for those derivations to work, which means turning off the dead code lint, or at least restricting it.

[stephen-lazaro]

@LukaJCB I incline towards option (2) but I imagine we could get by with either. (2) has the advantage of allowing us to make changes upon 2.0 if things shake out weird.

[catostrophe]

No, I'm not too picky about names. Although we already have quite many discrepancies between cats/scalaz/haskell and it makes user experience harder.

[stephen-lazaro]

@catostrophe Fair point. Worth thinking about how much divergence is acceptable before it's a problem...

[LukaJCB]

@catostrophe Everything you're saying makes absolute sense to me, thanks a ton!

Though I think we should discuss the issue of renaming existing type classes in a different issue, otherwise this could get out of hand quickly :)

[LukaJCB]

Of course with Nothing come some very annoying problems, type inference regularly breaks when the signature contains Nothing somewhere and of course we run into the dead code issue as well.

I wonder if we can avoid Nothing somehow.

[catostrophe]

Maybe INothing from fs2?

[catostrophe]

Or Void from scalaz-zio

[LukaJCB]

I added a WIP for the missing type classes (sans Decidable) here: https://github.com/typelevel/cats/pull/2632

[catostrophe]

I just realized we have pure in InvariantMonoidal which is wrong and doesn't make sense (see my https://github.com/typelevel/cats/issues/2620#issuecomment-440459517 above)

[catostrophe]

Should be removed in 2.0

[catostrophe]

I also have some arguments against the Sum suffix in the newly added typeclasses and the sum function.

It might be misleading as in the wrong analogy we've discussed recently with @LukaJCB in gitter. For type Pred[A] = A => Boolean one can think that if InvariantMonoidal provides const(true) as unit and && as product, then InvariantAddMonoidal should provide const(false) and || correspondingly - which is wrong, and && and || shoud actually be expressed as different InvariantMonoidal instances with the aid of newtypes, e.g. with newts Any and All).

InvariantAddMonoidal provides a choice. Think of Option.getOrElse or IO.race semantics. It's not a sum. I'd rather call it choice or merge. A sum type is actually a choice from several subtypes.

[LukaJCB]

@catostrophe do you mean point? I'm not sure I can deduce what's wrong with it. Also I fully agree with your assessment on the two possible InvariantMonoidal instances for Predicate. I do think though that the term sum makes sense as Either is primitive sum type just as Tuple2 is the primitive product type.

[catostrophe]

Yes, I mean point, and I think it doesn't make sense for contravariant monoidal functors. point :: (() -> a) -> (f () -> f a) This is a covariant lift.

What does InvariantMonoidal[Pred[Int]].point(42) mean?

[LukaJCB]

It means the same as unit.contramap[Unit, Int](_ => ()) which is the same as trivial[Int]. Of course the 42 gets discarded, but that's just the nature of implementing imap in terms of either map or contramap it will always ignore one side.

[kailuowang]

I might've missed something but is this not BC breaking on scala 2.12?

[LukaJCB]

I honestly don't know if it is or not, it might be, but I'm not sure. It definitely breaks for 2.11 though.

[travisbrown]

@LukaJCB Do you still want to try to get this into 2.1?

[LukaJCB]

@travisbrown let me figure out if this is binary compatible (I highly doubt it is)

[LukaJCB]

Turns out, this might be binary compatible after all!

[rossabaker]

I may have a use case both for this and a free construction of it! I am experimenting with an HttpCodec in http4s based on FreeInvariantMonoidal. HttpVersion looks like:

(
  stringLiteral("HTTP/"),
  digit.imap(_ - '0')(i => (i + '0').toChar),
  charLiteral('.'),
  digit.imap(_ - '0')(i => (i + '0').toChar),
).imapN((_, major, _, minor) => new HttpVersion(major, minor))(httpVersion =>
  ((), httpVersion.major, (), httpVersion.minor)
)

The free construction can be foldMapped to cats.parse.Parser0 for decoding and the detestable org.http4s.util.Renderer for encoding. Performance is fine, because the interpretation to the "real" decoder and encoder happen once. One can imagine other interpreters that go straight to binary, use pooled ByteBuffers in IO, etc. The free codec closely reflects the HTTP spec, and backends with different needs can compile from that.

... but there are also sum types, so I'm about to hit a wall. I've been studying Haskell's Free Alternative and Free Decidable. I think what I need is a Free Invariant Semiringal?!