David R. MacIver's Blog

Minor revelation about Scala existential types

So, I’ve just realised why Scala’s existential types are several orders of magnitude more powerful than Java’s wildcards.

   def swap(xs : Array[T forSome { type T; }]) = xs(0) = x(1); 

The type is not completely unknown, and is persisted across method invocations, so for a given fixed instance you can make use of that to perform operations that would be impossible with wildcards. In particular the following can’t work:

  public void swap(List<?> xs){ 
    xs.set(0, xs.get(1));
  }

This can’t work, because Java has no way of determining that the two wildcards in xs.set and xs.get are the same.

Comments

ijuma on 2008-01-09 20:50:00:

Try the following in your favourite Java compiler (using [] for generics):

public [T] void swap(List[? extends T] xs){
swap0(xs);
}

private [T] void swap0(List[T] xs) {
xs.set(0, xs.get(1));
}

Ugly, but works.

Ismael

David R. MacIver on 2008-01-09 21:00:00:

Yeah. You can basically encode existentially quantified types by moving the type parameter around and universally quantifying instead. This gets really annoying outside of non-trivial examples though - to the point where I usually just give up and cast.

David on 2008-01-09 21:49:00:

Not understanding something here:

public [T] void swap(List[T] xs) {
xs.set(0,xs.get(1));
}

completely valid in java (1.6) and generates no errors or warnings.

so used in the context of:
List[String] xs = new ArrayList[String]();
swap(xs);

it will work correctly (other than the out of bounds exception since I didn’t populate the list)

what am I missing?

David R. MacIver on 2008-01-09 21:54:00:

True. That was probably a bad example because of the misleading method.

A better one is as follows:

def foo(xss : Array[Array[T : forSome { type T; }]] = for(xs <- xss) {
xs(0) = xs(1);
}

The point is that this works locally without you having to extract out all your logic into a single method and pass it that way. Sometimes the extracted method is actually useful and you should do that, but this removes a lot of pain points when you have relatively simple code.

Marius on 2008-01-18 22:56:00:

So where is the revelation?

def foo[T](xss : Array[Array[T]]) = for(xs <- xss) {
xs(0) = xs(1);
}

seems to be equivalent to your example. So why using an existential type in your example?

In Java one can capture the wildcard with a T.

P.S.
I also like Scala very much and I’d like to have a better understanding of existential types although so far it seems to me that their usefulness is related with packing types without using inference of the polymorphic method

David R. MacIver on 2008-01-18 23:57:00:

Those two don’t do the same thing though.

Array(Array(“foo”), Array(1)) is a perfectly valid Array[Array[T forSome { type T; }]], but it isn’t an Array[Array[T]] for any given T. The point is that T can assume different values for different members of the outer array.

Marius on 2008-01-19 17:00:00:

having :

def foo(xss : Array[Array[T forSome { type T; }]]) = for(xs <- xss) {
xs(0) = xs(1);
}


attempting to call it like:
foo1(Array(Array(“foo”), Array(3)));

yields the following compiler error :

“inferred type arguments [T forSome { type T }] do not conform to method apply’s type parameter bounds [A <: AnyRef]”

similarly:

val t: Array[Array[T forSome { type T; }]] = Array(Array(“foo”), Array(1))

is not a valid declaration.

(I’m using Scala 2.6.1)

Any thoughts?

Marius on 2008-01-19 17:12:00:

One more thing:

having

val t: Array[Array[T forSome {type T}]] = Array(Array(“foo”), Array(“1”))

yields the same compiler error whereas:

val t: Array[Array[T forSome {type T <: String}]] = Array(Array(“foo”), Array(“1”))

is a correct declaration.

... so far I could not use existential types to abstract different types. Am I doing something wrong?

P.S. - there is atypoe above I declared foo but invoked foo1. Just ignore this

Marius on 2008-01-19 17:23:00:

doing a different approach:

having:

class C[T](x: T*)

and
def foo(xs : C[C[T forSome {type T;}]]) = { }

foo(new C(new C(“foo”), new C(1)));

compiles correctly

whereas

having:

def foo[T](xs : C[C[T]]) = { }

does not compile.

so you’re right the two declarations are not the same (just beautiful) but still I’m not clear why the Array’s example does not compile. Arrays apply method is parameterized like [A <: Any] but obviously a type T is ultimately an Any.

Best of drmaciver.com | David R. MacIver on 2014-01-12 13:13:29:

[…] A little detail on the difference between Java wildcards and Scala existential types. […]