Better accommodate MTL style

[adelbertc]

EDIT Better written post about why the current (at the time of this writing, Oct 9, 2016) type class encoding is insufficient: http://typelevel.org/blog/2016/09/30/subtype-typeclasses.html )

---

One issue with the current approach is if you want to do MTL style programming, you end up having duplication. A short, contrived, example:

trait MonadMagic[F[_]] extends Monad[F] {
  def magic: F[Int]
}

Now I want to define MonadMagic[Option].. but that means I also need to re-implement the Monad flatMap and pure methods, which leads to duplication and makes me uncomfortable.

I suppose it could be solved by putting the Monad[Option] definition in a trait and exposing it for people to mix-in.. but then we'd have to do it for every data type. Which maybe isn't a big deal? But perhaps a deficiency of the current approach.

I suppose you could also do something like

trait MonadMagic[F[_]] {
  def monad: Monad[F]
}

and provide an implicit conversion [F]MonadMagic[F] => Monad[F] but that departs from how we are currently encoding things.

I find some solution to this is important so as to not hinder MTL style programming which I find is an elegant way to encode EDSLs like Free modulo the need to explicitly reify the AST and thus presumably more performant.

[adelbertc]

Related issue, it seems we also currently suffer from ambiguous implicits:

import cats.{MonadReader, MonadState}
import cats.implicits._

def foo[F[_], R, S](implicit R: MonadReader[F, R], S: MonadState[F, S]): F[Boolean] =
  for {
    int  <- S.get
    char <- R.ask
  } yield false

// Exiting paste mode, now interpreting.

<console>:16: error: value flatMap is not a member of type parameter F[S]
           int  <- S.get
                     ^
<console>:17: error: value map is not a member of type parameter F[R]
           char <- R.ask
                     ^

The above doesn't work because both MonadReader and MonadState give a valid Monad[F]. If we remove one of them, it works fine:

import cats.{MonadReader, MonadState}
import cats.implicits._

def foo[F[_], R, S](implicit R: MonadReader[F, R]): F[Boolean] =
  for {
    int  <- R.ask
    char <- R.ask
  } yield false

// Exiting paste mode, now interpreting.

import cats.{MonadReader, MonadState}
import cats.implicits._
foo: [F[_], R, S](implicit R: cats.MonadReader[F,R])F[Boolean]

[johnynek]

we would not need implicit conversion would we? For instance this would work:

trait MonadMagic[F[_]] {
  def monad: Monad[F]
}

object MonadMagic {
  implicit def mmmonad[F[_]](implicit mm: MonadMagic[F]): Monad[F] = mm.monad
}

The ambiguous implicits problem of the second example is a bigger problem if you ask me. That said, I'm pessimistic about solving it. Cats uses extension pretty heavily throughout the design. One alternative could be something like:

trait Functor[F[_]] {
  def map[A, B](f: F[A])(fn: A => B): F[B]
}

trait Applicative[F[_]] {
  def functor: Functor[F]
  def pure[A](a: A): F[A]
}

trait Monad[F[_]] {
  def applicative: Applicative[F]
  def flatMap[A, B](f: F[A])(fn: A => F[B]): F[B]
}

trait LowPriorityApplicative {
  // look up the hierarchy 
  implicit def appFromMonad[F[_]](implicit m: Monad[F]): Applicative[F] = m.applicative 
}

object Applicative extends LowPriorityApplicative {
  ...
}

This is anti-modular because subtypes implicit resolution looks up, while the super types give instances of the subtypes, so they also know of the existence.

That said, it might be just a linear chain, so that it is actually manageable within cats.

But it is a big departure (and speculative in that there may be other issues).

[adelbertc]

I think the approach you sketched out is similar to the approach taken in scato which is also the approach taken in scalaz8.

Completely agree on the ambiguous implicits being more serious, but I do think it needs fixing/looking into. The small example I used is a completely reasonable use case, it just takes abstracting via type classes one step further. Cats already provides MonadReader, MonadWriter, MonadState, and MonadError so expecting someone to use them together is reasonable (and useful!).

[aloiscochard]

Hey @adelbertc,

Yes this is exactly the approach taken initially in scato which serve now as a basis in scalaz8, we are moving forward with it and it seems to works well.

The only thing is that I don't think it's realistic to expect being able to encode the hierarchy in the companion of the type classes, we basically use a big TC module that is part of the root scope.

