这本来是我在挖shapeless实现的时候,发现的Rúnar大神的旧博客中的内容,其中介绍了NatHList等结构在scala中的简单实现,不过是10年的内容,有点旧了,而且他一开始就假设读者对dependent type什么的都熟悉。我自己整理一下。

Dependent Types

在诸如Java这样的语言中,typevalue是完全分离,我们用type去标记一个value,为其添加约束,而且,我们往往是要预先定义它。

Dependent Types沟通了两个世界,Wikipedia上有

a dependent type is a type whose definition depends on a value. A “string” is a type. A “fixed-length string of length 5” is a dependent type because of the dependence on a value.

也就是说,dependent types是指type依赖于具体的value。通过加入这种功能,我们获得了

  • 由于类型依赖于具体的值,这就意味着,我们可以像计算值一样计算类型。

  • 我们可以构造出对值的类型的更强大更灵活的约束。

Example from Idris

如果你去看Idris的官网,能看到它的标志下面大大的A Language with Dependent Types。它自称

In Idris, types are a first class language construct, meaning that they can be computed and manipulated (and passed to functions) just like any other language construct.

看一个栗子

1
2
3
isSingleton : Bool -> Type
isSingleton True = Nat
isSingleton False = List Nat

恩,长得和Haskell差不多,这个函数接受Bool返回Type,但是其实他会返回NatList[Nat]两种不同的结果,也就是我们一般的函数是take a value and return a value,但是这种函数会take a value and return a type dependent with value。下面一个应用的栗子

1
2
3
mkSingle : (x : Bool) -> isSingleton x
mkSingle True = 0
mkSingle False = []

这里,mkSingle函数利用isSingleton函数通过x计算类型,当xTrue时,类型签名为Bool -> Nat,当xFalse时,类型签名为Bool -> List[Nat]。我们在类型声明的时候也可以做类型计算。

下面看一个利用dependent types来定义更强的类型约束的例子。

1
2
3
(++) : Vect n a -> Vect m a -> Vect (n + m) a
(++) Nil ys = ys
(++) (x :: xs) ys = x :: xs ++ ys

这里定义了++函数用来做Vector的加法,Vector有两个参数,第一个是长度,第二个是元素类型,也就是说,我们通过类型签名,不仅限制了实现返回的类型,还限制了返回的值的语义,这样编译器的编译的时候也会检查实现,是不是能满足这个要求了。是不是感觉很强大。

Path Dependent Types in Scala

Scala并是像Idris那样的full dependently typed language,只支持一定形式的dependent types

Path Dependent Types是指我们可以定义nested components。比如在一个trait里面定义class等等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Foo {
class Bar
}
val foo1 = new Foo
val foo2 = new Foo
val a: Foo# Bar = new foo1.Bar
val b: Foo# Bar = new foo2.Bar
val c: foo1.Bar = new foo1.Bar
// raise error
val d: foo2.Bar = new foo1.Bar

这里我们在Foo里面声明了Bar,我们有两种方法获取Foo中的Bar类型,通过Foo# Bar或者通过具体的实例中foo1.Bar,并且,不同Foo实例中的Bar是不同的。

Parameter Dependent Types in Scala

利用这种方法,我们也可以在一定程度上实现返回值类型依赖参数的效果。

1
2
3
4
5
6
trait Foo {
trait Bar
def value: Bar
}
def foo(f: Foo): f.Bar = f.value

再看一个,对泛型参数依赖要求的栗子。

Scala的标准库中有CanBuildFrom这个东西,大概长成下面的样子

1
2
3
trait CanBuildFrom[From, Elem, To] {
def apply ...
}

它表达的是集合类To关于元素类型Elem是不是可以从From这个集合类型构建。

对于一个可以包含任意类型的集合,他应该是由

1
2
3
4
implicit def regularCanBuildFrom[CC[_], A] =
new CanBuildFrom[CC[_], A, CC[A]] {
def apply ...
}

我们可以在console里面试一下

1
2
3
4
5
6
7
import scala.collection.generic._
// right
implicitly[CanBuildFrom[List[Int], String, List[String]]]
// error
implicitly[CanBuildFrom[List[String], Int, List[Double]]]

这里就能看出来,其实类型参数的最后一个参数是由前两个参数决定的,而这种实现方式就是通过提供隐式类型转化。

下面用矩阵的乘法做个例子。

我们都知道矩阵相乘应该有。

Matrix * Matrix => Matrix

Matrix * Vector => Vector

Matrix * Int => Matrix

Int * Matrix => Matrix

不可能出现

Matrix * Vector => Matrix

这种情况下,可以这样搞

1
2
3
4
5
6
7
8
9
10
11
12
13
trait Matrix // Dummy definitions for expository purposes
trait Vector
trait MultDep[A, B, C]
implicit object mmm extends MultDep[Matrix, Matrix, Matrix]
implicit object mvv extends MultDep[Matrix, Vector, Vector]
implicit object mim extends MultDep[Matrix, Int, Matrix]
implicit object imm extends MultDep[Int, Matrix, Matrix]
def mult[A, B, C](a: A, b: B)
(implicit instance: MultDep[A, B, C]): C =
sys.error("TODO")

这样,每次在调用函数的时候,都回去寻找对应的implicit instance这个参数,不过我们不定义对应的类型,就不可能通过编译。保证了函数的安全。然后我们在诸如imm``mim中提供真正的计算过程,然后在mult中调用。看起来是不是很靠谱。

