Scalaz（27）－ Inference & Unapply ：类型的推导和匹配

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

经过一段时间的摸索，用scala进行函数式编程的过程对我来说就好像是想着法儿如何将函数的款式对齐以及如何正确地匹配类型，真正是一种全新的体验，但好像有点太偏重学术型了。本来不想花什么功夫在scala的类型系统上，但在阅读scalaz源代码时往往遇到类型层面的编程（type level programming），常常扰乱了理解scalaz代码思路，所以还是要简单的介绍一下scala类型系统的一些情况。scala类型系统在scala语言教材中一般都提及到了。但有些特殊的类型如phantom type, dependent type等，以及在一些场合下使用类型的特殊技巧还是值得研究的。scala类型系统的主要功能就是在程序运行之前，在编译时（compile time）尽量捕捉代码中可能出现的错误，也就是类型不匹配错误。scala类型系统是通过找寻隐式转换类型证例（implicit type evidence）来判断代码中当前类型是否期待的类型从而确定是否发生类型错误（type error）。写起来很简单，我们只要用隐式参数（implicit parameter）来表述一个隐式的类型实例（implicit type instance）：

trait Proof
def sayHi(implicit isthere: Proof) = println("hello")
sayHi //编译失败

创建一个Proof实例后：

trait Proof
def sayHi(implicit isthere: Proof) = println("hello")
//> sayHi: (implicit isthere: Exercises.deptype.Proof)Unit
implicit object ishere extends Proof //建一个实例
sayHi //> hello

sayHi现在能正常通过编译了。虽然在sayHi函数内部并没有引用这个隐式参数isthere，但这个例子可以说明编译器进行类型推断的原理。一般来说我们都会在函数内部引用isthere这种隐式参数，并且按不同需要在隐式转换解析域内创建不同功能的类型实例（instance）：

trait Proof { def apply(): String}
def sayHi(implicit isthere: Proof) = println(isthere())
//> sayHi: (implicit isthere: Exercises.deptype.Proof)Unit
implicit object ishere extends Proof {def apply() = "Hello World!"}
sayHi //> Hello World!

在Scalaz中还有些更复杂的引用例子如：scalaz/BindSyntax.scala

def join[B](implicit ev: A <~< F[B]): F[B] = F.bind(self)(ev(_))

List(List(),List(),List()).join //> res0: List[Int] = List(1, 2, 3)
//List(1.some,2.some,3.some).join //无法编译，输入类型不对

以上例子里的隐式转换和解析域就比较隐晦了：scalaz/Liskov.Scala

