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.