夜锈病的单子和GAT

这篇博客文章的灵感完全来自于每晚阅读GAT！ / d / C5H5N5O的Reddit帖子。我只是决定把事情做得有点过头，并认为关于它的博客文章会很有趣。我想从一开始就很清楚：我在这篇文章中介绍了一些高级概念，这些概念依赖于Rust中的不稳定功能。我根本不主张使用它们。我只是在探索GAT可能和不可能的事情。

Rust在类型系统级别上与Haskell有许多相似之处。两者都具有类型，泛型类型，关联类型和特征/类型类（基本上是等效的）。但是，Haskell具有Rust中缺少的一项重要附加功能：高级类型（HKT）。这并不是Rust的偶然限制，也不是应该填补的空白。至少据我所知，这是一个故意的设计决定。但是结果是，到目前为止，Rust仍无法真正实现某些功能。

以Haskell中的Functor为例。尽管听起来很恐怖，但如今几乎所有开发人员都对Functor的概念很熟悉。 Functor提供了一个通用接口，用于在此结构上映射功能。 Rust中许多不同的结构都可以提供这种映射功能，包括Option，Result，Iterator和Future。

但是，不可能编写可以由多种类型实现的通用Functor特性。相反，单个类型可以将它们实现为该类型上的方法。例如，我们可以编写我们自己的自定义MyOption和MyResult枚举并提供映射方法：

＃[派生（Debug，PartialEq）]枚举MyOption＆lt; A＆gt; {Some（A），None，}表示＆lt; A＆gt; MyOption＆lt; A＆gt; {fn map＆lt; F：FnOnce（A）-＆gt; B，B＞（self，f：F）-＞ B。 MyOption＆lt; B＆gt; {match self {MyOption :: Some（a）=＆gt; MyOption :: Some（f（a）），MyOption :: None =＆gt; MyOption :: None，}}}＃[test] fn test_option_map（）{assert_eq！ （MyOption :: Some（5）。map（| x | x + 1），MyOption :: Some（6））; assert_eq！ （MyOption :: None。map（| x：i32 | x + 1），MyOption :: None）;}＃[派生（Debug，PartialEq）]枚举MyResult＆lt; A，E＆gt; {Ok（A），Err（E），} impl＆lt; A，E＆gt; MyResult＆lt; A，E＆gt; {fn map＆lt; F：FnOnce（A）-＆gt; B，B＞（self，f：F）-＞ B。 MyResult＆lt; B，E＆gt; {match self {MyResult :: Ok（a）=＆gt; MyResult :: Ok（f（a）），MyResult :: Err（e）=> MyResult :: Err（e），}}}＃[test] fn test_result_map（）{assert_eq！ （MyResult :: Ok（5）。map（| x | x + 1），MyResult :: Ok ::＆lt; i32，（）＆gt;（6））; assert_eq！ （MyResult :: Err（＆＃34; hello＆＃34;）。map（| x：i32 | x + 1），MyResult :: Err（＆＃34; hello＆＃34;））;}

但是，没有GAT不可能将map定义为特征方法。让我们看看为什么。这是单态仿函数的幼稚方法。特质，以及Option的实现：

///单态函子特征trait MonoFunctor {类型Unwrapped; //值＆＃34;包含在内部＆＃34; fn映射＆lt; F＆gt;（self，f：F）-＆gt;自己在哪里F：FnMut（自己::未包装）-＆gt;自我：：未包装；} imp＆lt; A＆gt;选项＆lt; A＆gt;的MonoFunctor {类型Unwrapped = A; fn映射＆lt; F：FnMut（A）-＆gt; A＆gt;（self，mut f：F）-＆gt;选项＆lt; A＆gt; {匹配自己{一些（a）=＆gt;一些（f（a）），无=>没有 ， } }}

在特征定义中，我们为存在于＆＃34; inside＆＃34;中的值定义了一个关联类型Unwrapped。 MonoFunctor。在选项＆lt; A＆gt;的情况下，将是A。这就是问题所在。我们将Unwrapped硬编码为一种类型，A。通常使用map函数，我们希望将类型更改为B。但是，在当前稳定的Rust中，我们无话可说与该MonoFunctor关联的类型，但其内部的内容也有些不同。＆＃34;