trait LiskovFunctions {
import Liskov._ /**Lift Scala's subtyping relationship */
implicit def isa[A, B >: A]: A <~< B = new (A <~< B) {
def subst[F[-_]](p: F[B]): F[A] = p
}

这个隐式转换产生的实例限定了A必须是B或者是B的子类。在这个例子中不但限定了类型的正确性，而且还进行了些类型关系的推导。理论上我们可以用依赖类型（dependent type）来描述类型参数之间的关系，推导结果类型最终确定代码中类型的正确无误。据我所知scala并不支持完整功能的依赖类型，但有些前辈在scala类型编程（type level programming）中使用了一些依赖类型的功能和技巧。Scalaz的unapply就利用了依赖类型的原理，然后通过隐式参数（implicit parameter）证明某些类型实例的存在来判断输入参数类型正确性的。Unapply的构思是由Miles Sabin创造的。我们先用他举的一个例子来看看如何利用依赖类型及类型实例通过隐式输入参数类型来推导结果类型并判断输入参数类型正确性的：

trait TypeA
trait TypeB trait DepType[A,B,C] //依赖类型
implicit object abb extends DepType[TypeA,TypeB,TypeB] {
def apply(a:TypeA, b:TypeB): TypeB = error("TODO") //结果类型依赖TypeA和TypeB
}
implicit object aaa extends DepType[TypeA,TypeA,TypeA] {
def apply(a:TypeA, b:TypeA): TypeA = error("TODO") //结果类型依赖TypeA和TypeA
}
implicit object iab extends DepType[Int,TypeA,TypeB] {
def apply(a:Int, b:TypeA): TypeB = error("TODO") //结果类型依赖Int和TypeB
}
implicit object bbi extends DepType[TypeB, TypeB, Int] {
def apply(a:TypeB, b:TypeB): Int = error("TODO") //结果类型依赖Int和TypeB
}
implicitly[DepType[Int,TypeA,TypeB]] //> res1: Exercises.deptype.DepType[Int,Exercises.deptype.TypeA,Exercises.deptyp
//| e.TypeB] = Exercises.deptype$$anonfun$main$1$iab$2$@7722c3c3
implicitly[DepType[TypeB,TypeB,Int]] //> res2: Exercises.deptype.DepType[Exercises.deptype.TypeB,Exercises.deptype.Ty
//| peB,Int] = Exercises.deptype$$anonfun$main$1$bbi$2$@2ef3eef9 implicitly[DepType[TypeA,TypeB,TypeB]] //> res3: Exercises.deptype.DepType[Exercises.deptype.TypeA,Exercises.deptype.T
//| ypeB,Exercises.deptype.TypeB] = Exercises.deptype$$anonfun$main$1$abb$2$@24
//| 3c4f91
implicitly[DepType[TypeA,TypeA,TypeA]] //> res4: Exercises.deptype.DepType[Exercises.deptype.TypeA,Exercises.deptype.T
//| ypeA,Exercises.deptype.TypeA] = Exercises.deptype$$anonfun$main$1$aaa$2$@29
//| 1ae
//implicitly[DepType[TypeA,TypeA,TypeB]] //无法通过编译 could not find implicit value for parameter e: Exercises.deptype.DepType[Exercises.deptype.TypeA,Exercises.deptype.TypeA,Exercises.deptype.TypeB] def checkABC[A,B,C](a: A, b: B)(implicit instance: DepType[A,B,C]): C = error("TODO")
//> checkABC: [A, B, C](a: A, b: B)(implicit instance: Exercises.deptype.DepTyp
//| e[A,B,C])C
/*
val v_aaa: TypeA = checkABC(new TypeA{},new TypeA{})
val v_iab: TypeB = checkABC(1,new TypeA{})
val v_bbi: Int = checkABC(new TypeB{},new TypeB{})
val v_aab: TypeB = checkABC(new TypeA{}, new TypeA{}) //ype mismatch; found : Exercises.deptype.TypeA required: Exercises.deptype.TypeB
*/

以上例子利用依赖类型的类型关系实现了类型推导和验证。

函数式编程重视概括抽象以方便函数组合从而实现高度的代码重复使用。因为我们在进行函数式编程时最常遇到的类型款式是这样的：F[A]，所以我们在设计函数时会尽量对函数的参数进行针对F[A]的概括。但这样也会对函数的使用者提出了苛刻要求：在调用函数时必须按照要求传人F[A]类型的参数，实际上又限制了函数的通用。Scalaz里的Unapply类型可以把许多不同款式的类型对应成抽离的F[]，A和TC。其中TC是个typeclass，用来引导编译器进行类型推导。Unapply trait 如下：scalaz/Unapply.scala

trait Unapply[TC[_[_]], MA] { /** The type constructor */
type M[_] /** The type that `M` was applied to */
type A /** The instance of the type class */
def TC: TC[M] /** Evidence that MA =:= M[A] */
def leibniz: MA === M[A] /** Compatibility. */
@inline final def apply(ma: MA): M[A] = leibniz(ma)
}

从定义上分析：Unapply把MA拆分出M[]和A，但使用者必须提供TC - 一个施用在A的typeclass。

好了，我们先用一个简单的例子来分析使用Unapply的背景和具体方式：

class TypeWithMap[F[_],A](fa: F[A])(implicit F: Functor[F]) {
def doMap[B](f: A => B) = F.map(fa)(f)
} val mapList = new TypeWithMap(List(,,)) //> mapList : Exercises.unapply.TypeWithMap[List,Int] = Exercises.unapply$$anon
//| fun$main$1$TypeWithMap$1@1d9b7cce
mapList.doMap {_ + } //> res2: List[Int] = List(2, 3, 4)

在这个例子里我们通过传入一个F[A]类型来创建一个TypeWithMap类型实例, F是个Functor。如果我们传入一个List, 因为List的类型款式是F[A]的，所以编译器顺利地把F[A]拆解成F[_]和A, 在例子里就是List和Int。那么如果我们试着传入一个Function1[Int,Int]呢？

val mapFunc = new TypeWithMap( (_: Int) * )
//- not enough arguments for constructor TypeWithMap: (implicit F: scalaz.Functor[Any])Exercises.unapply.TypeWithMap[Any,A]. Unspecified value parameter F.
//- could not find implicit value for parameter F: scalaz.Functor[Any]

这个东西根本过不了编译。主要是编译器不晓得如何把Function1[A,A]对应成F[A]。我们试试手工把类型款式对应关系提供给编译器：

val mapFunc2 = new TypeWithMap[({type l[x] = Function1[Int,x]})#l,Int]((_: Int) * )
//> mapFunc2 : Exercises.unapply.TypeWithMap[[x]Int => x,Int] = Exercises.unapp
//| ly$$anonfun$main$1$TypeWithMap$1@15ff3e9e
mapFunc2.doMap {_ + }() //> res3: Int = 5

看来没问题，不过手工写的还是有点复杂。Unapply是通过提供多种款式的类型隐式转换实例（implicit instance）来进行类型匹配再分拆的。在上面的例子里Unapply提供了这么个款式的类型实例：

/**Unpack a value of type `M0[A0, B0]` into types `[b]M0[A0, b]` and `B`, given an instance of `TC` */
implicit def unapplyMAB2[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[A0, α]})#λ]): Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
} = new Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
def TC = TC0
def leibniz = refl
}

