Minor revelation about Scala existential types
January 9th, 2008So, 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.
January 9th, 2008 at 8:50 pm
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
January 9th, 2008 at 9:00 pm
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.
January 9th, 2008 at 9:49 pm
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?
January 9th, 2008 at 9:54 pm
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.
January 18th, 2008 at 10:56 pm
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
January 18th, 2008 at 11:57 pm
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.
January 19th, 2008 at 5:00 pm
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?
January 19th, 2008 at 5:12 pm
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
January 19th, 2008 at 5:23 pm
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.