This way we can fine grain the resolution among all typeclasses in our base module`.

Hope that helps, feel free to ping me if you have any specific question.

Cheers

[adelbertc]

So I randomly tried this:

import cats._
import cats.implicits._

trait MonadMagic[F[_]] { deps: Monad[F] => // self-type instead of extends
  def magic: F[Int]
}

def foo[F[_]](implicit A: MonadMagic[F], B: MonadReader[F, Int]): F[Int] = for {
  a <- A.magic
  b <- B.ask
} yield a + b

and it seems to work? I'm expecting this to fail somewhere else you would want it to work (disregarding the fact that this encoding is different from the encoding for all the other type classes)... leaving here for feedback.

EDIT

So one thing I've noticed is that if you have access (from the outside) to a subclass (e.g. MonadMagic[F]) you don't get access to the superclass methods (e.g. map):

scala> def foo[F[_]](implicit F: MonadMagic[F]): F[Int] = F.map(F.magic)(identity)
<console>:36: error: value map is not a member of MonadMagic[F]
       def foo[F[_]](implicit F: MonadMagic[F]): F[Int] = F.map(F.magic)(identity)
                                                            ^

[aloiscochard]

@adelbertc we did experiment a bit with this, but due to the limitation you are facing we decided to keep this approach only for the template system.

You can find the latest revision of the template system (designed mainly by @jbgi) that should be merged soon in this PR: scalaz/scalaz#1217

For example: https://github.com/jbgi/scalaz/blob/d5f101700c50a7930141f212a6f23bce95e3280c/base/src/main/scala/typeclass/MonadClass.scala

[adelbertc]

I wonder if the following would work for the existing subtype encoding of type classes in Cats (and Scalaz 7):

For MTL type classes (e.g. MonadReader, MonadState, etc.), encode them as (in the example of MonadReader):

trait MonadReader[F[_], R] { self: Monad[F] =>
  ...
}

but don't do the whole Scato encoding, we just stop there. I believe clients can then say things like:

def foo[F[_], R, S](implicit F: Monad[F], R: MonadReader[F, R], S: MonadState[F, S]): F[Boolean] =
  for {
    int  <- S.get
    char <- R.ask
  } yield false

Note that foo now needs to explicitly specify Monad since you can't get syntax through the MTL type classes because Scala. However, the self-type still enforces that whoever implements the type classes needs to also have a Monad and so you can't get weird standalone lawless instances. Law checking then proceeds as usual.

Example of defining instances:

trait Foo

object Foo {
  // Note having to explicitly specify Monad instead of getting it transitively through MTL
  implicit def instance[A, B]: Monad[Foo] with MonadReader[Foo, A] with MonadState[Foo, B] = ...
}

cc @non since I know you didn't like this for MonadRec due to the explosion of instances, but that's to be expected in the MTL case anyways.

BTW I am proposing this as a change to Cats. The one bit that bothers me is it special cases the treatment of type class encoding for MTL - we effectively split the world of type classes into "the fundamental blessed type classes" and "MTL." But a similar ambiguous implicit situation arises in the case of say, [F[_]: Traverse, Applicative] (ambiguous Functor[F]) though perhaps that use case is not very common.

That being said, this change does make (monadic) MTL much nicer to use.

[aloiscochard]

The thing that would personally bother me, is that you can't actually get a Monad out of a, let say MonadReader.

This can be mitigated by introducing a def monad: Monad[F] in the interface and might work in your definition by doing val monad = self.

Hope that helps!

[alexandru]

In Monix we have this package called monix.types in which I compiled a bunch of needed type-classes to support the types exposed in Monix and to allow me to translate them in corresponding Cats and Scalaz type instances, an idea I got from djspiewak/shims.

I recently switched the type-class encoding used to that in Scato / Scalaz 8. I instantly got rid of things like MonadError, Bimonad, MonadPlus and others. It's actually amazing, because I have a mini-Cats in my project for about 60 KB. And I also have an Enumerator[F[_], A] type that I'm working on, with a type-class based design. And this encoding feels really nice.

[adelbertc]

@alexandru Hm I'm not sure I follow - why did switching the encoding allow you to get rid of MonadError? Perhaps I misunderstand but it seems the encoding just lets you specify various constraints that subclass Monad without running into an ambiguous implicits problem.

That being said, that's awesome to hear. I'm a fan of the encoding as well :-)

[alexandru]

@adelbertc what I wanted to say is that if you have ApplicativeError (like Cats has) you no longer need a MonadError to inherit from ApplicativeError with Monad. It's no longer necessary to have combinations of existing operations, you only need new types when you want to express new operations.

[adelbertc]

@alexandru Ah I see - I suppose you would still need something similar to do law checking, but yeah you can just ask for ApplicativeError and Monad. Glad to hear you're finding success with it "in the wild" - I'm wondering what your thoughts are on the proposed solution to get something working for the current subtyping approach? I was thinking something like:

trait MonadReader[F[_], R] { self: Monad[F] =>
  implicit def instance: Monad[F]
}

This solves:

1. Ambiguous implicits since self types don't affect implicit resolution
2. Given a MonadReader[F, *] you can get a Monad[F] via instance. I've marked it as implicit here but it need not be - with implicit in your local scope you can then do import monadReader.instance._ to get the Monad in scope and hence the syntax. Alternatively we can just say users should also require Monad[F] explicitly.

My main concern is we're treating MTL type classes as "special".. but maybe in the interest of getting a usable MTL experience in Scala that's not a huge deal?

[alexandru]

I'll have to think about it, I never tried it with a typed self. On exposing the instances, we could also expose different fields, for each type involved.

trait MonadError[F[_], E] { self: Monad[F] with ApplicativeError[F,E] =>
  def applicativeError: ApplicativeError[F,E] = self
  def monad: Monad[F] = self
}

Btw, I hope ordering of inheritance doesn't matter for those self types, because in Scala A with B isn't the same as B with A, though I don't think it's a problem here.

[aloiscochard]

@alexandru nice to hear you had good use of it :-)

I intuitively feel that the encoding should be used only if the instances which are define with it are coherent. I don't have a counter example, but it does not seems too hard to find one.

For the self type, the hierarchy of scalaz8 is not complex enough to exercise this case, but I would highly surprised if self annotation constraints the order of linearisation, but oh well it's scalac after all ;)

May the force be with you.

[milessabin]

Interestingly the approach @johnynek suggests above (and apparently the one taken in Scalaz 8) is similar to the approach I took in export-hook for what I called "subclass instances".

It's probably not obvious because the boilerplate is hidden behind export-hooks annotation macros.

[alexandru]

You might want to checkout the progress I've been making in my experiment:

• type-classes
• and actual usage

[adelbertc]

@alexandru Looks interesting, is it similar to the approaches outlined above minus the scaffolding that allows you to treat, say, Applicative[F] as Functor[F]? It looks like you're importing implicits on use sites: https://github.com/monixio/monix/blob/wip-streams/monix-eval/shared/src/main/scala/monix/eval/Stream.scala#L102

Would appreciate your feedback on #1379 as I think it's important we discuss what we want to do moving forward. It's also blocking stuff like #1337

[alexandru]

@adelbertc so yes, the only inheritance that happens is to support composition, such that a Monad[F] has an implicit def functor and an implicit def applicative and then I import those in the context when needed, like on that line 102.

It's not perfect, but when abstracting over F[_] in Scala, it comes with the territory - having those imports where needed is much less painful then to specify generic types explicitly in order to keep IntelliJ IDEA green.

[alexandru]

One thing to keep in mind though, my type-class hierarchy is meant only to support the types I'm building, along with conversions for Cats and Scalaz, which means it is much simpler than what Cats is trying to support. Applying this encoding only to types such as MonadFilter makes some sense.

[aaronlevin]

I'm curious what the status is on this? I'm interesting in this and willing to put some effort into finding a solution (though I'm not sure how I can help - everyone seems to have chimed in and there's no clear winner).

In thinking about the MTL syntax problem, it seems like the core of the issue is in MonadOps and FunctorOps et al requiring an implicit Functor or Monad. Here is a potentially disastrous and terrible idea but might be a decent bridge if it works and isn't too much work: perhaps a work-around would be to produce our own quoted DSL that is identical to a for-comprehension but allows us to desugar in the way that's necessary (if this is possible). This is inspired by what quill does. For example, this might look like:

def foo[M[_]](implicit me: MonadError[M, String], mr: MonadReader[M, Int]): M[Boolean] = {
  mtl {
    foo <- mr.ask
    bar <- mr.ask
  } yield False
}

I recognize I might have a fairly naive understanding of the problem. I'd love to get MTL supported in cats in a usable way.

[aaronlevin]

(one way I might be able to help is to do the grunt work of putting together a proposal with the different approaches, their implementations, trade-offs, examples, etc. I just need to sync with whatever the status is and whoever is leading this / interested in leading this)

[adelbertc]

@aaronlevin I outlined the problem in full here.

The current status is bursts of discussion here and there. I had a PR that implemented the above proposal but that's long since rotted in the presence of other Cats activity.

The principled version of me would like to see a general solution to this for all implicits - for instance I've filed an issue with Dotty.

But for the language we're given.. I don't know. Scato solves it, but it's bulky and "untested in the wild" (though I'm fairly confident it would work.. don't know how performant it would be though).

Jury's still out :/

[aaronlevin]

@adelbertc how do you feel about a cats-mtl library outside of cats?

[adelbertc]

I would not be opposed to it - it might also open the doors for us to encode the MTL classes in Scato style instead of via subtyping.

That being said it is probably easier said than done. The Scato encoding has certain implications w.r.t. how users need to import things to get the appropriate conversions in scope. This may confuse users and involve breaking changes for existing users - I believe Circe uses the MTL classes in some places.

[kailuowang]

@edmundnoble, according to this comment, you are working on this, right?

[edmundnoble]

@kailuowang Yes. I'm working on disentangling the typeclass hierarchy to remove typeclasses which just exist to agglomerate laws.

[kailuowang]

@edmundnoble , fantastic! Shall we assign this issue to you and mark it as "in progress" , or are you still experimenting?

[kailuowang]

@adelbertc shall we close this since the decision is made on #1616?

[adelbertc]

Yeppers