这不就是我们例子的类型款式嘛。那我们看用Unapply能不能免去手工提供类型提示：

class TypeWithMap[F[_],A](fa: F[A])(implicit F: Functor[F]) {
def doMap[B](f: A => B) = F.map(fa)(f)
}
object TypeWithMap {
def apply[T](t: T)(implicit U: Unapply[Functor, T]) =
new TypeWithMap[U.M,U.A](U.apply(t))(U.TC)
}
val umapList = TypeWithMap(List(,,)) //> umapList : Exercises.unapply.TypeWithMap[[X]List[X],Int] = Exercises.unappl
//| y$$anonfun$main$1$TypeWithMap$2@42e99e4a
umapList.doMap {_ + } //> res2: List[Int] = List(2, 3, 4)
val umapFunc = TypeWithMap((_: Int) * ) //> umapFunc : Exercises.unapply.TypeWithMap[[X]Int => X,Int] = Exercises.unapp
//| ly$$anonfun$main$1$TypeWithMap$2@32eff876
umapFunc.doMap {_ + }() //> res3: Int = 5

看，不用我们提示编译器，但我们必须提供TC的类型，在这里是Functor。注意：这里我们是对任意类型T进行分拆的。实际上U.apply(t)把T转换成了U.M[U.A]，看看Unapply的这段源代码：

/** Evidence that MA =:= M[A] */
def leibniz: MA === M[A] /** Compatibility. */
@inline final def apply(ma: MA): M[A] = leibniz(ma)

从这里实现了MA >>> M[A]的转换。
当我看到用Unapply使Int这样的简单类型也能转换成M[A]时觉得挺新鲜。看看traverse操作：

Applicative[Option].traverse(List(,,))(a => (a + ).some)
//> res6: Option[List[Int]] = Some(List(2, 3, 4))

traverse函数的款式是这样的:

final def traverse[G[_], B](f: A => G[B])(implicit G: Applicative[G]): G[F[B]]

G是个Applicative，它的类型款式当然是G[B]这样的了，也就是我们必须提供f: A => G[B]这样的函数款式。但如何解释以下这句：

Monoid[Int].applicative.traverse(List(,,))(a => a + )
//> res7: Int = 9

也就是说scalaz在什么地方把基本类型Int转换成了G[B]这么个款式。从Unapply源代码里查了一下，找到了这段：

