Scala higher type dispersion

Question

I dip my toes into higher types, learning a very simple 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", _)) 

It works:

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

But this does not compile:

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

Compilation errors that 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 make deviations in the game?

Answer 1

We can do this work with a slightly more parametric 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", _))) } } 

Productivity:

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

Now the compiler displays Some as Mappable[Some]#Res[Int] and Mappable[List]#Res[Int] , which is pretty ugly. One would expect that the compiler would indeed be able to infer the desired type without requiring any co / contravariance based on the Mappable , which we cannot do, since we use it in an invariant position.

Answer 2

The politicism of subtypes allows us to pass values ​​of a certain type or any of its subtypes into a method. If the method takes a value like Fruit, we can also pass Apple inside (an apple is a fruit after all). Therefore, if you want to pass Mappable.MappableOption to your bananaTuple method, you must make this MappableOption a subtype of MappableSome (since the type of your first bananaTuple parameter is implicit). This means that you want your comparable contravariant (if Some <: Option , then Mappable[Some] >: Mappable[Option] ).

But you cannot have Mappable[F[_]] contravariant in F, because F appears in the covariant map position (as a function parameter). Note that F also appears in the 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 relation, such as, for example, Apple <: Fruit will result in Mappable[Apple] >: Mappable[Fruit] (this will not compile since Apple and Fruit are not type constructors, but I just use simple types to do here).

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