Scala knowledge - Existential types

前言

Scala 的Type parameter 是一個強大的特性, 實現許多抽象化資料結構, 但Scala run 在jvm上, 仍是受到type erase限制, 因此在Type parameter中需要再處理抽象化type時候, Existential types 是一個很好詮釋Abstract data type的方式

許多概念和範例來自這些文章, 你也可以直接參考原文

http://developer.51cto.com/art/200906/127934.htm

http://www.drmaciver.com/2008/03/existential-types-in-scala/

Existential types

Existential types是用來表現Abstract data type
可以看一下Wiki 對於Existential types本質上的定義

Existential types are frequently used in connection with record types to represent modules and abstract data types, due to their ability to separate implementation from interface. For example, the type "T = ∃X { a: X; f: (X → int); }" describes a module interface that has a data member named a of type X and a function named f that takes a parameter of the same type X and returns an integer. This could be implemented in different ways; for example:

Wiki定義有點抽象, 就我個人理解而言
Existential types這個名稱是從 ∃X { a: X; f: (X → int); } 這裡開始
∃在數學符號裡面代表 Exist 存在
直白上來說, Existential type T = ∃X { a: X; f: (X → int); }這個例子
就是在說明 Module T內存在一個 X type,
這個X 的意義就是 Abstract data type
然後你不管這個抽象type X是什麼, 都有某些functions可針對它運作
例子中是 function  f: (X → int); 把抽象的X type 轉換成 Int

上面的T = ∃X { a: X; f: (X → int); }算是一個Abstract data type定義
就是一個interface 尚未implement
那麼實作會變成怎樣？
wiki上的例子是
intT = { a: int; f: (int → int); }Module T 用 Int實作, 因此原本裡面的抽象X type實現成Int type
此時 X ＝ Int, 然後 function f 實作上就是把 Int => Int

intT = { a: int; f: (int → int); } 本身就是subtype of  ∃X { a: X; f: (X → int); }
在Java 語法上你可以視為 intT = { a: int; f: (int → int); } extends ∃X { a: X; f: (X → int); }

那麼 Existential type 到底有什麼好處？
我剛剛有提到『你不管這個抽象type X是什麼, 都有某些functions可針對它運作』
主要目的就是讓抽象化的Type X獨立出來, 不管你實作給什麼
這些特定functions都可以運作

這樣講很抽象
我們來看看Scala更實際的例子

Existential types in Scala

比如說你今天想要寫一個函式來計算Array長度
Array的 element 可能位各種形態 比如Array[Int], Array[String]
你今天的目的就是：我根本不管List 的Element 是什麼, 我都要能計算它的size
你可能會很單純想到 Array[Any], 反正Scala所有class都extends Any嘛,
透過Polymorphism 來強迫吃任何Array 的element type

 scala> def foo(x : Array[Any]) = println(x.length);  
 foo: (Array[Any])Unit  
 scala> foo(Array[String]("foo", "bar", "baz"))  
 :6: error: type mismatch;  
  found  : Array[String]  
  required: Array[Any]  
     foo(Array[String]("foo", "bar", "baz"))  

沒想到一個Array[String] 就爆炸了
因為根本不type safe

好吧那麼我們在function階層改用type parameter [T]

 scala> def foo[T](x : Array[T]) = println(x.length)  
 foo: [T](Array[T])Unit  
 scala>> foo(Array[String]("foo", "bar", "baz"))  
 3  

看起來沒問題, 目標達成了！！
儘管還要多宣告一個type parameter [T]有點多餘, 但也無傷大雅
但是回到原本目的：我根本不管List 的Element 是什麼, 我都要能計算它的size

此時就要用Scala  Existential types來達成目標

 scala> def foo(x : Array[T] forSome { type T}) = println(x.length)  
 foo: (Array[T] forSome { type T })Unit  
 scala> foo(Array[String]("foo", "bar", "baz"))  
 3  

用Existential types之後如果你還有其他需求
比如你希望你的Existential type的bound 是CharSequence

 scala> def foo(x : Array[T] forSome { type T <: CharSequence}) = x.foreach(y => println(y.length))  
 foo: (Array[T] forSome { type T <: java.lang.CharSequence })Unit  
 scala> foo(Array[String]("foo", "bar", "baz"))  
 3  
 3  
 3  

Scala特別引進Existential types
就是讓Abstract data type 可以更進一步強化有 Upper and lower bounds

在更進一步細讀Scala  Existential type意義
因為我們種是有一些constructor M, 它本身不算是一個具體的Type
比如List, 你得給他List[String]它才算是一個真正的Type
M 還算停留在抽象階段
M[T] forSome { type T; }就是Existential types定義

M這個Module , 接受一個 type T 然後成為 M[T] type

然後 M 的一些function 就可以運作, 不管你給他T是什麼

比如 M.size(): Int

接著你還可以針對這存在的T , 做一些複雜限制

比如Array[T] forSome { type T <: Number; }
就是只接受數字型態的 T

這大概是Scala Existential types 的基本認知

那麼可以在想想當初Martin Odersky為什麼要引入Existential types
看看這一段

Scala needs existential types for essentially three things. The first is that we need to make some sense of Java's wildcards, and existential types is the sense we make of them. The second is that we need to make some sense of Java's raw types, because they are also still in the libraries, the ungenerified types. If you get a Java raw type, such as java.util.List it is a list where you don't know the element type. That can also be represented in Scala by an existential type. Finally, we need existential types as a way to explain what goes on in the VM at the high level of Scala. Scala uses the erasure model of generics, just like Java, so we don't see the type parameters anymore when programs are run. We have to do erasure because we need to interoperate with Java. But then what happens when we do reflection or want to express what goes on the in the VM? We need to be able to represent what the JVM does using the types we have in Scala, and existential types let us do that. They let you talk about types where you don't know certain aspects of those types.

基本上Scala是在JVM上的語言

1. JAVA有Wild-cards的應用, 因此Scala Existential types算是JAVA wild-cards的延伸
2. 有些type 是 raw type, 是半抽象階段比如List, Array等等得有 Existential types使其raw type 實際成為 " 真的存在的type " 可以進一步應用
3. 最後就是JVM的Type erase問題, 你定義的List[String], 事實上在JVM層級就不知道是甚麼type, Existential types讓我們在reflection時候可以知道原本Scala code用的是甚麼型態

Existential types syntax traps

Existential type在用的時候會有些typo導致有很大的結果誤差
比如

 Array[T] forSome { type T; }  
 Array[T forSome { type T; }]  

兩個看起來很像
但實際上的意義不一樣!!
第一個是各種type的 Array
第二個卻是Array[Any] !!