协议编程，第2部分：依赖向量

在上一部分中，我们使用了协议以便对我们感兴趣的某些属性进行建模，并找到了适合该模型的多个示例（2D矢量，复数和线性函数）。

但是这些仅限于二维类型。 这太局限了，我们想操纵2个以上的维度。 这将需要确保我们正在操纵相同尺寸的值。

像第1部分一样，您可以在一个快速的游乐场中跟随，您可以在此处下载iPad或在Mac下载

免责声明

紧随其后的内容被视为“请勿在家中尝试”，纯粹是出于学术兴趣而非在Swift中的实际应用。

我们将使用协议来实现依赖类型。

N维向量，第一次尝试

为了更好地理解该问题，我们将尝试使用一个简单的数组来实现n维向量。 现有的大多数实现都使用数组来表示n维向量，但是它们有很大的缺陷：

不幸的是，我们无法实现NVector Additive ，因为它没有携带有关其大小的足够信息。 我们需要以某种方式对向量的大小进行编码。 这将使我们既可以重用代码，又可以避免出现以下错误：

为了解决此问题，我们将需要使用Size类型参数及其所持有的值的类型声明NVector结构。

我们的+函数看起来像这样：

由于第一个类型参数是数组的大小，因此我们强制要求两个加法向量的值相同。

事实证明，Swift已经拥有足够的技术来实现这种功能。

首先，我们将定义一个新的类型Nat以表示自然数

纳兹世界

“ Nat”是“自然数”的简写，自然数是从0到无穷大的整数的名称。 使用这两个定义来递归定义它们：

• 零是自然数。
• 自然数的任何后继也是自然数。

可以这样用Swift编写：

现在，我们可以定义几个自然数：

如您所见，数字是根据先前的数字递归定义的。 您还可以看到我们正在使用没有值的空enum声明。 这意味着Nat仅作为类型而不是value存在。 类型Three没有值 。

但是，我们可以创建一个函数，给定类型为Nat的函数可以返回它表示的Int值。 这样我们就可以从类型Three获得值3 （类型为Int ）。

方法如下：

1.首先我们需要一个协议，该协议将声明符合它的类型具有Int表示形式

该协议声明符合它的类型具有与之关联的静态Int值。

2.然后，我们需要为Zero类型和Succ类型实现此协议。 Zero直接实现： Zero由数字0表示。

3.最后，我们需要为Succ实现相同的协议。 Succ有点棘手，因为它是递归定义的。 因此，我们需要利用条件一致性来要求内部N类型也具有Int表示形式。 包装的类型N实际上是我们当前正在计算的类型的前身。

因此， Succ返回1加N的Int值，它是前身。 这样，类型Two返回1加上1整数值，后者本身返回1 + Zero整数值0 。 总计为1 + 1 + 0 = 2 。

我们现在可以写

并按预期方式获得3 。

从属向量

现在我们有了自然数类型，我们可以使用此类型来定义使用Nat的矢量类型，以携带其大小信息。

不幸的是，如果我们像Lists那样尝试实现NVector遇到问题：

我们不能为每种情况使用不同的N ，理想情况下，我们希望

这看起来像是 GADT

相反，我们将使用与Nat相同的策略，我们将定义一个协议并使用具体的类型来实现它。

这表示N维向量取决于两种类型，即Nat的大小和向量中的Elements 。

有趣的是，我们不能使用数组来定义向量，因为它们不携带类型级别的大小信息。 相反，我们将像实现链表一样实现向量。 在此提醒您，我们将如何快速实现链接列表

也就是说， LinkedList可以为空，或者具有head元素和尾部LinkedList 。 同样，由于大小的限制，我们不能在此处使用enum ，但是我们将使用相同的想法：空向量不包含任何内容，而“ cons”向量既包含元素又包含尾向量。

空向量的定义非常简单，它是一个空结构，大小Zero并带有任何类型A

