《Haskell语言中的泛型编程实用方法》

《理论计算机科学电子笔记》第41卷第1期（2001年）网址：http://www.elsevier.nl/locate/entcs/volume41.html31页可派生类型类Ralf Hinze1波恩第三大学信息学院Rüomerstrafte164，53117Bonn，Germany西蒙·佩顿·琼斯微软研究有限公司地址：1 Guildhall St Cambridge CB23NH，England摘要泛型编程允许你写一个函数一次，并在不同的类型上多次使用它。在泛型编程方面已经做了很多很好的基础工作。本文的目标是提出一种在Haskell语言中支持泛型编程的实用方法，而不从根本上改变语言或其类型系统。其核心思想是将泛型编程作为一种更丰富的语言，在类声明中编写默认方法定义。在此过程中，我们遇到了一个单独的问题，关于涉及更高类型的类型类重载。我们提出了一个简单的类型类系统扩展，允许程序员编写更丰富的上下文比目前可能的。1介绍泛型或多型函数是程序员编写一次，但可以在许多不同的数据类型上工作的函数。标准的例子是解析和打印、序列化、取相等、排序、散列等等。在泛型编程方面有很多工作[2，8，1，6]。在本文中，我们提出了一个扩展的设计和实现Haskell，支持泛型编程。乍一看，Haskell的类型类似乎但我们有1电邮地址： ralf@informatik.uni-bonn.de2电子邮件地址：simonpj@microsoft.com2000年1月，出版社dbyElsevierScienceB。 V. 操作访问和C CBYNCND许可证。欣兹和佩顿·琼斯2→→我发现它们可以非常优雅地组合在一起，从而实现对Haskell的平滑向上扩展。在这个过程中，我们描述了一个正交的，但互补的想法。Haskell允许定义更高阶的kinded数据类型，例如，一个相等实例。 这似乎是不幸的：语言的一部分比另一部分更强大。我们描述了一个适度的扩展Haskell更具体地说，我们的贡献如下：我们介绍了支持泛型编程的Haskell扩展的语言设计（第2-6节）。泛型函数只出现在类声明中。我们描述了一个完全独立的扩展，它允许人们为Haskell 98中简单不可表达的高阶kind数据类型编写某些实例声明（第7节）。我们讨论这两部分的实现。本文的第一部分是[4]的后续工作;新的成就在第8节中详细介绍。2设置场景在本节中，我们为我们的建议设定了背景。我们首先回顾Haskell2.1类型类重载简介Haskell支持基于类型类的重载。例如，Prelude定义了类Eq：类等式t，其中（ ），（/）：：t→t→Bool。这定义了两个重载的顶级函数，（）和（/），它们的类型是（），（/）：：（Eq t）t→t→Bool。在我们可以对值使用（）之前，比如说Int，我们必须解释如何在Int值上取相等：实例Eq Int，其中（）=eqInt（/）= neInt.这里我们假设eqInt：：Int Int Bool和类似的neInt是从某个地方提供的。实例声明说欣兹和佩顿·琼斯3///我们怎样才能使两个值相等呢？大概是通过比较它们的组件;但这需要组件类型的相等性实例（Eq a，Eq b）<$Eq（a，b）其中（x1，y1）（x2，y2）=（x1x2）<$（y1y2）（x1，y1）/（x2，y2）=（x1/x2）<$（y1/ y2）。不断地为（）方法编写代码是有点烦人的，因为它只是（）方法代码的否定，所以Haskell允许你在类声明中编写一个默认方法类等式t，其中（），（/）：：t→t→Bool x1/x2=not（x1x2）.现在，如果你给出一个Eq的实例声明，它缺少（）的定义，Haskell所以我们可以这样写：实例（Eq a，Eq b）<$Eq（a，b）其中（x1，y1）（x2，y2）=（x1x2）<$（y1y2）得到和以前一样的效果。您甚至可以为这两种方法指定一个默认方法：类等式t，其中（ ），（/） ：： t→t→布尔x1x2=非（x1/x2）x1/x2=非（x1x2）。在一个实例声明中，你现在可以给（）一个定义，或者给（）一个定义，或者两者都给。如果你没有指定，那么你将得到一个无限循环，不幸的是！如果你给出了一个实例声明，但没有为方法op指定代码，并且类没有默认的op方法，那么调用该方法将停止程序并显示错误消息。这不是一个编译时错误;有时一个方法2.2重载不是泛型编程Haskell目前不支持泛型或多型编程。特别是，假设你定义了一个新的数据类型：dataWibble = Wag Int|伍格布尔如何在Wibble上实现相等是然而，在Haskell中，你必须给出一个显式的欣兹和佩顿·琼斯4实例声明，包含代码欣兹和佩顿·琼斯5平等：实例Eq Wibble，其中（ Wagi1 ） （ Wagi2 ） =i1i2（ Wugb1 ）（Wugb2 ）=b1b2w1w2=Fals e.生成这类样板代码是如此令人厌烦，以至于Haskell为一些内置类提供了特殊的支持--所谓的特别是，对于EQ，dataWibble=Wag Int| WugBool推导（方程式）。“派生（Eq）”部分告诉Haskell生成“明显的“明显”的意思在语言定义的附录中非正式地规定了[15]。这是相当特别的，特别是它只适用于一组固定的内置类（Eq，Ord，Enum，Bounded，Read，Show和Ix）。2.3通用默认方法因此，我们所寻求的是一种自动机制，它为实例声明的方法“填充”一个合适的实现。但是等一下！这就是默认方法的作用！确实如此，但是，正如我们已经重新标记的那样，默认方法太弱了.如果我们只写实例Eq Wibble如前所述，我们会得到一个无限循环。我们必须在某个地方提供一些真正的代码！我们想要的是一种更丰富的语言来编写默认方法。这就是我们现在要关注的3一般定义从语言设计的角度来看，我们的故事是这样的：为类声明中的默认方法定义提供更丰富的语言，提供了一种优雅的方式来扩展Haskell的泛型编程能力。我们将在第9节中更充分地证明这一说法，但首先我们必须提出我们的 设计。欣兹和佩顿·琼斯6/3.1两个例子我们对[4]中的建议作了微小的修改。有两个例子可以说明这一点。首先，这里是用一般等式扩充的Eq类：类等式t，其中（ ），（/）：： t→t→布尔--通用默认方法（）{1}Unit Unit=True（）{a+b}（Inlx1）（Inlx2）=x1x2（）{a+b}（Inry1）（Inry2）=y1y2（）{a+b}=False（）{ab}（x1：：y1）（x2：：y2）=x1x2y1y2-- vanilla，非泛型默认方法（/）x1x2=非（x1x2）。这个新的类声明包含一个普通的默认声明for（），就像以前一样。新特性是对相等的通用定义，由左侧的花括号区分，花括号包含一个类型参数。我们将在4.2节中更详细地研究这些一般定义。现在，我们简单地观察到泛型定义通过归纳作用于类被实例化的类型的结构（用花括号写）。现在我们可以给出一个这样的实例声明：实例Eq Wibble而不给出任何一种方法的代码。这两个方法都将 普通的、非泛型的默认方法（/），已填充一字不差通用默认方法（）以我们将描述的方式专门化，基本上给出了2.2节中的代码。也就是说，实例声明的结果就像我们编写的实例Eq Wibble，其中（ Wagi1 ） （ Wagi2 ） =i1i2（Wugb1 ）（ Wugb2 ）=b1b2w1w2=Falsew1/w2=不（w1w2）。这是另一个例子。Binary类有showBin和readBin方法它们分别将值转换为位列表，反之亦然：数据位=0|1typeBin=[Bit]classBinary t其中showBin：：t→BinreadBin ：： Bin→（t，Bin）。欣兹和佩顿·琼斯7一个真正的实现可能有一个更复杂的Bin表示，但这是一个单独的问题。我们可以这样给showBin和readBin下一个通用的定义：showBin{1}单元=[ ]showBin{a+b}（Inlx）=0：showBinxshowBin{a+b}（Inry）=1：showBinyshowBin{ab}（x：n：y）=showBinx++showBinyreadBin{1}bs =（Unit，bs）readBin{a+b}[ ]=err或“readBin”readBin{a+b}（0：bs）=let（x，bsJ）=readBinbsin（Inl x，bsJ）readBin{a+b}（1：bs）=let（y，bs J）=readBinbsin（Inr y，bsJ）readBin{ab}bs=let（x，bs 1）=readBinbs（y，bs2）=readBinbs1在（（x：n：y），b s2）中。注意，readBin生成未知类型t的值，而showBin和（）都使用这样的值。同样，我们可以将Wibble作为一个实例 简单地说，二进制Wibble。3.2推导与推导虽然这一切听起来很简单，但它有着有趣而重要的后果：虽然带有泛型方法的类的实例声明现在相当简短，但仍然必须给出。例如，当在Eq的类声明中给出一个泛型默认方法时，并不是所有类型都成为Eq的实例。实例声明不需要出现在与数据类型声明或类声明相同的模块中。相反，在Haskell 98中，派生子句必须附加到数据类型声明中。这种分离是有用的，因为类甚至可能不在声明类型的作用域编译器只在程序员省略方法定义时才填充它。例如，如果我们说其中（Wag）（Wag）=Truew2w2=False，则当然使用该程序员提供的代码。这是我们的建议与别人不同的一点。在大多数泛型编程系统中，泛型函数一般适用于所有类型。在我们的设计中，欣兹和佩顿·琼斯8程序员可以在逐个类型的基础上覆盖泛型定义。这种能力对于支持抽象数据类型来说是至关重要的。 例如，一个集合可以用不止一种方式表示为平衡树，等式必须考虑这个事实。简单地使用一个通用的相等函数将获得表示的相等，这在这种情况下是错误的。以类似的方式，我们也可以使用普通的实例声明来指定泛型操作应该在原始类型上做什么，例如Char，Int，Double。特别是，如果你想为涉及函数空间的类型定义一个方法，你只需提供一个实例声明为“→"。派生子句现在可以被看作是实例声明的简写（尽管现在并没有短得多）。不过，有一点不同。考虑数据树a =节点a [树a]导出（等式）。在我们的设计中，派生子句是instance（Eq a）<$Eq（Tree a）注意，在实例声明中，我们必须显式指定上下文（等式a），这是由派生机制自动推断的。我们将在4.4节中更详细地讨论这个问题3.3泛型表示类型泛型定义左侧大括号中的参数是类型。当然，我们的想法是，这些类属定义可以专门用于任何特定类型。例如，假设我们有一个数据类型List，我们让List成为Binary的一个实例：dataList a=Cons a（List a）|无instance（Binary a）Binary（Lista）. 编译器如何填充缺少的方法定义？首先，我们定义List的通用表示类型，我们将其称为列表编号：typeLista=（aLista）+1.我们将在6.2节中对表示类型有更多的介绍，但现在我们可以将List_n看作一个或多或少与List同构的类型，但它只使用一个小的、固定的类型构造函数集，即unit、sums和products。还请注意，List不是递归类型;它在右侧提到List，而不是List。因此，我们的泛型表示类型只给出了递归类型的“顶层”表示单位、总和和乘积类型的定义如下：数据1 =单位数据a + b = Inla|INR b数据a b= a：：b。欣兹和佩顿·琼斯9∗∗∀当然，1不是合法的Haskell类型构造函数，fix（+）和（）也不是。我们给它们特殊的语法来区分它们与它们的在我们的示例中，List是两种类型的和（+）：元素类型a和List的乘积（），以及单位类型（1）。为了使同构明确，让我们编写函数，将3转换为3：to-List：：目录a。List_a →List_a to-List（Inl（x：n：xs））=Cons xxs至列表（Inr单位）=无从-List：：blog。List a →List afrom-List（Cons x xs）=Inl（x：n：xs）从-列表Nil= Inr单位。3.4通用实例其思想是，通过将List视为List对 象，泛型代码解释了要做什么。例如，showBin的泛型方法说明了如果参数是一个sum，该怎么做，如果参数是一个product，该怎么做，如果参数是一个unit类型，该怎么做。将这些默认方法重新表示为三个普通的实例声明是很有用的实例二进制1，其中showBin Unit=[]readBin bs=（Unit，bs）instance（Binary a，Binary b）Binary（a+b）其中showBin（Inl x）=0：showBinx showBin（Inr y）=1：showBin yreadBin[]=错误“readBin”readBin（0：bs）=let（x，bsJ）=readBin bsin（Inl x，bsJ）readBin（1：bs）=let（y，bsJ）=readBin bsin（Inr y，bsJ）instance（Binary a，Binary b）<$Binary（a<$b）其中showBin（x：n：y）=showBinx++showBinyreadBinbs=let（x，bs1）=readBinbs（y，bs2）=readBinbs1在（（x：n：y），b s2）中。3在本文中，我们将使量化显式，即使Haskell 98没有显式量化。所以，在这个例子中，我们在to-List的类型签名中写了一个显式的.我们的一些类型变得相当复杂，所以欣兹和佩顿·琼斯10它有助于绝对确定量化发生在哪里。欣兹和佩顿·琼斯11∀→∗我们将泛型表示类型的这些实例声明描述为泛型实例声明。它们不是由程序员显式编写的，而是由编译器从具有泛型默认方法的类声明中派生出来的。我们将在4.3节中进一步讨论泛型实例声明。3.5填充缺少的方法我们现在可以更精确地说明编译器如何填充缺失的方法。在本节中，我们将使用一个例子来概述这个想法，而第6节将处理一般情况。当程序员写instance（Binary a）Binary（Lista）编译器将在方法声明中填充如下：showBin xs=showBin（from-List xs）readBin bs =casereadBin bsof（xs，bsJ）→（to-List xs，bsJ）.让我们专注于showBin的定义。它分为两个阶段：(i) 首先，从-List：： a . List aLista将类型为将a转换为List_a类型的值。(ii) 其次，我们调用重载的showBin函数来完成这个任务，使用泛型实例声明的方法起初，这看起来非常奇怪。我们将showBin定义为showBin。但是看看一个人手写的定义：instance（Binary a）Binary（List a）whereshowBinNil=0：[]showBin（Consxx s）=1：showBinx++showBinx s。第一个调用是在列表元素类型上调用showBin;第二个是在列表类型上递归调用同一个showBin。类似的事情发生在一般定义上。在这里，showBin是在List类型的参数上调用的。这是一个sum类型，所以Binary的sum实例启动（第3.4节）。它依次调用showBin，一次在类型1，一次在类型a List a。 前者有一个实例声明，而后者使用product实例并在类型a和List a处调用showBin。但是前者就像手写体实例中的showBin x，而后者就像showBin xs。所以一切顺利。让我们回到上面的第一步。在showBin的例子中，将参数转换为它的泛型表示类型相当简单。另一方面，readBin有点复杂，因为它返回一个对，只有一个组件需要转换。一般来说，编译器是如何执行这种转换的？我们把整个第5节都用来讨论这个问题。不过，首先，我们详细说明我们的欣兹和佩顿·琼斯12设计4讨论和阐述我们现在已经勾画出了我们设计的要点。在本节中，我们将详细介绍其中的一些细节。4.1构造函数名称和记录标签令人恼火的是，单位、总和和乘积是不够的。例如，考虑标准的Haskell类Show。为了能够给出showsPrec的通用定义，构造函数的名称及其固定值必须是可访问的。为此，我们提供了一个额外的泛型表示类型，其形式为cofa，其中c是ConDescr类型的值变量，a是类型变量。ConDescr类型是一种新的基本类型，它包含所有构造函数名称。要操作构造函数名，可以使用以下操作-详细列表见[4]。dataConDescr--abstract数据固定性=不固定|固定整数|Infixl Int| Infixr IntconName：：ConDescr → String -- primitiveconArity：：ConDescr → Int-- primitiveconFixity：：ConDescr → Fixity--primitive实例显示ConDescr，其中show=conName使用conName和conArity，我们可以实现Haskell显示类-对于全边缘版本，请参见[4]。类Show twhereshow：：t→String产品展示 Int→t→Stringshow x=showsPrec 0xshowsPrec{a+b}d（Inlx）=showsPrecdxshowsPrec{a+b}d （ Inry ）=showsPrecdyshowsPrec{cofa}d（Concx）=ifconArity c0thenshow celseshowParen（d10）（showc++“。“++显示Prec10x）showsPrec{ab}d（x：n：y）=showsPrecdx++“。“++显示Precdya的表示类型c由以下伪Haskell声明定义：newtypecofa = Con c a.欣兹和佩顿·琼斯13→→对于Haskell来说，c是一个由类型携带的值。 最好是想想 上面的声明定义了一个类型族：对于每个c，类型构造函数“c of“类型 ** 值构造函数“Con c“为A型（CofA）。 那么，为什么a的类型c包含信息关于C？有人可能会怀疑，提供这些信息是足够的价值水平。这样做可以显示效果，但读起来会失败：classRead t whereread：：String→[（t，String）]read{cofa}s=[（Concx，s3）| (s1,s2)←lexs,s1conNamec,（x，s3）←reads2].重要的一点是，read产生（而不是消费）值，但它需要访问构造函数名称。Haskell允许程序员为构造函数的组件分配标签，这些标签也是read和show所需要的。然而，出于演示的目的事实上，它们可以完全类似于构造函数名来处理。4.2泛型类声明一般来说，类声明由签名和实现部分组成，签名指定类方法的类型，实现部分给出类方法的类型签名具有一般形式：类ctxCa，其中执行部分第1段 *执行部分1a...opn * 行动处。实现部分由通用和非通用默认定义组成。非泛型定义是普通的Haskell定义op--一个泛型定义可以通过左边的类型模式识别，用花括号括起来它有一个示意图操作{1}=.o p{a+b}=. . .o p{ab}=. . .op {cofa}=....欣兹和佩顿·琼斯14/类型模式是强制性的，以便公式可以正确分组。例如，考虑前面给出的（）的一般定义（）{1}Unit Unit=True（）{a+b}（Inlx1）（Inlx2）=x1 x2（）{a+b}（Inry1）（Inry2）=y1 y2（）{a+b}=False（）{ab}（x1：：y1）（x2：：y2）=x1x2y1y2.如果没有类型模式，就没有办法决定第二个但最后一个等式属于（+）还是（+）情况。除了类型模式之外，泛型定义完全具有正常Haskell定义的形式。我们注意到以下几点：类声明可以指定泛型和非泛型默认方法声明的任意混合。在上面的Eq的情况下，（）是通过对参数类型的归纳来定义的，而（）是非泛型的。泛型和非泛型方法可以是相互递归的。类声明是泛型定义在我们的设计中唯一出现的地方。 没有“独立的”通用定义，正如有Haskell中没有独立的重载定义。 (One可能不同意这种选择，但它并没有限制表达能力，因为人们总是可以发明一个类来封装新的重载或泛型函数。目前，泛型默认声明只能用于类型类，也就是说，对于类型参数范围超过kind类型的*. 例如，我们不能为Functor类指定泛型默认方法类函数f，其中fmap：：（a→b）→（f a→f b）.这是我们计划在未来添加的第一个扩展对于多参数类型类，将有多个类型参数。我们不考虑这种复杂性在本文中。4.3泛型实例声明在3.4节中，我们说过类声明中的泛型定义被编译器重新表示为一组实例声明，每个实例声明对应一个泛型表示类型。有人可能会问：为什么不让程序员直接写这些实例声明呢？我们的答案是文体而不是技术。我们希望将Haskell中的泛型编程作为一种更丰富的语言来编写默认方法声明，将它们分散在几个实例声明中并不能传达这一信息。关于是否可以使用通用默认声明的问题将变得更加复杂，因为有些部分，欣兹和佩顿·琼斯15∗∗而不是其他的。在类声明中一次编写所有声明似乎是最简单和最直接的方法，尽管它确实涉及到一些新的语法。我们决定的另一个风格上的原因是，很容易将产品a b的泛型实例声明与相应的"普通"产品类型（a，b）的"普通"实例声明混淆。例如，在Show的情况下，产品的普通实例声明可能如下所示：instance（Show a，Show b）实例（Showa，Show b）showsPrec d（x，y）=“（“++ showsPrec0x++“，”++ showsPrec0y++“）“。由于元组通常使用dist fix表示法显示，因此我们选择覆盖通用定义。尽管如此，Show的类声明将产生泛型实例声明instance（Show a，Show b）Show（ab）whereshowsPrec d（x：x：y）=showsPrecdx++“。“++ showsPrecdy.回想一下，乘积a b用于表示一个参数的参数。因此，泛型实例声明指定了构造函数参数的布局：它们被连续显示，并由空格分隔。4.4推断实例上下文当一个类有泛型方法时，可以给出一个实例声明，而不提供任何方法的代码。但是仍然需要为实例声明提供上下文。例如，一个人不能写实例Eq（列表a）因为类型检查器会抱怨缺少（等式a）约束。相反，一个人必须写instanceEq a<$Eq（List a）.与此相反，现有的派生机制推断必要的实例上下文。一个明显的问题是：在我们的新方案中，编译器能推断出实例上下文吗？例如，我们可以写instance（.. . ）Eq（列表a）这表明编译器应该在缺少的上下文中填充“（.. . ）".实际上，我们可能希望在任何类型的签名中允许这样的缩写，比如说，f：：（.. . ）a→ a.编写这种部分类型签名的能力，省略号由类型推断填充，已经在Haskell邮件列表中讨论过，从技术角度来看看是完全可行的。例如，声明很重要欣兹和佩顿·琼斯16对于一阶kinded类型仍然是可行的（尽管有点棘手，涉及定点迭代），但我们相信它对于高阶kinded类型是不可行的（见7.3节）。无论如何，这个问题与我们的主题完全不同，因此我们不进一步讨论它。5映射函数我们现在已经展示了程序员看到的设计。但是，在描述实现之前，我们需要暂停一下，介绍双向映射，这是实现的重要基础回想一下在3.5节中，我们在实例声明的泛型方法中填充的一般计划。假设我们有如下的类声明：C类a，其中：Op a.我们将只处理单参数类型类，但请参见第9节。我们还假设，为了符号清晰，方法op的类型简单地由Op a给出。我们总是可以引入一个类型同义词来做到这一点4.现在假设程序员编写实例声明instancectxC（Ta<$）.其中ctx是一个连续文本，a是一个变量序列。这是怎么回事？编译器在方法op的定义中填充？在3.5节之后，它可以这样填充：实例ctxC（Ta<$），其中op=adapt-Op（op：：Op（Ta<$））。也就是说，我们在类型Ta′，以产生typeOp（T）的值（a），然后将值转换为Op（Ta′）。函数adapt-Op这样做阻抗匹配通过转换一个函数，该函数对类型为把它交给一个在它上面工作的人。adapt-Op：：a<$。Op（Ta<$）→Op（Ta<$）显然，adapt-Op如何工作取决于Op的形式，4从技术上讲，Haskell类型同义词还没有强大到可以做这样的缩写对于像properFraction这样的方法：类RealFrac a，其中properFraction：：（Integral b）a→（b，a）.因为它的类型在开始时有上下文。但我们将假设这样的缩写是可能的。欣兹和佩顿·琼斯17法 以下是一些示例：typeIn a=a→Stringadapt-In：：a<$。In（Ta<$）→In（Ta<$）adapt-In=λf→f·from-T类型Out a=String→aadapt-Out：：a<$。出（Ta<$）→出（Ta<$）adapt-Out=λf→to-T·ftypeBoth a=a→aadapt-Both：：a<$. Both（T a<$）→Both（Ta<$）adapt-Both=λf→to-T·f·from-T.这些自适应函数使用函数to-T和from-T，它们将吐温TA和T;它们在第3.3节中介绍。请注意，需要to-T和from-T;单独一个是不行的。此外，当我们定义类，从而定义Op类型时，一旦我们可以将该类的实例写为许多不同的类型T。所以我们想从adapt函数中抽象出to-T和from-T函数（注意，下面的a是一个类型变量）：adapt-BothJ：： 你好（a→a）→（a→a）→（Botha→Both a）adapt-BothJto from=λf→to·f·fromadapt-Both=adapt-BothJto -T from-T事实证明，将to-T和from-T函数打包起来是很方便的嵌入-投影对：数据EP aa= EP{to：：a→a，from：：a→a}。这里EP aa现在我们可以写adapt-BothJJ：：adapta. EPaa→（Botha→Both a）adapt-BothJJep-a=λf→to ep-a·f·from ep-a conv-T：：a. EP（Ta<$）（Ta<$）conv-T=EP{to=to -T，from=from-T}adapt-Both= adapt-BothJJconv-T.最后一步是使adapt函数本身返回一个嵌入-投影对，而不仅仅是bimap-Both：：bimap. EP aa→EP（Both a）（Botha）bimap-Both ep-a=EP{to=λf→from ep-a·f·to ep -a，from=λf→to ep-a·f·from ep-a}adapt-Both = to（bimap-Both conv-T）.欣兹和佩顿·琼斯18联系我们我们为什么要在两个方向上构造映射，这一点并不明显，当我们使用它时，我们可以丢弃其中一个，但是在为任意类型构造bimap时，它是必不可少的，我们将在下一节中看到。5.1生成双向映射函数在上一节中，我们为特定的方法类型Both a生成了bimap-Both。我们还观察到，合适的代码取决于方法类型的结构，所以百万美元的问题是：我们如何为任意方法类型生成双向映射？我们简单地通过归纳方法的类型来完成，因此：bimap-Op：：bimap. EP aa→EP（Op a）（Opa）bima p-Ope p-a=bima p{Opa}[a：=e p-a].这个定义并不是正确的Haskell;bimap应该被认为是一个Meta函数，在编译时求值，返回一个Haskell表达式。它接受以下参数：一个类型（用花括号写）和一个环境Q，将类型变量映射到表达式。语法[a：=ep-a]表示将a绑定到ep-a的环境。我们通过归纳类型表达式的结构来定义bimapbimap{a}Q=Q（a）bimap{（→）}Q=bimap-Arowbimap{T}Q=bimap-Tbimap{tu}Q=（bimap{t}Q）（bimap{u}Q）哪里bimap-Arrow：：aab. EP aa→EP bb→EP（a→b）（a→b）bimap-箭头ep -a ep-b=EP{to=λf→to ep-b·f·from ep-a，from = λf→ from ep-b·f·to ep-a}。bimap T的情况是处理除（）之外的类型构造函数让我们举一个例子。回想一下我们的Both类型：类型Both a = a→ a。设Q=[a：=ep-a]，我们有bimap-Both ep -a=bimap{a→a}Q=（bimap{（→）a}Q）（bimap{a}Q）=（（bimap（→）Q）（bimap{a}Q））（bimap{a}Q）=bimap-箭头ep-a ep-a=EP{to=λf→to ep-a·f·from ep-a}，from=λf→from ep-a·f·to ep-a.欣兹和佩顿·琼斯19→→ →→5.2数据类型映射如果涉及到数据类型怎么办？例如，在readBin类型中，结果类型中有一对输入ReadBin a=Bin→（a，Bin）。如果我们只是尝试我们目前的计划，我们会陷入困境：bimap-ReadBin ep=bimap{Bin→（a，Bin）}Q=bima p-Arow（bima p{Bin}Q）（bima p{（a，Bin）}Q）。现在，由于Bin不是参数化类型，因此没有什么可做的，bimap-Bin ：：EP BinBin bimap-Bin=id-EPid-EP：：patha. EP a aid-EP=EP{to=λx→x，from=λx→x}而pairs是在两种类型上参数化的，所以我们必须将映射函数推到内部：bimap-对：：aab。EP aa→EP b b→EP（a，b）（a，b）bimap-对ep -a ep-b=EP{to=λ（xλ，yλ）→（to ep-a xλ，to ep-b yλ），f rom= λ（x，y）→（f rome p-ax，f rome p-by）}.一般来说，我们可以通过归纳数据类型声明的结构来定义bimap-T。数据类型dataT a1. a k= K1t11. t1m1| · · · |K n t n1. t nmn由图1中显示的bimap-T这张双向图是什么类型的？答案很简单，但令人难以置信：bimap-T的类型取决于T的类型。 假设T有kind*，例如Bin。那么双向映射的类型就是EP T T（实际上是bimap-T=id-EP）。如果T和所有Op一样有kind* *bimap-T：：bimap abimap. EP aa→EP（T a）（T a）。一个更复杂的类型，比如（* *）（* *），会产生一个更复杂的类型：bimap-T：：ff。（2002年b月b日）EP bb→EP（f b）（fb））→（aa. EPaa→EP（T f a）（Tfa））。现在bimap-T有一个所谓的rank-2类型签名[12]。粗略地说，bimap-T将双向映射转换为双向映射（这就是为什么bimap-T的参数被称为bimap-ai）。一般来说，如果T有kindκ，那么bimap-T有类型Bimap{κ}T T，其中Bimap是通过在欣兹和佩顿·琼斯20--bimap-T bimap-a1. bimap-ak=EP{to=to-T，from=from-T}哪里到-T（K1x11. x1m1）=K1（to（bima p{t11}Q）x11）. . （to（bimap{t1m1}Q）x1m1）...到-T（K n x n1. x nmn）=Kn（to（bima p{tn1}Q）xn1）. . . （to（bimap{tnmn}Q）xnmn）从-T（K1x11. x1m1）=K1（f_om（bima p{t11}Q）x11）. . （from（bimap{t1m1}Q）x1m1）...从-T（K n x n1. x nmn）=Kn（f_（bima p{tn1}Q）xn1）. . . （from（bimap{tnmn}Q）xnmn）Q=[a1：=bimap-a1，.，a k：=bimap-ak]图1.数据类型T的双向映射函数。种类结构Bimap{*}tt=EPttBimap{κ1→κ2}tt=aa。 Bimap{κ1}aa→Bimap{κ2}（ta）（ta）。如果κ的阶数为n，则双映射κ是秩为n的类型。然而，这并没有造成任何问题，因为Glasgow Haskell算法内部使用了多态λ演算的变体[17]。我们将在第7节中更多地讨论高阶kinded类型。有关种类索引类型（如Bimap）的更多信息，请参阅[7]。6实现泛型默认方法现在，我们终于准备好处理执行问题了。我们将其描述为Haskell源代码到源代码的转换，在类型检查之前执行（至少在概念上）。为什么？为什么？类型检查器已经做了很多我们需要的事情。 而且我们可能有更好的机会，将顺利地与复杂的，如多参数类型类[16]，隐式参数[13]和函数依赖[11]。源代码到源代码的翻译如下。对于每个数据类型声明T，我们生成以下内容：对于每个构造函数K，一个ConDescr类型的值con-K，它描述了构造函数的属性（第6.1节）。一个类型同义词，T，T的泛型表示类型（第6. 2节）。一个嵌入-投影对转换-T：：a<$。EP（Ta<$）（Ta<$），这是一种T和它的类属表示T之间的verts（6.3节）。