Existential types: what do clouds smell like?

In Scala, it’s pretty common to use wildcards to get rid of declaring parameter types and insist on it’s not necessary knowing their type for executing our method/class associated logic.
Something like:

val myArray: Array[_] = Array(1,2,3)

Before talking about existential types, I think it’s appropiate to give a little disclaimer about how heavy it can seem (better than a couple of pills with a shot).

tumblr_mgf4arKIkk1rfq0ndo1_500

Existential types

Let’s suppose we have a method that returns cardinality of an element collection. If this collection is covariant in T

scala> def count(elements: List[Any]): Int = elements.length
count: (elements: List[Any])Int

we would have no problems when invoking such method with

scala> count(List[Int](1,2,3))
res0: Int = 3

However, if we try with a collection which is invariant in T

scala> def count(elements: Set[Any]): Int = elements.size
count: (elements: Set[Any])Int

scala> count(Set[Int](1,2,3))
<console>:9: error: type mismatch;
 found   : scala.collection.immutable.Set[Int]
 required: Set[Any]
Note: Int <: Any, but trait Set is invariant in type A.
You may wish to investigate a wildcard type such as `_ <: Any`. (SLS 3.2.10)
              count(Set[Int](1,2,3))
                            ^

Obvious. No surprise so far. A Set[Int] ain’t a Set[Any]. If we want that our method accepts any kind of Set of elements, we can make it generic:

scala> def count[T](elements: Set[T]): Int = elements.size
count: [T](elements: Set[T])Int

scala> count(Set[Int](1,2,3))
res0: Int = 3

Nevertheless, this forces us to add a pointless parameter type: it’s just a way of making compiler happy, obviating the contained type.

The proposed alternative is to define the parameter type inside the parameter signature, like this:

scala> def count(elements: Set[T] forSome {type T}): Int = elements.size
count: (elements: Set[_])Int

scala> count(Set[Int](1,2,3))
res1: Int = 3

Existential types are in deed what underlies the syntactic sugar of wildcards. The equivalence with to ‘yee-haa’ notation is:

scala> def count(elements: Set[_]): Int = elements.size
count: (elements: Set[_])Int

scala> count(Set[Int](1,2,3))
res2: Int = 3

The twist

Significantly, about parameter definition, we can add some constraints (context bounds). For example, if we want to define a Set that contains every kind of primitive type…

scala> def count(elements: Set[T] forSome {type T<:AnyVal}): Int = elements.size
count: (elements: Set[_ <: AnyVal])Int

Just realize that REPL is already returning the declared method with the ‘yee-haa’ notation. We can prove that context bounds work with:

scala> count(Set(1,2,3))
res3: Int = 3

scala> count(Set(new{}))
<console>:9: error: type mismatch;
 found   : AnyRef
 required: AnyVal
Note that implicit conversions are not applicable because they are ambiguous:
 both method ArrowAssoc in object Predef of type [A](self: A)ArrowAssoc[A]
 and method Ensuring in object Predef of type [A](self: A)Ensuring[A]
 are possible conversion functions from AnyRef to AnyVal
              count(Set(new{}))
                        ^

Just when we try to invoke the method with a common AnyRef…BAZINGA!: the compiler jumps its prey like a cheetah.

91662

A limitation is the impossibility of defining view bounds over the type T:

scala> def count(elements: Set[T] forSome {type T<%Int}): Int = elements.size
<console>:1: error: `=', `>:', or `<:' expected
       def count(elements: Set[T] forSome {type T<%Int}): Int = elements.size
                                                 ^

In this case, we would have to get back to the original idea of parameterizing the method. If we wanted to define a method that added all the elements of a Set, and that all elements had a way to become a Double:

scala> def sum[T<%Double](elements: Set[T]): Double =
  (0.0 /: elements)((d1,d2) => d1 + d2)
sum: [T](elements: Set[T])(implicit evidence$1: T => Double)Double

scala> sum(Set[Int](1,2,3))
res9: Double = 6.0

scala> sum(Set[Float](1.0f,2.5f))
res10: Double = 3.5

Twisting the twist (and seriously, you can’t twist it anymore)

If we became philosophers, what would it happen if we used the following existential type?

T forSome {type T}

982aad317c237d9fa918138b1c7bd020_1024

Without opening a debate if the world is plain and it’s hold by four elephants on the shell of a cosmic turtle…the type we refer to is Any (We will have a closer look at Any in future posts.).

So, what’s the main difference between the following definitions?

Set[T] forSome { type T }
Set[T forSome { type T }]

my-eyes-messed-up_o_386883

First type refers to all kind of Set (ignoring the contained type) while the second type, as we have said before, represents Set[Any].

Can’t you still see the difference? Think in invariance terms, and with the help of a little piece of code. With first definition, already used in first examples of this post, we have that:

scala> def count(elements: Set[T] forSome {type T}): Int = elements.size
count: (elements: Set[_])Int

scala> count(Set[Int](1,2,3))
res13: Int = 3

scala> count(Set[String]("hi","bye"))
res14: Int = 2

But if we change the method definition, using the second of the previously exposed forms, we will see that Set[Int] ain’t a subtype of Set[Any]:

scala> def count(elements: Set[T forSome {type T}]): Int = elements.size
count: (elements: Set[_])Int

scala> count(Set[Int](1,2,3))
<console>:9: error: type mismatch;
 found   : scala.collection.immutable.Set[Int]
 required: Set[T forSome { type T }]
Note: Int <: T forSome { type T }, but trait Set is invariant in type A.
You may wish to investigate a wildcard type such as `_ <: T forSome { type T }`. (SLS 3.2.10)
              count(Set[Int](1,2,3))
                            ^

Mad enough? I hope you don’t, just to keep reading further posts 🙂

Peace out!

Anuncios

One thought on “Existential types: what do clouds smell like?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s