对于Cons情况，我们有一个带有两个字段的结构。 一个用于向量的头部，一个用于向量的尾部。 尾巴的类型（ VS ）也必须是NVector 。 这使我们可以根据尾巴的大小定义矢量的大小。 那就是Cons的大小Succ它的尾巴大小的Succ 。 它还强制在头部的taht元素必须与由尾巴保持的元素具有相同的类型。

编写依赖函数

现在，我们可以开始使用大小合适的向量，但是创建它们的过程并不十分符合人体工程学。 为了构造一个大小为3的向量，我们需要对ConsVect进行3次调用，对ConsVect进行一次调用：

这是不可读的。

为了解决此问题，我们将引入“ cons”运算符。 传统上，这是双冒号（ :: ，但是Swift保留冒号符号用于类型定义，并且它不是有效的运算符。 相反，我们将使用§§ ，它可以在Apple平台上与alt-6使用。

如您所见，此函数的类型签名为

读为“对于所有向量V ，给定V的元素和向量V ，构造大小为1 + V.Size的向量”。最后一部分至关重要： ConsVect意思是“比V的大小大一个”。

为了进一步简化Vector的使用，我们将添加empty函数以创建空白vector。

并结合使用两者来创建向量：

这是我们在向量上定义的函数的第一个示例，该函数利用其大小信息来构造正确大小的向量。

使用类型信息

类型中包含大小信息的一个很好的特性是，我们甚至不必检查数据即可计算出有用的程序。 例如，通过在Nat上重用我们的int属性，我们可以计算向量的大小而无需对其进行迭代。

这仍然需要遍历 Nat 类型。

这个特定示例的用处有限，但它向我们揭示了一个新概念：存在结构（如向量）的属性与其所持有的值无关。 这些属性可以用类型表示，并且适用于所有可能的实例。 这种形式的多态性比简单的泛型要强，因为它允许我们编写更复杂的约束（如大小约束），而与我们处理的数据的性质无关。 确实， NVector的实现可能会有所不同，但是只要它使用Nat来NVector其大小，则此实现将起作用。

您可能还会注意到，我们能够从Nat为Int但是我们没有提供从Int为Nat 。 这是因为swift无法使用从运行时值定义的类型。 实际上，如果值3来自标准输入。 Swift如何分辨Succ<Succ<Succ>> ？

即使可以使用此功能，我们也不能在类型签名中使用它。 例如我们不能做

在依赖类型的编程语言中这是可能的

实施协议

您可能已经注意到，打印矢量不会输出非常漂亮或可读的文本。 为了解决这个问题，我们需要实现Swift的标准库协议CustomStringConvertible 。 它只有一个字段，并且是一个description getter，它返回String 。 我们将使向量与CustomStringConvertible一致，以便打印出更漂亮的消息。

我们不为空向量打印任何内容，对于ConsVect我们打印头部，然后递归打印尾部，两者之间ConsVect间隔。

现在我们甚至可以使用依赖向量打印矩阵

添加剂

现在我们有了n维向量，并且知道如何在它们上实现函数，我们可以再次添加Vector拥有的所有功能

与以前不同，我们不能自动实现Additive因为我们只有符合TwoDimensions类型的默认实现。 此外，我们的NVector类型没有定义为普通数据类型，而是分为NVector协议的两个实例，这不是我们可以抽象的语言的本机结构。

这意味着我们必须为NilVect和ConsVect自己实现Additive 。

将空向量加在一起非常容易，因为它们不携带任何值，我们每次都可以返回空向量。

对于ConsVect我们将必须根据当前值和tail向量递归地定义加法，并假设尾部也是可Additive 。

如您所见，用于添加的身份ConsVect是身份值的向量。 将两个向量相加就等于创建了一个新的向量，该向量具有两个头部的和与两个末端的和。 我们现在可以写

并获得预期的结果：

  4 4 4 4 

花式多，标量和量级

我们可以通过使用NilVect一个基本案例和NilVect一个递归实例来实现所有其他现有协议。

您会发现它们都遵循相同的模式：

• NilVect返回某种空值或身份
• ConsVect对头部进行一些操作，然后对尾部进行递归调用。

