Sufficiency checker complains about a valid instance.

[sir-wabbit]

import scalaz.meta.minimal

trait InvariantFunctor[F[_]] {
  def imap[A, B](ma: F[A])(f: A => B)(g: B => A): F[B]
}

trait Functor[F[_]] extends InvariantFunctor[F] {
  def map[A, B](ma: F[A])(f: A => B): F[B]

  def imap[A, B](ma: F[A])(f: A => B)(g: B => A): F[B] = map(ma)(f)
}

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](fa: F[A])(f: F[A => B]): F[B]
}

@minimal(("pure", "ap"), ("unit", "zip", "map"))
trait Applicative[F[_]] extends Apply[F] {
  def unit: F[Unit] = pure(())

  def pure[A](a: A): F[A] = map(unit)(_ => a)

  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)] = ap(fa)(map(fb)(b => a => (a, b)))

  def ap[A, B](fa: F[A])(f: F[A => B]): F[B] = map(zip(f, fa)) { case (f, a) => f(a) }

  def map[A, B](ma: F[A])(f: A => B): F[B] = ap(ma)(pure(f))
}

object ComposeImpl {
  type Compose[F[_], G[_]] = { type L[X] = F[G[X]] }

  def invariant[F[_], G[_]](implicit F0: InvariantFunctor[F], G0: InvariantFunctor[G]): InvariantFunctor[Compose[F, G]#L] =
    new ComposeInvariantFunctor[F, G] {
      val F = F0
      val G = G0
    }

  def functor[F[_], G[_]](implicit F0: Functor[F], G0: Functor[G]): Functor[Compose[F, G]#L] =
    new ComposeFunctor[F, G] {
      val F = F0
      val G = G0
    }

  def apply[F[_], G[_]](implicit F0: Apply[F], G0: Apply[G]): Apply[Compose[F, G]#L] =
    new ComposeApply[F, G] {
      val F = F0
      val G = G0
    }

  def applicative[F[_], G[_]](implicit F0: Applicative[F], G0: Applicative[G]): Applicative[Compose[F, G]#L] =
    new ComposeApplicative[F, G] {
      val F = F0
      val G = G0
    }

  private trait ComposeInvariantFunctor[F[_], G[_]] extends InvariantFunctor[Compose[F, G]#L] {
    val F: InvariantFunctor[F]
    val G: InvariantFunctor[G]

    final def imap[A, B](ma: F[G[A]])(f: A => B)(g: B => A): F[G[B]] =
      F.imap[G[A], G[B]](ma)(G.imap(_)(f)(g))(G.imap(_)(g)(f))
  }

  private trait ComposeFunctor[F[_], G[_]] extends Functor[Compose[F, G]#L] {
    val F: Functor[F]
    val G: Functor[G]

    final def map[A, B](fa: F[G[A]])(f: A => B): F[G[B]] =
      F.map(fa)(G.map(_)(f))
  }

  private trait ComposeApply[F[_], G[_]] extends ComposeFunctor[F, G] with Apply[Compose[F, G]#L] {
    val F: Apply[F]
    val G: Apply[G]

    final def ap[A, B](fa: F[G[A]])(f: F[G[A => B]]): F[G[B]] =
      F.ap(fa)(F.map(f)(gab => G.ap(_)(gab)))
  }

  private trait ComposeApplicative[F[_], G[_]] extends ComposeApply[F, G] with Applicative[Compose[F, G]#L] {
    val F: Applicative[F]
    val G: Applicative[G]

    final override def pure[A](a: A): F[G[A]] = F.pure(G.pure(a))
  }
}

Sufficiency checker complains missing implementation for methods: ap OR (unit AND zip AND map) on new ComposeApplicative[F, G].

[sir-wabbit]

Ah, I think the original code had a bug, the correct order of inheritance is:

  private trait ComposeApply[F[_], G[_]] extends Apply[Compose[F, G]#L] with ComposeFunctor[F, G] {
    val F: Apply[F]
    val G: Apply[G]

    final override def ap[A, B](fa: F[G[A]])(f: F[G[A => B]]): F[G[B]] =
      F.ap(fa)(F.map(f)(gab => G.ap(_)(gab)))
  }

  private trait ComposeApplicative[F[_], G[_]] extends Applicative[Compose[F, G]#L] with ComposeApply[F, G] {
    val F: Applicative[F]
    val G: Applicative[G]

    final override def pure[A](a: A): F[G[A]] = F.pure(G.pure(a))
  }

However this results in:

i64.scala:81: error: trait ComposeApplicative inherits conflicting members:
  method map in trait Applicative of type [A, B](<param> ma: F[G[A]])(<param> f: scala.this.Function1[A,B])F[G[B]]  and
  method map in trait ComposeFunctor of type [A, B](<param> fa: F[G[A]])(<param> f: scala.this.Function1[A,B])F[G[B]]
(Note: this can be resolved by declaring an override in trait ComposeApplicative.)
  private trait ComposeApplicative[F[_], G[_]] extends Applicative[Compose[F, G]#L] with ComposeApply[F, G] {
                ^

[sir-wabbit]

This compiles fine:

  private trait ComposeFunctor[F[_], G[_]] extends Functor[Compose[F, G]#L] {
    val F: Functor[F]
    val G: Functor[G]

    final override def map[A, B](fa: F[G[A]])(f: A => B): F[G[B]] =
      F.map(fa)(G.map(_)(f))
  }

  private trait ComposeApply[F[_], G[_]] extends Apply[Compose[F, G]#L] with ComposeFunctor[F, G] {
    val F: Apply[F]
    val G: Apply[G]

    final override def ap[A, B](fa: F[G[A]])(f: F[G[A => B]]): F[G[B]] =
      F.ap(fa)(F.map(f)(gab => G.ap(_)(gab)))
  }

  private trait ComposeApplicative[F[_], G[_]] extends Applicative[Compose[F, G]#L] with ComposeApply[F, G] {
    val F: Applicative[F]
    val G: Applicative[G]

    final override def pure[A](a: A): F[G[A]] = F.pure(G.pure(a))
  }

Turns out there is a difference between final def and final override def that affects child classes.

[sir-wabbit]

So at the end of the (second) day, I am no longer sure it's a bug. I am gonna leave it open for now in case we decide to carefully think about this case (and the interaction between sufficiency and subtyping) later.