sealed trait Unapply_4 {
// /** Unpack a value of type `A0` into type `[a]A0`, given a instance of `TC` */
implicit def unapplyA[TC[_[_]], A0](implicit TC0: TC[({type λ[α] = A0})#λ]): Unapply[TC, A0] {
type M[X] = A0
type A = A0
} = new Unapply[TC, A0] {
type M[X] = A0
type A = A0
def TC = TC0
def leibniz = refl
}
}

这就解释了上面的可能。当然在Unapply.scala几百行的源代码中提供了大量不同类型款式的隐式转换实例，大家可以在有需要的时候查找合适的分拆实例。下面我们再分析一个稍微复杂点的例子：假如我们想写个针对List的sequence操作函数：

def sequenceList[G[_], A](lga: List[G[A]])(implicit G: Applicative[G]): G[List[A]] =
lga.foldRight(List[A]().point[G])((a,b) => G.apply2(a,b){_ :: _})
//> sequenceList: [G#7905958[_#7912581], A#7905959](lga#7912582: List#3051[G#79
//| 05958[A#7905959]])(implicit G#7912583: scalaz#31.Applicative#28655[G#790595
//| 8])G#7905958[List#3051[A#7905959]]
val lli = List(List(),List(,),List()) //> lli : List#8636[List#8636[Int#1125]] = List(List(1), List(2, 3), List(4))
val los = List("a".some,"b".some,"c".some) //> los : List#8636[Option#1959[String#248]] = List(Some(a), Some(b), Some(c))
//|
sequenceList(lli) //> res6: List#8636[List#3051[Int#1125]] = List(List(1, 2, 4), List(1, 3, 4))
sequenceList(los) //> res7: Option#1959[List#3051[String#248]] = Some(List(a, b, c))

这个sequenceList函数对任何List[G[A]]这种传入的类型款式都可以处理。但如果出现这样的东西呢？

val lether = List(.right[String],.right[String],.right[String])
sequenceList(lether) //....required: List#3051[?G[?A]]

过不了编译。看这个错误提示[?G[?A]]，实际上编译器期待的是个F[G[A]]款式的输入参数但我们提供的是个F[G[A,B]]这么个款式，把编译器搞糊涂了。我们试着给它点提示：

val lether = List(.right[String],.right[String],.right[String])
//> lether : List#8636[scalaz#31.\/#32660[String#17383,Int#1125]] = List(\/-(1
//| ), \/-(2), \/-(3))
//sequenceList(lether) //....required: List#3051[?G[?A]]
sequenceList[({type l[x] = \/[String,x]})#l,Int](lether)
//> res8: scalaz#31.\/#32660[String#248,List#3051[Int#1125]] = \/-(List(1, 2, 3
//| ))

这样就可以了。那么在Unapply里有没有适合的款式呢？看看：

/**Unpack a value of type `M0[A0, B0]` into types `[a]M0[a, B0]` and `A`, given an instance of `TC` */
implicit def unapplyMAB1[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[α, B0]})#λ]): Unapply[TC, M0[A0, B0]] {
type M[X] = M0[X, B0]
type A = A0
} = new Unapply[TC, M0[A0, B0]] {
type M[X] = M0[X, B0]
type A = A0
def TC = TC0
def leibniz = refl
} /**Unpack a value of type `M0[A0, B0]` into types `[b]M0[A0, b]` and `B`, given an instance of `TC` */
implicit def unapplyMAB2[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[A0, α]})#λ]): Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
} = new Unapply[TC, M0[A0, B0]] {
type M[X] = M0[A0, X]
type A = B0
def TC = TC0
def leibniz = refl
}

好像unapplMFAB1,unapplMFAB2这两个实例都行。试试：

