Diverging Inject instances

[notxcain]

Given this specific case when a type constructor being injected is the right-right part of Coproduct and defined in object.

trait Foo[A]
trait Bar[A]
object Baz {
  trait F[A]
}
object Repro {
  Inject[Baz.F, Coproduct[Foo, Coproduct[Bar, Baz.F, ?], ?]]
}

It does not compile and I get

Error:(12, 9) diverging implicit expansion for type cats.free.Inject[Baz.F,[γ$0$]cats.data.Coproduct[Foo,[γ$1$]cats.data.Coproduct[Bar,Baz.F,γ$1$],γ$0$]]
starting with method catsFreeReflexiveInjectInstance in class InjectInstances
  Inject[Baz.F, Coproduct[Foo, Coproduct[Bar, Baz.F, ?], ?]]

I compiles well if move F out of Baz. But sadly for my case it's not an option.

[travisbrown]

There seems to be a lot of weirdness here. The following compiles on 2.12.1 if you paste it as individual lines into the REPL:

trait Foo[A]
trait Bar[A]
object Baz { trait F[A] }
import cats.data.Coproduct, cats.free._
type BarBaz[x] = Coproduct[Bar, Baz.F, x]
type FooBarBaz[x] = Coproduct[Foo, BarBaz, x]
Inject[Baz.F, FooBarBaz]

But not with :paste, not if the import comes first, and not if the cats.free._ import is replaced with cats.free.Inject (which seems like it should work just fine).

There's weirdness even without the nesting—e.g. none of the Injects here compile:

import cats.data.Coproduct, cats.free.Inject

trait Foo[A]
trait Bar[A]
trait Baz[A]

Inject[Foo, Coproduct[Foo, Coproduct[Bar, Baz, ?], ?]]
Inject[Bar, Coproduct[Foo, Coproduct[Bar, Baz, ?], ?]]
Inject[Baz, Coproduct[Foo, Coproduct[Bar, Baz, ?], ?]]

I think it's likely that we could do a better job of working around the compiler issues here to minimize the weirdness for users, but I'd say we kick that down the road past the 0.9 release, which could otherwise happen this week.

[romainreuillon]

I ran into the same pb while trying to stack several free monads:

  import cats._
  //import cats.data._
  import cats.data.Coproduct, cats.free.Inject, cats.free.Free

  object DSL1 {
    sealed trait Instruction[T]
    final case class Get() extends Instruction[Int]
    final case class Get2() extends Instruction[Double]

    implicit def dsl1[F[_]](implicit I: Inject[Instruction, F]): DSL1[F] = new DSL1[F]

     val interpreter = new (Instruction ~> Id) {
       def apply[A](fa: Instruction[A]): Id[A] = fa match {
         case Get() => 1
         case Get2() => 2.0
       }
     }
  }

  class DSL1[F[_]](implicit I: Inject[DSL1.Instruction, F]) {
    def get(): Free[F, Int] = Free.inject[DSL1.Instruction, F](DSL1.Get())
    def get2(): Free[F, Double] = Free.inject[DSL1.Instruction, F](DSL1.Get2())
  }

  object DSL2 {
    sealed trait Instruction[T]
    final case class Get() extends Instruction[Int]
    final case class Get2() extends Instruction[Double]

    implicit def dsl2[F[_]](implicit I: Inject[Instruction, F]): DSL2[F] = new DSL2[F]

    val interpreter = new (Instruction ~> Id) {
      def apply[A](fa: Instruction[A]): Id[A] = fa match {
        case Get() => 3
        case Get2() => 4.0
      }
    }
  }

  class DSL2[F[_]](implicit I: Inject[DSL2.Instruction, F]) {
    def get(): Free[F, Int] = Free.inject[DSL2.Instruction, F](DSL2.Get())
    def get2(): Free[F, Double] = Free.inject[DSL2.Instruction, F](DSL2.Get2())
  }

  object DSL3 {
    sealed trait Instruction[T]
    final case class Get() extends Instruction[Int]
    final case class Get2() extends Instruction[Double]

    implicit def dsl3[F[_]](implicit I: Inject[Instruction, F]): DSL3[F] = new DSL3[F]

    val interpreter = new (Instruction ~> Id) {
      def apply[A](fa: Instruction[A]): Id[A] = fa match {
        case Get() => 4
        case Get2() => 5.0
      }
    }
  }

  class DSL3[F[_]](implicit I: Inject[DSL3.Instruction, F]) {
    def get(): Free[F, Int] = Free.inject[DSL3.Instruction, F](DSL3.Get())
    def get2(): Free[F, Double] = Free.inject[DSL3.Instruction, F](DSL3.Get2())
  }

  type MergedDSL[A] = Coproduct[DSL1.Instruction,  Coproduct[DSL2.Instruction, DSL3.Instruction, ?], A]

  def prg(implicit dsl1: DSL1[MergedDSL], dsl2: DSL2[MergedDSL], dsl3: DSL3[MergedDSL]) =
    for {
      g <- dsl1.get()
      g2 <- dsl1.get2()
      sg <- dsl2.get()
      sg2 <- dsl2.get2()
    } yield g * g2 * sg * sg2

  val interpreter: MergedDSL ~> Id = DSL1.interpreter or (DSL2.interpreter or DSL3.interpreter)

  println(prg.foldMap(interpreter))

I get a compile time error:

[error] /home/reuillon/Documents/Recherche/Projects/freedsl/dsl/src/test/scala/freedsl/dsl/DSLTest.scala:199: diverging implicit expansion for type cats.free.Inject[freedsl.dsl.MergeCats.DSL3.Instruction,freedsl.dsl.MergeCats.DSL3.Instruction]
[error] starting with method catsFreeReflexiveInjectInstance in class InjectInstances
[error]   println(prg.foldMap(interpreter))
[error]           ^

[peterneyens]

As as workaround adding this implicit using shapeless.Lazy worked in my case :

import cats.data.Coproduct
import cats.free.Inject
import shapeless.Lazy

implicit def catsFreeRightInjectInstanceLazy[F[_], G[_], H[_]](
  implicit I: Lazy[Inject[F, G]]
): Inject[F, Coproduct[H, G, ?]] = Inject.catsFreeRightInjectInstance(I.value)

Hopefully we can come up with a cleaner solution though.

[dvic]

@peterneyens @romainreuillon For me the automatic implicit resolution works on Scala 2.12.2 when I define my merged DSL in terms of type aliases, for the example mentioned by @romainreuillon that would be something like

type SubDSL[A] = Coproduct[DSL2.Instruction, DSL3.Instruction, A]
type MergedDSL[A] = Coproduct[DSL1.Instruction, SubDSL, A]

Any clue why?

[romainreuillon]

Great. I'll give it a try with 2.12.2...

Thx

[dvic]

Just checked with 2.12.1, that should also work.

[dvic]

But you have to have scalacOptions ++= Seq("-Ypartial-unification"), otherwise it won't work.