为了获得多态函子，我们需要能够说出如果我在其中封装了其他类型，我的类型将如何显示。例如，对于Option，我们想说“嘿，我有Option＆lt; A＆gt ;，它包含一个A类型，但是如果它包含一个B类型，它将是选项＆lt; B＆gt;。为此，我们将使用通用的关联类型Wrapped＆lt; B＆gt ;：

特征Functor {类型为未包装;包装的＆lt; B＆gt;类型：Functor; fn映射＆lt; F，B＆gt;（self，f：F）-＆gt;自身：：包装的B。其中F：FnMut（自我：：未包装）-＆gt; B;}

当我们知道一个函子时，我们也可以找出另一个关联类型WrappedB。就像“自我”，但其下面的包裹值不同

函数参数将从当前的基础Unwrapped值映射到一些新的B类型

impl＆lt; A＆gt;选项＆lt; A＆gt;的函子{类型Unwrapped = A;类型包装的＆lt; B＆gt; =选项＆lt; B＆gt ;； fn映射＆lt; F：FnMut（A）-＆gt; B，B＞（self，mut f：F）-＞ B。选项＆lt; B＆gt; {match self {Some（x）=＆gt;一些（f（x）），无=>无，}}}＃[测试] fn test_option_map（）{assert_eq！ （Some（5）。map（| x | x + 1），Some（6））; assert_eq！ （None。map（| x：i32 | x + 1），None）;}

而且，如果您使用所有类型的体操运动，您将发现它最终与我们上面针对MyOption特殊设置的map方法相同（没有FnOnce和FnMut之间的差异）。凉！

在Haskell中，不需要任何此类通用关联类型业务。实际上，Haskell函子不使用任何关联的类型。 Haskell中的Functor的类型类早于该语言中相关类型的存在。为了进行比较，让我们看一下外观，将其重命名为与Rust相匹配：

类Functor f其中map ::（a-> b）-＆gt; f a-＆gt; f b实例Functor Option，其中map f option = Some x-＆gt;的case选项。某些（f x）无->没有