不幸的是，Swift无法像Vector ， Complex和Linear那样自动实现那些协议。 有趣的是，有一部分语言可以对此模式进行抽象，这就是Equatable协议：

如果编译器公开了用于实现此目的的工具，那就太好了，这样我们就不必自己编写所有这些函数了。

结束语

一个精明的读者可能会注意到我们还没有实现矢量上最著名的功能map 。 那是因为，至少就我目前对类型系统的理解而言，目前尚不可能。 要了解原因，请尝试一下：

具有 map 功能的 类型为 Functor

这个定义是不正确的，因为它表明我们将“ Self转换为“ Self ，这表明“ Self ”没有改变。 但是，我们要通过更改其类型参数进行转换，即：将Self转换为Self 。 我们需要尝试其他方法：

在这里，我们创建一个协议Wrapper ，该Wrapper抽象具有一个类型参数的类型，并且可以给定该类型的值来创建自己。 作为示例，我们给出了Array的Wrapper实现。 现在，我们可以再次尝试围绕Wrapper设计Functor协议：

我们将函数称为“ fmap”，以避免与 数组中 的“ map" 函数 发生冲突

这个定义还有另一个问题。 它返回R ，只要它符合Functor ，就可以是任何类型。 这是不正确的，除了在Dest而不是InnerType参数化之外，我们希望R与Self具有相同的类型。 如果我们继续尝试，我们仍然可以实现fmap函数，但是结果是相当困难的。

这就是我们要编写的内容，但是编译器告诉我们它无法将[Dest]转换为R ，这是因为无法证明R和Self一定相同。 这是我们无法表达的约束。 编译器的唯一建议是添加as! R as! R结尾。 但是我们仍然会有问题：

1.不管as! R as! R它不能说出为什么这是错误的：

2.我们丢失类型推断：

它说

“无法使用类型为（（（Int）-> Int）’的参数列表调用’fmap’””

这非常令人困惑。 我们可以使用(Int) -> Int作为参数来调用fmap ，但是Swift不能推断出返回类型应该为[Int]因为我们只是告诉它返回R 以下作品

通过告诉map返回R而不能够进一步限制它，我们失去了推断fmap的返回类型的能力，而fmap的返回类型不能用作API。

如果Swift具有类型级别的功能（如之前的IntToNat ）或高级类型，我们可以编写类似于以下内容的代码：

我在重用 我们用于函数 签名 的 (Type) -> Type 语法， 并用尖括号替换括号，以明确 表明这与类型构造函数有关，而不与值构造函数有关。

用 -> *表示在单个类型实参上参数化的类型。

这将允许编译器推断fmap的返回类型与符合它的类型相同，只是通过不同的InnerType参数化了它。

当试图将两个大小的矩阵（向量的向量）相乘时，我们会遇到类似的问题。 给定一个大小为M x N的矩阵，另一个大小为N x O我们需要返回一个大小为M x O的矩阵。 不幸的是，Swift不允许我们定义一个函数，该函数返回相同类型但在M x O参数化的新值。

结论

在第一部分中，我们能够设计一套协议，使我们能够抽象非常通用的结构的行为，并且能够以非常有趣的方式将它们组合起来（只要它们是2D的）。 然后，我们尝试抽象出类型的大小并实现大小向量。 不幸的是，这也是我们达到Swift极限的地方。 缺少真正的依存类型会阻止我们从运行时构造大小向量（它们都必须在编译类型下进行静态定义），而缺乏类型级别的函数或更高种类的类型会阻止我们在函数map或map上定义函数矩阵乘法。

尽管存在这些缺点，但通过引入条件一致性，Swift的类型系统已变得更加强大和有用，并且能够处理大多数编程任务。 遗憾的是，我们仍然必须依赖运行时错误才能乘以矩阵。

如果Swift中包括从属类型，我们也将允许开发类型安全的状态机，网络协议和更好的优化。 即使我们“仅”获得了更高种类的类型，至少我们也可以在NVector上实现map 。