//val u1 = Unapply.unapplyMAB1[Applicative, \/, String, Int] //这个不行
//could not find implicit value for parameter TC0: scalaz#31.Applicative#28655[[α#75838]scalaz#31.\/#32660[α#75838,Int#1125]]
val u2 = Unapply.unapplyMAB2[Applicative, \/, String, Int] //这个可以
//> u2 : scalaz#31.Unapply#32894[scalaz#31.Applicative#28655,scalaz#31.\/#3266
//| 0[String#17383,Int#1125]]{type M#9842257[X#9842258] = scalaz#31.\/#32660[St
//| ring#17383,X#9842258]; type A#9842259 = Int#1125} = scalaz.Unapply_0$$anon$
//| 13@47eaca72
sequenceList[u2.M,u2.A](lether) //> res9: Exercises#29.unapply#17810.u2#9836539.M#9842257[List#3051[Exercises#2
//| 9.unapply#17810.u2#9836539.A#9842259]] = \/-(List(1, 2, 3))

不过需要我们人工判定那个款式才合适。我们可以充分利用Unapply来编写一个更概括的sequenceList函数：

def sequenceListU[GA](lga: List[GA])(implicit U: Unapply[Applicative, GA]): U.M[List[U.A]] =
sequenceList[U.M,U.A](U.leibniz.subst(lga))(U.TC)
//> sequenceListU: [GA#10927512](lga#10936796: List#3051[GA#10927512])(implicit
//| U#10936797: scalaz#31.Unapply#32894[scalaz#31.Applicative#28655,GA#1092751
//| 2])U#10936797.M#65840[List#3051[U#10936797.A#65842]]
sequenceListU(lli) //> res10: List#8636[List#8636[Int#1125]] = List(List(1, 2, 4), List(1, 3, 4))
sequenceListU(los) //> res11: Option#1959[List#8636[String#248]] = Some(List(a, b, c))
sequenceListU(lether) //> res12: scalaz#31.\/#32660[String#248,List#8636[Int#1125]] = \/-(List(1, 2,
//| 3))
sequenceListU(List(,,)) //> res13: Int#1125 = 6

这个函数够概括的了。主要是通过leibeniz.subst把List[GA]转换成List[G[A]], 我们看看subst的源代码：

