Add Divisible and Decideable (contravariant Applicative and co.)

[adelbertc]

https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

Example use case: divide can be seen as a way of deriving behavior by splitting a "larger" type in two

[iravid]

Yes please! Very useful for encoders

[LukaJCB]

Can you expand a bit on the example use case? I'm not really seeing its usefulness right now

[iravid]

Divisible is to Applicative as Contravariant is to Functor.

Let's say that we have an encoder trait:

trait Encoder[T] {
  def encode(t: T): String
}

Encoder has a contravariant functor as it is isomorphic to ? => String.

Given this definition of divisible:

trait Divisible[F[_]] extends Contravariant[F[_]] {
  def contramap2[A, B, C](fa: F[A], fb: F[B])(f: C => (A, B): F[C]
}

I could derive an encoder given two other encoders:

case class Record(i: Int, s: String)
val recEnc: Encoder[Record] = Divisible[Record].contramap2(Encoder[Int], Encoder[String])((rec: Record) => (rec.i, rec.s))

[LukaJCB]

Thanks @iravid, that indeed seems like a useful addition. However, I'm not sure that we'd have a lot of instances. The only one I can come up with right now would be Show and Order. I'm not really sure these are common enough to warrant adding them to core.

Maybe we could add them in some other module? WDYT?

[iravid]

I wouldn't mind that, as long as they're available :-)

[adelbertc]

Looking at https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html we can define instances for Const, the usual transformer "induction"/"back chaining", Nested, Tuple2K

[stephen-lazaro]

Would anyone object if I were to try my hand at this? I'd be happy to give it a shot. I can always open it against cats-core for now and then move it over to cats-more if that's the direction folks go.

[kailuowang]

This one is more likely to goto cats.more.

[LukaJCB]

This can be closed now after #2034

[LukaJCB]

Actually I closed to early as we do have an analogue to Divisible, but not to Decidable, so I'll reopen this :)

[LukaJCB]

To be honest, it'd be pretty cool to see something like this in Cats:

@typeclass trait Decidable[F[_]] extends ContravariantMonoidal[F] with MonoidK[F] {

  def decide[A, B, C](fa: F[A], fb: F[B])(f: C => Either[A, B]): F[C]

  override def combineK[A](x: F[A], y: F[A]): F[A] =
    decide[A, A, A](x, y)(Right(_))
}

[stephen-lazaro]

I am willing to add. I kind of meant to but forgot tbh

…

On Tue, Oct 30, 2018, 03:55 Luka Jacobowitz ***@***.***> wrote: To be honest, it'd be pretty cool to see something like this in Cats: @typeclass trait Decidable[F[_]] extends ContravariantMonoidal[F] with MonoidK[F] { def decide[A, B, C](fa: F[A], fb: F[B])(f: C => Either[A, B]): F[C] override def combineK[A](x: F[A], y: F[A]): F[A] = decide[A, A, A](x, y)(Right(_)) } — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1935 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHdT-bMLA0rJ3M6_ChYQVg4v2Lw8dRQUks5uqDANgaJpZM4PlNfF> .

[LukaJCB]

Please feel free to go right ahead :)

[stephen-lazaro]

@LukaJCB If I wanted to add a dependency on typelevel/algebra would that be acceptable? As far as I can tell, it doesn't exist currently. It would be useful to articulate Semiring / Ring constraints in some cases

[LukaJCB]

I don't think that's in scope right now, there some talks on merging it into the cats repo or maybe even the cats-kernel module, so I propose adding Decidable now and then adding instances using Semiring constraints later :)

[stephen-lazaro]

Yeah, fair. Makes sense, I'll leave those instances out for now. I'll opt for more specific instances for now and leave a note, so we can at least have things like A => Boolean.

[kailuowang]

Is there an issue for merging algebra into cats?

[stephen-lazaro]

I'm happy to do that if that's something we want, after I finish adding this.

[LukaJCB]

@kailuowang the discussion's mostly been going on in #2041 and typelevel/algebra#218 :)

[LukaJCB]

Decidable might be more tricky to add than I thought a day ago. I don't think we can derive combineK for contravariant and invariant structures, so that means there's no way to extend from SemigroupK :(
Maybe in the future we could add an invariant parent for SemigroupK that could also be a superclass for Decidable.
Possibly someone else has other ideas :)

[stephen-lazaro]

Hmmm, right. I think for now I might drop the SemigroupK dependency in favor of optimizing for the sum and decide operations.
I imagine that means we can't really add it at a later date, but oh well.