[scala] Interesting use for existential types

[Miles Sabin]

Hi folks,

Sadly the code which follows crashes the compiler just at the mo',

  http://scala-webapps.epfl.ch/bugtracking/contribs/display.do?id=721

but I'm fairly sure it ought to work ... which means that Scala's type
system is powerful enough to define type-safe heterogenous maps (of a
restricted, but still very useful, form). I think this is _very_
impressive :-)

  class HMap[A[_], B[_]] {
    val kvs = List[Pair[A[T], B[T]] forSome { type T }]()
 
    def this(kvs: List[Pair[A[T], B[T]] forSome { type T }]) = { this() }
 
    def apply[T](k: A[T]) : B[T] = get(k) match {
      case Some(v) => v
      case None => default(k)
    }
 
    def get[T](k: A[T]) : Option[B[T]] = {
      kvs.foreach({ case Pair(k, v) => return Some(v) })
      return None
    }

    def +[T](kv: (A[T], B[T])): HMap[A, B] = {
      new HMap[A, B](kv :: kvs.remove({ case Pair(kv._1, _) => true ; case _ => false }))
    }
 
    def default[T](k: A[T]): B[T] =
      throw new NoSuchElementException("key not found: " + k)
  }

  object Test extends Application {

    case class Foo[A](v: A)
    case class Bar[A] {
      def apply(a: A) = println(a)
    }
 
    val k1 = Foo[Int](123)
    val k2 = Foo[String]("abc")
 
    val hmap = new HMap[Foo, Bar]+(k1->Bar[Int])+(k2->Bar[String])

    val v1 = hmap(k1) ; v1(k1.v)
    val v2 = hmap(k2) ; v2(k2.v)
  }

Cheers,


Miles

[Adriaan Moors-2]

Hi Miles,

Did you try a recent nightly build? My working copy says:

/Users/adriaan/src/scala/trunk/test/files/pos/hmap.scala:12: error:  
type mismatch;
  found   : B[T(in value $anonfun)]
  required: B[T(in method get)]
       kvs.foreach({ case Pair(k, v) => return Some(v) })
                                                    ^
one error found

which seems to make sense, since the T in method get is universally  
quantified (meaning the caller can pass any T he/she likes), whereas  
the other T is existentially quantified (meaning you should unpack  
the existential to find out which particular type it is). Someone  
please correct me if I'm wrong, as I haven't used  existential types  
much.

I'm currently looking into how to fix that error (have you had a look  
at Lämmel's HList?)

regards
adriaan

On 27 Jul 2007, at 22:50, Miles Sabin wrote:

>  class HMap[A[_], B[_]] {
>     val kvs = List[Pair[A[T], B[T]] forSome { type T }]()
>
>     def this(kvs: List[Pair[A[T], B[T]] forSome { type T }]) =  
> { this() }
>
>     def apply[T](k: A[T]) : B[T] = get(k) match {
>       case Some(v) => v
>       case None => default(k)
>     }
>
>     def get[T](k: A[T]) : Option[B[T]] = {
>       kvs.foreach({ case Pair(k, v) => return Some(v) })
>       return None
>     }
>
>     def +[T](kv: (A[T], B[T])): HMap[A, B] = {
>       new HMap[A, B](kv :: kvs.remove({ case Pair(kv._1, _) =>  
> true ; case _ => false }))
>     }
>
>     def default[T](k: A[T]): B[T] =
>       throw new NoSuchElementException("key not found: " + k)
>   }
>
>   object Test extends Application {
>
>     case class Foo[A](v: A)
>     case class Bar[A] {
>       def apply(a: A) = println(a)
>     }
>
>     val k1 = Foo[Int](123)
>     val k2 = Foo[String]("abc")
>
>     val hmap = new HMap[Foo, Bar]+(k1->Bar[Int])+(k2->Bar[String])
>
>     val v1 = hmap(k1) ; v1(k1.v)
>     val v2 = hmap(k2) ; v2(k2.v)
>   }

[Miles Sabin]

Adriaan Moors wrote,
> Did you try a recent nightly build? My working copy says:

That was with 2.6.0-RC1.

> /Users/adriaan/src/scala/trunk/test/files/pos/hmap.scala:12: error:
> type mismatch;
>   found   : B[T(in value $anonfun)]
>   required: B[T(in method get)]
>        kvs.foreach({ case Pair(k, v) => return Some(v) })
>                                                     ^
> one error found
>
> which seems to make sense, since the T in method get is universally
> quantified (meaning the caller can pass any T he/she likes), whereas
> the other T is existentially quantified (meaning you should unpack
> the existential to find out which particular type it is). Someone
> please correct me if I'm wrong, as I haven't used  existential types
> much.

Yes, I also see that with some variations on this which do actually
compile. I think it ought to be OK tho', because the type of k
determines the type of v fairly straightforwardly.

FWIW, the following _does_ compile and behaves correctly,

  def get[T](k: A[T]) : Option[B[T]] = {
    var i = kvs;
    while(i.length > 0) {
      val p = i.head
      i = i.tail
     
      p match {
        case Pair(k, v: B[T]) => return Some(v)
      }
    }
   
    return None
  }

Not quite as pretty, and here the type annotation for v deals with your
complaint ... but I think it's actually redundant.

> I'm currently looking into how to fix that error (have you had a look
> at L�mmel's HList?)

Yes I have ... it's not a coincidence that this is called HMap ;-)

Cheers,


Miles