Difference between type constructors and parametrized type bounds in Scala

Question

Take a look at the following code:

case class MyTypeConstructor[T[_]: Seq, A](mySeq: T[A]) {
    def map[B](f: A => B): T[B] = mySeq.map(f) // value map is not a member of type parameter T[A]
}

case class MyTypeBounds[T[A] <: Seq[A], A](mySeq: T[A]) {
    def map[B](f: A => B): T[B] = mySeq.map(f) 
}

Ideally both would do the same thing, just define a dummy map that calls the map method from Seq. However, the first one does not event compile while the second one works (actually the second one doesen't work either but I am omitting things for simplicity).

The compilation error I get is that T[A] does not have a member map, but I am stranged because the type constructor T should return a Seq (which does have map).

Can anyone explain me what is conceptually different between these two implementations?

Answer 1

what is conceptually different between these two implementations?

We can constrain polymorphic type parameters either using subtyping or type class approach

scala> case class Subtyping[T[A] <: Seq[A], A](xs: T[A]) {
     |   def map[B](f: A => B) = xs.map(f)
     | }
     | 
     | import scala.collection.BuildFrom
     |
     | case class TypeClassVanilla[T[x] <: IterableOnce[x], A](xs: T[A]) {
     |   def map[B](f: A => B)(implicit bf: BuildFrom[T[A], B, T[B]]): T[B] =
     |     bf.fromSpecific(xs)(xs.iterator.map(f))
     | }
     | 
     | import cats.Functor
     | import cats.syntax.all._
     | 
     | case class TypeClassCats[T[_]: Functor, A](xs: T[A]) {
     |   def map[B](f: A => B): T[B] =
     |     xs.map(f) 
     | }
class Subtyping
import scala.collection.BuildFrom
class TypeClassVanilla
import cats.Functor
import cats.syntax.all._
class TypeClassCats

scala> val xs = List(1, 2, 3)
val xs: List[Int] = List(1, 2, 3)

scala> Subtyping(xs).map(_ + 1)
val res0: Seq[Int] = List(2, 3, 4)

scala> TypeClassCats(xs).map(_ + 1)
val res1: List[Int] = List(2, 3, 4)

scala> TypeClassVanilla(xs).map(_ + 1)
val res2: List[Int] = List(2, 3, 4)

They are different approaches to achieving the same thing. With type class approach perhaps we do not have to worry as much about organising inheritance hierarchies, which as system grows in complexity, might lead us to start artificially forcing things into hierarchy.

Answer 2

T[_]: Seq

This does not say "T[_] should return a Seq-like this". That's what your second example correctly states. This says "T[_] should satisfy an implicit whose name is Seq". But T takes parameters, so it can't really be a part of an implicit. Essentially, it's trying to do

case class MyTypeConstructor[T[_], A](mySeq: T[A])(implicit arg: Seq[T[_]])

But Seq[T[_]] doesn't make sense as an argument to a function, first off because T takes a parameter which is not provided* and second because Seq is not intended to be used as an implicit.

We can see that this is an odd construct because you can remove myMap and still get an error.

// error: type T takes type parameters
case class MyTypeConstructor[T[_]: Seq, A](mySeq: T[A]) {}

*Theoretically, the compiler could treat T[_]: Seq as a declaration that an implicit existential argument is required, but that isn't what it does now and would be of questionable utility, even if it did.