How to use typeclass inheritance?

trait Functor[F[_]]:
  extension[A] (fa: F[A])
    def map[B](f: A => B): F[B]

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

  extension[A, B] (fab: F[A => B])
    def ap(fa: F[A]): F[B]

object Applicative:
  def pure[A, F[_]](a: A)(using ap: Applicative[F]): F[A] = ap.pure(a)

@targetName("apFirst")
def <*[A, B, F[_]: Applicative](fa: F[A], fb: F[B]): F[A] = fa.map(a => (_: B) => a).ap(fb)

Error: value map is not a member of type F in <*.

I get error in the last function. If I add Functor constraint it works, but shouldn't it work without that since I constrained it in the Applicative definition? What am I missing?

Solution

Type class inheritance is a normal inheritance:

trait Functor[F[_]]:
  extension[A] (fa: F[A])
    def map[B](f: A => B): F[B]

trait Applicative[F[_]] extends Functor[F]:
  def pure[A](a: A): F[A]

  extension[A, B] (fab: F[A => B])
    def ap(fa: F[A]): F[B]
  
  extension[A] (fa: F[A])
    override def map[B](f: A => B): F[B] = pure(f).ap(fa)

Be cautious when you use it though, as having 2 type classes having the same parent will result in conflicting instances:

trait TypeClass1[A]
  def method: A
object TypeClass1:
  def method[A: TypeClass1]: A = summon[TypeClass1[A]].method

trait TypeClass2[A] extends TypeClass1[A]:
  def method2: A
  override def method: A = method2

trait TypeClass3[A] extends TypeClass1[A]:
  def method3: A
  override def method: A = method3

def usage[A: TypeClass2: TypeClass3] =
  TypeClass1.method[A] // ambiguous implicit

This issue can be seen in some Cats Effect 2 type class hierarchy.

When you define things like this:

trait Functor[F[_]]:
  extension[A] (fa: F[A])
    def map[B](f: A => B): F[B]

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

  extension[A, B] (fab: F[A => B])
    def ap(fa: F[A]): F[B]

then the inside of Applicative[F] sees that F is a Functor and has access to .map... but F : Functor is a constraint, not a proper type bound. It desugars to (using Functor[F]) which is merely an argument to a constructor (or other method), not something which extends interface nor encodes in its type any information about inheritance. As far as the outside of Applicative is concerned in such code there is no relationship between Functor[F] and Applicative[F].

Additionally, the relation would be backward - Functor's map can be implemented with pure and ap, not otherwise, and F being a Applicative proves that F is a Functor, so it could kinda work with something like:

trait Functor[F[_]]:
  extension[A] (fa: F[A])
    def map[B](f: A => B): F[B]
object Functor:
  given fromApplicative[F[_]: Applicative]: Functor[F] with
    extension[A] (fa: F[A])
      override def map[B](f: A => B): F[B] =
        summon[Applicative[F]].pure(f).ap(fa)

trait Applicative[F[_]:
  def pure[A](a: A): F[A]

  extension[A, B] (fab: F[A => B])
    def ap(fa: F[A]): F[B]

Then there would still be no relationship between Applicative and Functor types, but every time there would be given Appilcative[F] a given Functor[F] could be constructed. However, this encoding would be harder to debug if you missed something, so just extending traits is both easier, safer and potentially less taxing on GC (only 1 instance passed down, rather than spawning a lot of them on demand).