特性HktFunctor {fn map＆lt; A，B，F：FnMut（A）-＆gt; B＆gt;（self：Self＆lt; A＆gt; f：F）-＆gt;自我B；选项{fn map 的impl HktFunctor B＆gt;（self：Option＆lt; A＆gt ;, f：F）-＆gt;选项＆lt; B＆gt; {匹配自己{一些（a）=＆gt;一些（f（a）），无=>没有 ， } }}

但这不是有效的Rust！那是因为我们正在尝试为Self提供类型参数。但是在Rust中，Option不是一种类型。选项必须先应用于单个类型参数，然后才能成为类型。选项＆lt; i32＆gt;是一种。期权本身不是。

相反，在Haskell中，也许Int是Type类型的一种。也许是类型构造器，类型->类型。但是您可以为了创建类型类和实例而将Maybe拥有自己的类型。 Haskell中的Functor使用Type-＆gt;类型。这就是“更高种类的类型”的意思：我们可以拥有类型比不仅仅是“类型”高的类型。

在以下示例中，Rust中的GAT是针对缺少HKT的一种解决方法。但是，正如我们最终看到的那样，它们更加脆弱且更加冗长。这并不是说GAT是一件坏事，离它还很遥远。就是说，尝试用Rust编写Haskell可能不是一个好主意。

好的，既然我们已经彻底确定了我们将要做的不是一个好主意，那就去做吧！

在Haskell中，一个有争议的类型类称为Pointed。之所以引起争议，是因为它引入了一个没有任何相关法律的类型类，而这通常不是很喜欢。但是，由于我已经告诉过您，这都是一个坏主意，让我们实现Pointed。

指向对象的想法很简单：将值包装到类似Functor的事物中。因此，对于Option而言，这就像用Some包装它。结果是，使用Ok。对于Vec，它将是一个单元素向量。与Functor不同，这将是静态方法，因为我们没有要更改的现有Pointed值。让我们来看看它的作用：

指向的特征：函子{fn wrap＆lt; T＆gt;（t：T）-＆gt;自：：包裹T} impl＆lt; A＆gt;指向选项＆lt; A＆gt; {fn wrap＆lt; T＆gt;（t：T）-＆gt;选项＆lt; T＆gt; {一些（t）}}

对此特别有趣的是，我们根本没有在Option实现中使用A类型参数。

还有另外一件事值得注意。调用wrap的结果是Self :: Wrapped＆lt; T＆gt;值。我们确切了解Self :: Wrapped＆lt; T＆gt;吗？好吧，从Functor特征定义中，我们确切地知道一件事：Wrapped＆lt; T＆gt;必须是函子。有趣的是，我们在这里已经失去了Self :: Wrapped＆lt; T＆gt;也是有针对性的。对于接下来的几个特征，这将是一个反复出现的主题。

但是，让我重申一下这种不同的方式。当我们使用常规的Functor特征实现时，我们对Wrapped关联类型一无所知，只是它实现了Functor本身。从逻辑上讲，我们知道对于Option＆lt; A＆gt;实施中，我们希望Wrapped是OptionB。之类的事情。但是GAT实施不会强制实施。 （相比之下，Haskell中的HKT方法确实实现了这一点。）没有什么可以阻止我们编写令人毛骨悚然的不明智的实现，例如：

impl＆lt; A＆gt; MyOption＆lt; A＆gt;的函子{类型Unwrapped = A;类型包装的＆lt; B＆gt; =结果＆lt; B，字符串＆gt ;; //会吗？ fn映射＆lt; F：FnMut（A）-＆gt; B，B＞（self，mut f：F）-＞ B。结果＆lt; B，字符串＆gt; {match self {MyOption :: Some（a）=＆gt;确定（f（a）），MyOption :: None =＆gt;错误（＆＃34;嗯，这很奇怪，不是吗？＆＃34;。to_owned（）），}}}

您可能在想，那么，没人会这样写。如果他们这样做，那是他们自己的错。这不是这里的重点。关键是编译器无法知道Self和Wrapped B之间存在联系。而且由于它不知道，所以有些事情我们无法输入check。最后，我将向您展示其中之一。

当我接受Haskell培训后，进入Functor / Applicative / Monad部分，大多数人都对Monads感到不安。以我的经验，真正令人困惑的部分是实用性的。一旦您了解了这一点，Monad相对来说就很简单。

Haskell中的Applicative类型类有两种方法。 pure等同于我放入Pointed中的包装，因此我们可以忽略它。另一种方法是＆lt; *，称为＆＃34; apply，＆＃34;或＆＃34;或领带战斗机。＆＃34;我最初使用与该运算符匹配的名为apply的方法来实现Applicative，但发现最好走另一条路。

取而代之的是，还有一种替代方法，可以基于另一个称为liftA2的函数（或在Rust中为lift_a2）来定义Applicative类型类。这是想法。假设我有两个功能：

我可能不知道当前年份或出生年份，在这种情况下，我将返回None。但是，如果我对这两个函数调用均获得“和”回报，则可以计算出年龄。在普通的Rust代码中，这可能类似于：

fn age（）-＆gt;选项＆lt; i32＆gt; {let birth_year = birth_year（）吗？ ;让current_year = current_year（）吗？ ;一些（当前年份-出生年份）}

但这是杠杆吗？和早日返回。应用程序的主要目的是解决相同的问题。因此，我们将其重写而没有任何提前返回，而是使用一些模式匹配：

fn age（）-＆gt;选项＆lt; i32＆gt; {match（birth_year（），current_year（））{（Some（birth_year），Some（current_year））=＆gt;一些（当前年份-出生年份），_ =＆gt;没有 ， }}

当然可以，但是很冗长。它也不会推广到其他情况，例如结果。还有一个非常复杂的案例，例如“我有一个可以返回出生年份的Future，一个可以返回当前年份的Future，并且我想生成一个可以发现差异的Future。”使用async / await语法，这很容易做到。但是，我们也可以使用我们的lift_a2方法在Applicative中完成此操作。

lift_a2的要点是：我包装了两个值，也许都在一个期权中。我想使用一个函数将它们组合在一起。让我们看一下Rust中的外观：

性状适用：指向{fn lift_a2＆lt; F，B，C＆gt;（self，b：Self :: Wrapped B，f：F）-自：：包裹的C。其中F：FnMut（自我：：未包装，B）-＆gt; C；} impl A ＝ C。适用于选项＆lt; A＆gt; {fn lift_a2＆lt; F，B，C＆gt;（self，b：Self ::包装的B＆gt; mut f：F）-＆gt;自：：包裹的C。其中F：FnMut（自我：：未包装，B）-＆gt; C {让a =自我？ ;令b = b？ ;一些（f（a，b））}}

这是否是一种改进，可能在很大程度上取决于您一生写了多少Haskell。同样，我不主张在这里更改Rust，但这确实很有趣。

fn birth_year（）->结果＆lt; i32，字符串＆gt; {Err（＆＃34;没有出生年份＆＃34;。to_string（））} fn current_year（）-＆gt;结果＆lt; i32，字符串＆gt; {Err（＆＃34;无当前年份＆＃34; to_string（））} fn age（）-＆gt;结果＆lt; i32，字符串＆gt; { 今年 （）。 lift_a2（birth_year（），| cy，by | cy-by）}

可能是哪个问题：我们采用两个Err值中的哪个？嗯，这取决于我们对Applicative的实现，但是通常我们更喜欢选择第一个：

impl＆lt; A，E＆gt;适用于结果＆lt; A，E＆gt; {fn lift_a2＆lt; F，B，C＆gt;（self，b：Self ::包装的B＆gt; mut f：F）-＆gt;自：：包裹的C。其中F：FnMut（自我：：未包装，B）-＆gt; C {match（self，b）{（Ok（a），Ok（b））=>好（f（a，b）），（Err（e），_）=> Err（e），（_，Err（e））=>错误（e），}}}

但是，如果我们两个都想要怎么办？这是Applicative赋予我们权力的情况？不。

Haskell的Validation类型代表了我要尝试很多事情的想法，其中有些可能会失败，我想将所有错误结果汇总在一起。＆＃34;一个典型的例子是Web表单解析。如果用户输入了无效的电子邮件地址，无效的电话号码，并且忘记了单击“我同意”。框，您想生成所有三个错误消息。您不想只生成一个。

要开始我们的Validation实现，我们需要引入一个Haskell-y类型类，这一次是表示＆＃34;将多个值组合在一起的概念。我们可以在这里对Vec进行硬编码，但是这样做的乐趣在哪里呢？取而代之的是，我们引入一个名字奇怪的半群特征。这甚至不需要任何特殊的GAT代码：

特质Semigroup {fn append（self，rhs：Self）-> Self;} impl字符串的半群{fn append（mut self，rhs：Self）->自我{自我+ =＆amp; rhs;自我}}隐含＆lt; T＆gt; Vec＆lt; T＆gt;的半群{fn append（mut self，mut rhs：Self）->自我{Vec :: append（＆amp; mut self，＆amp; mut rhs）; self}} impl Semigroup for（）{fn append（self，（）：（））-> （）{}}

Functor和Pointed实现很无聊，让我们通过Applicative实现直接跳到最前面：

impl＆lt; A，E：Semigroup＆gt;适用于验证＆lt; A，E＆gt; {fn lift_a2＆lt; F，B，C＆gt;（self，b：Self ::包装的B＆gt; mut f：F）-＆gt;自：：包裹的C。其中F：FnMut（自我：：未包装，B）-＆gt; C {match（self，b）{（Validation :: Ok（a），Validation :: Ok（b））=> Validation :: Ok（f（a，b）），（Validation :: Err（e），Validation :: Ok（_））=> Validation :: Err（e），（Validation :: Ok（_），Validation :: Err（e））=>验证：： Err（e），（验证：： Err（e1），验证：： Err（e2））=>验证:: Err（e1。append（e2）），}}}

在这里，我们说的是错误类型参数必须实现Semigroup。如果两个值都为Ok，则将f函数应用于它们并将结果包装在Ok中。如果只有一个值是Err，我们将返回该错误。但是，如果两者都出错，则可以利用Semigroup的append方法将它们组合在一起。这是使用？样式错误处理无法获得的。

最后，可怕的莫纳德抬起头来！但实际上，至少对于Rustaceans而言，单子并不令人惊讶。您已经习惯了它：and_then方法。几乎所有以结尾的语句链？可以将Rust中的Monadic绑定重新想象。在我看来，monad之所以具有这种不可知的吸引力，其主要原因是一系列特别糟糕的教程，这些教程在人们的脑海中凝聚了这个想法。

无论如何，由于我们只是试图匹配Option上and_then的现有方法签名，所以我不会花很多时间来激发“ monad”的作用。相反，我们只看一下特征的定义：

性状Monad：适用{自身：：包装的B。其中F：FnMut（自我：：未包装）-＆gt;自：：包裹B；} impl A；选项＆lt; A＆gt;的Monad {fn bind＆lt; B，F＆gt;（self，f：F）-＆gt;选项＆lt; B＆gt;其中F：FnMut（A）→选项＆lt; B＆gt ;， {self。 and_then（f）}}

就这样，我们得到了Monadic Rust。是时候骑到日落了。

我总体上不是monad变压器的忠实拥护者。我认为它们在Haskell中被过度使用，并导致大量的并发症。相反，我主张使用ReaderT设计模式。但是同样，这篇文章绝对不是关于最佳实践的。

通常，每个monad实例都提供某种附加功能。选项表示＆＃34;它可能不会产生值。＆＃34;结果表示＆＃34;它可能会因错误而失败。＆＃34;如果我们提供了它，则Future意味着它不会立即产生一个值，但最终会产生一个值。作为最后一个示例，Reader monad意味着＆＃34;我对某些环境数据具有只读访问权限。＆＃34;

但是，如果我们想拥有两项功能，该怎么办？没有明显的方法将阅读器和结果结合起来。在Rust中，我们确实通过异步函数和？将Result和Future组合在一起，但是必须精心设计语言支持。相反，针对此问题的Haskell方法将是：仅提供do表示法（用于monad的语法糖），然后分层放置monad转换器以将所有功能加在一起。

我考虑过一段时间写一篇关于这种哲学差异的博客文章。 （如果人们对这样的帖子感兴趣，请让我知道。）但是，现在，让我们简单地探索在Rust中提供monad转换器的外观。我们将在所有最讨厌的monad转换器（IdentityT）中实现它。这是根本不做任何事情的变压器。 （并且，如果您想知道为什么拥有它，请考虑为什么Rust具有1个元组。有时，您需要一些适合特定形状的东西才能使某些通用代码正常工作。）

由于IdentityT不做任何事情，因此很高兴看到它的类型完美地反映了这一点：

我之所以调用类型参数M，是因为它本身就是Monad的实现。这就是这里的想法：每个monad变压器都位于基本monad的顶部。

接下来，让我们看一下Functor的实现。想法是拆开IdentityT层，利用底层的映射方法，然后重新包装IdentityT。

impl＆lt; M：Functor＆gt; IdentityT的函子＆lt; M＆gt; {类型为未包装= M ::未包装；类型包装的＆lt; A＆gt; = IdentityT＆lt; M ：：包裹的A； fn映射＆lt; F，B＆gt;（self，f：F）-＆gt;自身：：包装的B。其中F：FnMut（M ::未包装）-＆gt; B {IdentityT（self。0. map（f））}}

对于关联的类型，我们利用M的关联类型。在地图内部，我们使用self.0来获取基础M，然后包装地图方法的结果

......