Impredicative types vs. plain old subtyping

Question

A friend of mine posed a seemingly innocuous Scala language question last week that I didn't have a good answer to: whether there's an easy way to declare a collection of things belonging to some common typeclass. Of course there's no first-class notion of "typeclass" in Scala, so we have to think of this in terms of traits and context bounds (i.e. implicits).

Concretely, given some trait T[_] representing a typeclass, and types A, B and C, with corresponding implicits in scope T[A], T[B] and T[C], we want to declare something like a List[T[a] forAll { type a }], into which we can throw instances of A, B and C with impunity. This of course doesn't exist in Scala; a question last year discusses this in more depth.

The natural follow-up question is "how does Haskell do it?" Well, GHC in particular has a type system extension called impredicative polymorphism, described in the "Boxy Types" paper. In brief, given a typeclass T one can legally construct a list [forall a. T a => a]. Given a declaration of this form, the compiler does some dictionary-passing magic that lets us retain the typeclass instances corresponding to the types of each value in the list at runtime.

Thing is, "dictionary-passing magic" sounds a lot like "vtables." In an object-oriented language like Scala, subtyping is a much more simple, natural mechanism than the "Boxy Types" approach. If our A, B and C all extend trait T, then we can simply declare List[T] and be happy. Likewise, as Miles notes in a comment below, if they all extend traits T1, T2 and T3 then I can use List[T1 with T2 with T3] as an equivalent to the impredicative Haskell [forall a. (T1 a, T2 a, T3 a) => a].

However, the main, well-known disadvantage with subtyping compared to typeclasses is tight coupling: my A, B and C types have to have their T behavior baked in. Let's assume this is a major dealbreaker, and I can't use subtyping. So the middle ground in Scala is pimps^H^H^H^H^Himplicit conversions: given some A => T, B => T and C => T in implicit scope, I can again quite happily populate a List[T] with my A, B and C values...

... Until we want List[T1 with T2 with T3]. At that point, even if we have implicit conversions A => T1, A => T2 and A => T3, we can't put an A into the list. We could restructure our implicit conversions to literally provide A => T1 with T2 with T3, but I've never seen anybody do that before, and it seems like yet another form of tight coupling.

Okay, so my question finally is, I suppose, a combination of a couple questions that were previously asked here: "why avoid subtyping?" and "advantages of subtyping over typeclasses" ... is there some unifying theory that says impredicative polymorphism and subtype polymorphism are one and the same? Are implicit conversions somehow the secret love-child of the two? And can somebody articulate a good, clean pattern for expressing multiple bounds (as in the last example above) in Scala?

Answer 1

You're confusing impredicative types with existential types. Impredicative types allow you to put polymorphic values in a data structure, not arbitrary concrete ones. In other words [forall a. Num a => a] means that you have a list where each element works as any numeric type, so you can't put e.g. Int and Double in a list of type [forall a. Num a => a], but you can put something like 0 :: Num a => a in it. Impredicative types is not what you want here.

What you want is existential types, i.e. [exists a. Num a => a] (not real Haskell syntax), which says that each element is some unknown numeric type. To write this in Haskell, however, we need to introduce a wrapper data type:

data SomeNumber = forall a. Num a => SomeNumber a

Note the change from exists to forall. That's because we're describing the constructor. We can put any numeric type in, but then the type system "forgets" which type it was. Once we take it back out (by pattern matching), all we know is that it's some numeric type. What's happening under the hood, is that the SomeNumber type contains a hidden field which stores the type class dictionary (aka. vtable/implicit), which is why we need the wrapper type.

Now we can use the type [SomeNumber] for a list of arbitrary numbers, but we need to wrap each number on the way in, e.g. [SomeNumber (3.14 :: Double), SomeNumber (42 :: Int)]. The correct dictionary for each type is looked up and stored in the hidden field automatically at the point where we wrap each number.

The combination of existential types and type classes is in some ways similar to subtyping, since the main difference between type classes and interfaces is that with type classes the vtable travels separately from the objects, and existential types packages objects and vtables back together again.

However, unlike with traditional subtyping, you're not forced to pair them one to one, so we can write things like this which packages one vtable with two values of the same type.

data TwoNumbers = forall a. Num a => TwoNumbers a a

f :: TwoNumbers -> TwoNumbers
f (TwoNumbers x y) = TwoNumbers (x+y) (x*y)

list1 = map f [TwoNumbers (42 :: Int) 7, TwoNumbers (3.14 :: Double) 9]
-- ==> [TwoNumbers (49 :: Int) 294, TwoNumbers (12.14 :: Double) 28.26]

or even fancier things. Once we pattern match on the wrapper, we're back in the land of type classes. Although we don't know which type x and y are, we know that they're the same, and we have the correct dictionary available to perform numeric operations on them.

Everything above works similarly with multiple type classes. The compiler will simply generate hidden fields in the wrapper type for each vtable and bring them all into scope when we pattern match.

data SomeBoundedNumber = forall a. (Bounded a, Num a) => SBN a

g :: SomeBoundedNumber -> SomeBoundedNumber
g (SBN n) = SBN (maxBound - n)

list2 = map g [SBN (42 :: Int32), SBN (42 :: Int64)]
-- ==> [SBN (2147483605 :: Int32), SBN (9223372036854775765 :: Int64)]

As I'm very much a beginner when it comes to Scala, I'm not sure I can help with the final part of your question, but I hope this has at least cleared up some of the confusion and given you some ideas on how to proceed.

Answer 2

@hammar's answer is perfectly right. Here is the scala way of doint it. For the example i'll take Show as the type class and the values i and d to pack in a list :

// The type class
trait Show[A] {
   def show(a : A) : String
}

// Syntactic sugar for Show
implicit final class ShowOps[A](val self : A)(implicit A : Show[A]) {
  def show = A.show(self)
}

implicit val intShow    = new Show[Int] {
  def show(i : Int) = "Show of int " + i.toString
}

implicit val stringShow = new Show[String] {
  def show(s : String) = "Show of String " + s
}


val i : Int    = 5
val s : String = "abc"

What we want is to be able run the following code

val list = List(i, s)
for (e <- list) yield e.show

Building the list is easy but the list won't "remember" the exact type of each of its elements. Instead it will upcast each element to a common super type T. The more precise super super type between String and Int being Any, the type of the list is List[Any].

The problem is: what to forget and what to remember? We want to forget the exact type of the elements BUT we want to remember that they are all instances of Show. The following class does exactly that

abstract class Ex[TC[_]] {
  type t
  val  value : t
  implicit val instance : TC[t]
}

implicit def ex[TC[_], A](a : A)(implicit A : TC[A]) = new Ex[TC] {
  type t = A
  val  value    = a
  val  instance = A
}

This is an encoding of the existential :

val ex_i : Ex[Show] = ex[Show, Int](i)
val ex_s : Ex[Show] = ex[Show, String](s)

It pack a value with the corresponding type class instance.

Finally we can add an instance for Ex[Show]

implicit val exShow = new Show[Ex[Show]] {
  def show(e : Ex[Show]) : String = {
    import e._
    e.value.show 
  }
}

The import e._ is required to bring the instance into scope. Thanks to the magic of implicits:

val list = List[Ex[Show]](i , s)
for (e <- list) yield e.show

which is very close to the expected code.