Scala higher kinded type variance

Question

I am dipping my toes in higher kinded types, exploring a very basic Scala example:

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

object Mappable {
  implicit object MappableOption extends Mappable[Option] {
    def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
  }
  implicit object MappableSeq extends Mappable[Seq] {
    def map[A, B](fa: Seq[A])(f: A => B): Seq[B] = fa.map(f)
  }
}

def bananaTuple[F[_], T](f: F[T])(implicit F: Mappable[F]): F[(String, T)] =
  F.map(f)(("banana", _))

This works:

bananaTuple(Option(42)) // Some((banana,42))
bananaTuple(Seq(42))    // List((banana,42))

But this does not compile:

bananaTuple(Some(42))
bananaTuple(List(42))

The compile errors I get:

could not find implicit value for parameter F: ch.netzwerg.hkt.HigherKindedTypes.Mappable[Some] bananaTuple(Some(42))

not enough arguments for method bananaTuple: (implicit F: ch.netzwerg.hkt.HigherKindedTypes.Mappable[Some])Some[(String, Int)]. Unspecified value parameter F. bananaTuple(Some(42))

How can I bring variance into the game?

Answer 1

We can make this work with a little more parameteric polymorphism:

object MappableExample {
  trait Mappable[F[_]] {
    type Res[_]
    def map[A, B](f: A => B)(c: F[A]): Res[B]
  }

  implicit def seqMappable[C[X] <: Seq[X]] = new Mappable[C] {
    type Res[X] = Seq[X]
    override def map[A, B](f:A => B)(c: C[A]): Seq[B] = c.map(f)
  }

  implicit def optionMappable[C[X] <: Option[X]]: Mappable[C] = new Mappable[C] {
    type Res[X] = Option[X]
    override def map[A, B](f: A => B)(c: C[A]): Option[B] = c.map(f)
  }

  def map[A, B, C[_]](xs: C[A])(f: A => B)(implicit mappable: Mappable[C]): mappable.Res[B] = {
    mappable.map(f)(xs)
  }

  def main(args: Array[String]): Unit = {
    println(map(List(1,2,3))(("banana", _)))
    println(map(Some(1))(("banana", _)))
  }
}

Yields:

List((banana,1), (banana,2), (banana,3))
Some((banana,1))

The compiler now infers Some as Mappable[Some]#Res[Int] and Mappable[List]#Res[Int] which is quite ugly. One would expect the compiler to actually be able to infer the right type without needing for any co/contravariance on the Mappable trait, which we can't do since we're using it in an invariant position.

Answer 2

Subtype polymorphism allows us to pass values of a certain type or any of its subtypes to a method. If a method takes a value of type Fruit, we can also pass an Apple inside (an apple is a fruit after all). So if you want to be able to pass a Mappable.MappableOption to your bananaTuple method, you have to make that MappableOption a subtype of MappableSome (since the type of your first parameter of bananaTuple dictates the implicit one). This means that you want your Mappable contravariant (if Some <: Option, then Mappable[Some] >: Mappable[Option]).

But you cannot have Mappable[F[_]] contravariant in F because F appears in covariant position of map (as a function parameter). Note that F also appears in contravariant position of map (as a return value).

If you manage to make Mappable[F[_]] contravariant in F, it should work, but I'm not sure if making it contravariant makes sense. That is, if you want a subtype relationship such as e.g. Apple <: Fruit to result in Mappable[Apple] >: Mappable[Fruit] (this would not compile since Apple and Fruit are not type constructors, but I'm just using simple types to make a point here).

Making a type contravariant in its type and solving the problem of contravariant type appearing in covariant position is a common problem and perhaps it's better if you search for it elsewhere (here is one example). I still think that it's better to provide an implicit object for every type you want to use, that is, to provide separate implicit objects for e.g. Seq and List.