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.

This entry was posted in programming and tagged , , on by .

10 thoughts on “Minor revelation about Scala existential types

  1. ijuma

    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

  2. David R. MacIver

    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.

  3. David

    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?

  4. David R. MacIver

    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.

  5. Marius

    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

  6. David R. MacIver

    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.

  7. Marius

    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?

  8. Marius

    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

  9. Marius

    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.

  10. Pingback: Best of drmaciver.com | David R. MacIver

Comments are closed.