sealed abstract class Leibniz[-L, +H >: L, A >: L <: H, B >: L <: H] {
def apply(a: A): B = subst[Id](a)
def subst[F[_ >: L <: H]](p: F[A]): F[B]
...

不要慌，注意下面这两段代码：

/** Evidence that MA =:= M[A] */
def leibniz: MA === M[A] implicit def subst[A, B](a: A)(implicit f: A === B): B = f.subst[Id](a)

leibniz返回 MA === M[A], subst 传入 A 返回 B。A >>>GA, B>>>G[A]。这样上面例子中的U.leibniz.subst(lga)就把List[GA]转换成了List[G[A]]。

Scalaz（27）－ Inference & Unapply ：类型的推导和匹配的更多相关文章

item 1：理解template类型的推导
本文翻译自modern effective C++,由于水平有限,故无法保证翻译完全正确,欢迎指出错误.谢谢! 一些用户对复杂的系统会忽略它怎么工作,怎么设计的,但是很高兴去知道它完成的一些事.通过这 ...
c++ lambda返回类型自动推导的一些需要注意的地方
一句话,lambda返回类型自动推导走的是auto,而不是decltype,注意. class ObjectA { public: ObjectA() { val_ = ++g; } ObjectA( ...
Parse Fatal Error at line 41 column 24&colon; 元素类型 &quot&semi;url-pattern&quot&semi; 必须由匹配的结束标记 &quot&semi;&lt&semi;/url-pattern&gt&semi;&quot&semi; 终止
1.错误描述严重: Parse Fatal Error at line 41 column 24: 元素类型 "url-pattern" 必须由匹配的结束标记 "&lt ...
解决：org&period;xml&period;sax&period;SAXParseException&colon; 元素类型 &quot&semi;head&quot&semi; 必须由匹配的结束标记 &quot&semi;&lt&semi;/head&gt&semi;问题
事件背景: 今天就碰到了这样的问题, org.xml.sax.SAXParseException: 元素类型 "head" 必须由匹配的结束标记 "</head&g ...
元素类型 &OpenCurlyDoubleQuote;meta” 必须由匹配的结束标记 &OpenCurlyDoubleQuote;” 终止
报错 org.xml.sax.SAXParseException: 元素类型 “meta” 必须由匹配的结束标记 “” 终止系统自动创建 <meta charset="UTF-8&q ...
概念端类型&OpenCurlyDoubleQuote;xxx”中的成员&OpenCurlyDoubleQuote;ID”的类型&OpenCurlyDoubleQuote;Edm&period;Decimal”与对象端类型&OpenCurlyDoubleQuote;xxx”中的成员&OpenCurlyDoubleQuote;ID”的类型&OpenCurlyDoubleQuote;System&period;Int64”不匹配
概念端类型“xxx”中的成员“ID”的类型“Edm.Decimal”与对象端类型“xxx”中的成员“ID”的类型“System.Int64”不匹配使用EF实体模型映射之后将edmx中xml映射关系中 ...
org&period;xml&period;sax&period;SAXParseException&colon; 元素类型 &quot&semi;input&quot&semi; 必须由匹配的结束标记 &quot&semi;&lt&semi;/input&gt&semi;&quot&semi; 终止。
错误记录 Spring Boot推荐使用thymeleaf作为视图,按照SpringBoot实战一书的案例写Demo. 发生错误: org.xml.sax.SAXParseException: 元素类 ...
item 2&colon; 理解auto类型的推导
本文翻译自modern effective C++,由于水平有限,故无法保证翻译完全正确,欢迎指出错误.谢谢! 博客已经迁移到这里啦如果你已经读过item 1的模板类型推导,你已经知道大部分关于au ...
C++ 11 学习1：类型自动推导 auto和decltype
Cocos 3.x 用了大量的C++ 11 的东西,所以作为一个C++忠实粉丝,有必要对C++ 11进行一个系统的学习. 使用C++11之前,一定要注意自己使用的编译器对C++11的支持情况,有些编译 ...

随机推荐

Oracle操作
1.查询表空间地址: select name from v$datafile; 2.创建表空间: create tablespace yysspace datafile ‘D:\APP\MIAO\OR ...
wheel和staff分组
1.只有属于wheel组的用户才可以用su登录为root 2. 具体设置步骤如下: 1)修改 /etc/pam.d/su 文件,找到"#auth required /lib/security ...
AngularJS中的http拦截
$http服务允许我们与服务端交互,有时候我们希望在发出请求之前以及收到响应之后做些事情.即http拦截. $httpProvider包含了一个interceptors的数组. 我们这样创建一个int ...
【PRML读书笔记-Chapter1-Introduction】1&period;1 Example&colon;Polynomial Curve Fitting
书中给出了一个典型的曲线拟合的例子,给定一定量的x以及对应的t值,要你判断新的x对应的t值多少. 任务就是要我们去发现潜在的曲线方程:sin(2πx) 这时就需要概率论的帮忙,对于这种不确定给t赋何值 ...
C++ 构造函数放置默认转换explicit关键字（2）
按照默认规定,只有一个参数的构造函数也定义了一个隐式转换,将该构造函数对应数据类型的数据转换为该类对象,如下面所示: class String { String ( const char* p ); ...
DNS协议实践
根据DNS协议发送UDP请求,然后获取IP地址头文件: #ifndef __DNS__ #define __DNS__ #include <stdio.h> #include <s ...
python 安装scrapy
1. 首先你先得安装PYTHON...还是推荐2.7吧,之前装了3.3似乎和这个世界格格不入...先装个2.7. 并将python加入系统的环境变量. 2. 去scrapy 官网下载最新版本的scra ...
教你50招提升ASP&period;NET性能（十七）：不要认为问题只会从业务层产生
(28)Don’t assume that problems can only arise from business logic 招数28: 不要认为问题只会从业务层产生 When beginnin ...
邂逅python
你很美幸运遇见你很幸运,能在现在这么多繁杂的语言中选择python.初识python是在2016年的七月.大二学期刚刚结束,留在学校准备学点东西.刚好听同学说下学期要学习python,所以决定要学 ...
echarts对每个data[i]的图片添加点击事件
1.综述:以饼图为例,只需要对echarts对象option添加以下几行代码即可 //添加点击事件(单击),还有其他鼠标事件和键盘事件等等 myChart1.on("click", ...