到这里可能有人会说,这东西直接重载不就好了,重载了对应的类型,没有重载函数当然就不能通过编译了。

恩,对于有同时具有OO中常见的重载以及FP特性的Scala来说,这种写法确实没有那么明细的优势,尤其是当类型推断坑爹的时候。不过,回想之前那个Idris的例子,如果,我们对于矩阵和向量的长度也做要求呢?希望形状不对应的矩阵不能相乘,一般的矩阵库这都会是运行时错误,我们有办法把它提到编译时,在类型参数也加上一个Nat就行了。而,shapeless库就提供了这些功能。也是我们真正感兴趣的部分。不过,我们还需要更多的基础知识。

Abstract Types

scala中在实现Parametric polymorphism的时候,不只可以像C++Java一样在类型声明上写,还可以在类型中声明

1
2
3
4
5
6
7
8
trait Foo[T]{
def foo: T
}
trait Foo1 {
type T
def foo: T
}

考虑到之前Dependent Types的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
trait Foo {
type T
def value: T
}
object FooString extends Foo {
type T = String
def value: T = "hehe"
}
object FooInt extends Foo {
type T = Int
def value: T = 1
}
def getValue(f: Foo): f.T = f.value
val fs: String = getValue(FooString)
val fi: Int = getValue(FooInt)

这种写法,在之前的那个Parser的例子中就见过,利用这种方法在子类中填充InputElem的具体类型,在父类中实现统一的方法。这个例子更明显的体现了用处,getValue的类型签名是写不出来的。通过具体的参数才会具体化。

这里要强调的一点是type is not an alias,这并不像是c++typedef那种。常见的一种用途,就是在Scalaz里面见到

1
type Result[T] = Either[String, T]

这样就可以把这个类型扔给诸如

1
def get[T](Monad[T]): T

这种类型的函数去了。

Infix Operator

这个只能算是Scala语法的一个TipScala中可以省略括号

1
2
3
4
5
6
object Foo {
def bar(s: String) = println(s)
}
Foo.bar("Hello")
Foo bar "Hello"

对于类型也是一样,之前在ADT这一篇里面见识过,一个代数类型可以看做作为其参数的基本类型的函数,返回新的类型。

1
2
3
4
trait Foo[A, B]
Foo[Int, String]
Int Foo String

同时,我们知道Scala中符号可以用来定义变量,同样符号也可以用来定义类型,并且两者没有冲突。

1
2
3
4
trait ::[A, B]
::[Int, String]
Int :: String

这里是不是看出来了点Heterogeneous Lists的影子。

Phantom Types

Phantom Types我们在之前已经见识过了,所谓的Phantom就是指它没有实例化,我们只是借用这个类型表达一些语义,之前的MatrixCanBuildFrom都是很好的例子。

这里再看一个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
trait Status
trait Open extends Status
trait Closed extends Status
trait Door[S <: Status]
object Door {
def apply[S <: Status] = new Door[S]{}
def open[S <: Closed](d: Door[S]) = Door[Open]
def close[S <: Open](d: Door[S]) = Door[Closed]
}
val closedDoor = Door[Closed]
val openDoor = Door.open(closedDoor)
val closedAgainDoor = Door.close(openDoor)

这里利用OpenClosed来保证,我们只能打开已经关上的门,和只能关上已经打开的门,而且是在__编译时__,而不是在运行时返回错误甚至是抛异常。

Implicit Parameters and Implicit Conversions

这个在之前那个矩阵的例子中,就是利用隐式参数,来实现约束的,这个套路在很多地方都使用,比如在Future的实现中,就是依靠隐式参数指定ExecutionContext的。

看个小例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
trait Resolver[T, R] {
def resolve(t: T): R
}
object Resolver {
implicit val ib: Resolver[Int, Boolean] = new Resolver[Int, Boolean] {
def resolve(i :Int): Boolean = i > 1
}
implicit val sd: Resolver[String, Double] = new Resolver[String, Double] {
def resolve(i :String): Double = i.length.toDouble
}
}
def foo[T, R](t: T)(implicit p: Resolver[T, R]): R = p.resolve(t)
val res1: Boolean = foo(3)
val res2: Double = foo("ciao")

这就是像我在Matrix中说的,利用隐式参数在编译时选择合适的方法。不过这个例子展示了在部分类型已知的情况下的隐式参数。

Type Classes

这个直接看原论文吧。

还有这篇Generics of a Higher Kind

Implicitly and Type Equality

类型同样是可以进行比较的,

比较两个类型相同很简单,就是=:=

1
implicitly[Int == Int]

对于继承关系的约束可以通过<:<

1
implicitly[Int <:< Any]

最后一个是在view的约束,即表明A 可以看做 B。不过<%<运算符已经在scala 2.9之后废弃掉了。所以我们要自己造一个

1
2
3
4
5
6
sealed abstract class <%<[-From, +To] extends (From => To)
with Serializable
object <%< {
implicit def conformsOrViewsAs[A <% B, B]: A <%< B =
new (A <%< B) {def apply(x: A) = x}
}

然后我们自己试一下

1
2
3
4
5
6
7
8
9
case class A(i: Int) {}
case class B(s: String) {}
implicit def a2b(a: A): B = new B(a.i.toString)
// correct
implicitly[A <%< B]
// Error: could not find implicit value for parameter
implicitly[B <%< A]

至此,预备知识都复习了一遍。之后就可以好好学习一个了。




X