PointFree Episode 14: Contravariance

1. Introduction
1. Variance in subtyping
1. Variance in functional programming
1. Positive and negative positions
1. What’s the point?
1. PredicateSet
- 6.1. Set cannot hold infinitely many values
- 6.2. PredicateSet cannot be iterated over
- 6.3. Set cannot be inverted
- 6.4. PredicateSet cannot conform to Equatable
1. Set does not have map

1. Introduction

上周我们深入研究了map函数。首先，我们看到数组上的map在所有转换数组并满足简单属性的函数中是唯一的。这有点令人惊讶，因为这表明map的发明不是因为它方便，而是它只是坐在那里等着我们去发现它。

在今天的课程中，我们将探讨“contravariance（逆变性）”的概念。这是一种隐藏在编程世界中显而易见的组合，但无论出于什么原因，我们从来没有真正地与它面对面。所以我们想花些时间来真正研究它，并为它建立直觉，因为它将让我们发现新的方式来组成的东西，否则很难看到。

2. Variance in subtyping

如果你在编程中遇到过协方差和逆变性的概念，它很可能与子类型有关，你甚至可能听说过Liskov替换原理。这是关于什么时候用更具体的类型(如子类)或更一般的类型(如超类)来替换类型是有意义的。在某些情况下，你可以做一种而不做另一种，或者反过来。

Swift通过子类化实现了子类型。我们应该都很熟悉这个，因为UIKit是一个用非常深的子类层次结构构建的库。只要考虑这个将UIButton连接到它的根基类NSObject的子类序列:

// NSObject > UIResponder > UIView > UIControl > UIButton

我们使用>来显示超类型关系，我们还将使用<来显示子类型关系。

当与UIKit交互时，我们经常编写函数和方法，将UIKit组件作为输入或返回UIKit组件作为输出。当我们这样做的时候，我们将不可避免地遇到需要为这些函数提供子类型或超类型，或者将函数的输出解释为子类型或超类型。让我们来看一个例子:

func wrapView(padding: UIEdgeInsets) -> (UIView) -> UIView {
  return { subview in
    let wrapper = UIView()
    subview.translatesAutoresizingMaskIntoConstraints = false
    wrapper.addSubview(subview)
    NSLayoutConstraint.activate([
      subview.leadingAnchor.constraint(
        equalTo: wrapper.leadingAnchor, constant: padding.left
      ),
      subview.rightAnchor.constraint(
        equalTo: wrapper.rightAnchor, constant: -padding.right
      ),
      subview.topAnchor.constraint(
        equalTo: wrapper.topAnchor, constant: padding.top
      ),
      subview.bottomAnchor.constraint(
        equalTo: wrapper.bottomAnchor, constant: -padding.bottom
      ),
      ])
    return wrapper
  }
}

这是一个帮助函数，用于将现有视图包装到新视图中并应用一些填充。这是一个方便的功能，因为UIView在其布局中没有填充的概念。我们的偏好是先配置后转换，这是一个curry过的函数，它首先获取填充，然后你得到一个(UIView) -> UIView函数，它包装视图。

下面是我们如何使用它:

let view = UIView(frame: CGRect(x: 0, y: 0, width: 100, height: 100))
view.backgroundColor = .darkGray

let padding = UIEdgeInsets(top: 10, left: 20, bottom: 30, right: 40)

let wrapper = wrapView(padding: padding)(view)
wrapper.frame.size = CGSize(width: 300, height: 300)
wrapper.backgroundColor = .lightGray
wrapper

这个函数为探索逆变性提供了完美的设置。下面是wrapView的特征:

wrapView(padding: padding) as (UIView) -> UIView

没有惊喜。现在，让我们尝试调整输入类型。如果这个函数对我们提供它的UIView是满意的，那么它肯定对我们提供的，比如说一个UIButton也是满意的:

wrapView(padding: padding) as (UIButton) -> UIView

确实如此! 我们可以使用UIView的任何子类:

wrapView(padding: padding) as (UIControl) -> UIView
wrapView(padding: padding) as (UISwitch) -> UIView
wrapView(padding: padding) as (UIStackView) -> UIView

因此，我们看到的是，在输入上，我们可以自由地替换一个更具体的类型(即子类)，并且仍然得到一个有效的函数。如果我们尝试在UIView的超类中输入会发生什么?

wrapView(padding: padding) as (UIResponder) -> UIView

🛑 ‘(UIView) -> UIView’ is not convertible to ‘(UIResponder) -> UIView’

当然这不起作用，因为函数至少需要一个UIView，而UIResponder没有添加到视图层次结构的概念。所以我们看到我们不能用超类来代替这个函数的输入。

让我们在输出上试试。如果我们想返回一个UIButton而不是一个UIView呢:

wrapView(padding: padding) as (UIView) -> UIButton

🛑 ‘(UIView) -> UIView’ is not convertible to ‘(UIView) -> UIButton’

这并不能执行。这是有道理的，wrapView实例化并返回一个UIView，所以不抱希望将它解释为一个UIButton。然而，我们可能会忘记UIView的一些特性，而将其解释为更一般的东西，比如一个UIResponder:

wrapView(padding: padding) as (UIView) -> UIResponder

或者回到NSObject

wrapView(padding: padding) as (UIView) -> NSObject

我们甚至可以忘记更多关于这个类型的信息，并返回AnyObject!

wrapView(padding: padding) as (UIView) -> AnyObject

我们在这里发现，函数有子类型关系，就像子类一样，它有微妙的不同，取决于你是改变函数的输入还是输出。例如，我们已经看到(UIView) -> UIView是(UIButton) -> UIView的一个子类型，因为你可以在任何使用前者的地方你可以使用后者。该函数只是忘记了我们有一个按钮，并将其视为一个普通视图。另一方面，我们已经看到(UIView) > UIView是(UIView) > UIResponder的子类型因为在任何你可以使用前者的地方你可以只使用后者。我们只是忘了我们有一个视图，把它当作一个简单的响应器。

Correction
在视频中，我们无意中说了与我们对函数输出的子类型定义相反的话。我们说(UIView) > UIResponder是(UIView) > UIView的子类型，但我们实际上想说相反的:(UIView) -> UIView是(UIView) -> UIResponder的子类型。这是因为UIView是UIResponder的子类型。这是一个非常微妙的区别，可能很难在你的头脑中保持清楚。

让我们将其一般化，以便我们能更好地看到结构，使用<表示“**”的子类型:

/*
  If A < B, then

  then (B -> C) < (A -> C)

  then (C -> A) < (C -> B)
*/

这里有些奇怪的东西，但现在还看不出来。要看到它，我们需要移动到一个二维图片!

/*
  If A < B

  then B -> C
         <
       A -> C

  then C -> A
         <
       C -> B
 */

C组总是分组在一起! 如果我们把它们排成一行，就会更明显!

/*
  If A < B

  then B -> C
         <
       A -> C

  then      C -> A
              <
            C -> B
 */

在第一个关系中，A和B相对于“是一个子类型”关系的位置被翻转了。它从" A是B的子类型"变成"包含B的某物是包含A的某物的子类型"。角色互换了。

而在第二种关系中，角色没有互换。它从" A是B的一个子类型"变成" 包含A的某物是包含B的某物的子类型"

这就是变异的本质。当一个关系的顺序保持不变时，我们称之为协变，当一个关系反过来时，我们称之为逆变。我们已经知道，根据函数的输出对函数进行分类是协变关系，而根据函数的输入对函数进行分类是逆变关系。

/*
  If A < B

  then B -> C
         <              contravariant
       A -> C

  then      C -> A
              <         covariant
            C -> B
 */

这也是描述Liskov替换原则的一种非常简洁的方式，该原则表示“如果A是B的子类型，那么包含B类型对象的程序可以用A类型对象替换，而不改变其结果。”这似乎很合理! 但也许我们现在可以更清楚地看到，隐藏在这一陈述的简单地点是一种关系的逆转。你甚至可以看到这句话是如何提出的:“如果A是B的子类型，那么B类型的对象可以被A类型的对象替换”!很酷的东西!

不幸的是，这是我们了解协方差和逆变性的唯一途径。在编程中有很多这样的实例，但是如果您只熟悉Liskov替换原则，那么很难看到。这就是为什么我认为逆变的主题正好属于函数式编程领域(更普遍的是数学领域)，因为从函数的角度看它几乎是微不足道的。让我们探索这个!

3. Variance in functional programming

到目前为止，我们已经在这个系列中遇到过几次协变结构，但我们只是从来没有这样命名它们，因为我们还没有遇到逆变的东西来对比它们。协变关系的一个例子是我们的老朋友map:

func map<A, B>(_ f: (A) -> B) -> ([A]) -> [B] {
  fatalError("Unimplemented")
}

注意，我们有一个关系(A) -> B被提升到一个关系([A]) -> [B]。A和B相对于->的顺序保持不变。事实上，我们遇到的所有map都是协变的:map在可选值上，map在Result上，以及所有我们在map和参数化章节中定义的奇怪map。

我们在上一集中讨论过一种特殊类型。我们给它起了一个抽象的名字F2，但现在我们要给它一个正式的名字:

struct Func<A, B> {
  let apply: (A) -> B
}

它只是一个从A到B的函数包装结构。我们在那一集中看到，这个类型在第二个类型参数B上支持一个类似于映射的函数:

func map<A, B, C>(_ f: @escaping (B) -> C) -> ((Func<A, B>) -> Func<A, C>) {
  return { g in
    Func(apply: g.apply >>> f)
  }
}

注意B和C之间的关系被保留了，因此这是一个协变运算。有趣的是，函数的输出map是协变的，就像输出的子类型是协变的一样!

但是，我们故意没有考虑map到输入类型参数A意味着什么。 Let’s see what happens when we try:

func map<A, B, C>(_ f: @escaping (A) -> B) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    f as (A) -> B
    g.apply as (A) -> C
    // ???
  }
}

这些函数不匹配，所以没有办法组合它们。

让我们尝试一些奇怪的东西把变换函数从(A) - >B翻转到(B) - >A。

func map<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    f as (B) -> A
    g.apply as (A) -> C
    return Func(apply: f >>> g.apply)
  }
}

现在一切都匹配并编译了。但这并不是我们所熟知和喜爱的map，所以我们或许可以称之为fakeMap。

这个fakeMap实际上是我们想要的东西，当它涉及到“转换”一个函数的输入，所以我们应该给它一个适当的名字。
如果map是协变的，那么也许我们应该叫它contramap。事实上，这是许多语言和库所使用的，尽管有些也使用cmap和comap。

func contramap<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    Func(apply: f >>> g.call)
  }
}

Correction
Although contramap is a really nice name for this operation, we have since decided to go with a more intuitive name: pullback. The idea is that we can pull back structures on one type to structures on another type by performing function pre-composition. To find out more about why we did this, refer to our blog post on the topic.

另一种箭头从map翻转的理解方式是，我们可以复制粘贴Func上map的实现，并字面上翻转>>>箭头!

func contramap<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
//    Func(apply: f >>> g.call)
    Func(apply: g.apply <<< f)
  }
}

在关于setter的章节中，我们将<<<定义为向后合成，以便将嵌套的setter组合在一起，向后合成有助于描述我们更深入地研究结构的直觉。 <<<如何帮助我们显式地显示在这个类型上定义map和contramap的区别是很有趣的。

现在我们已经看到了函数箭头->在其输出中是协变的，这意味着我们可以通过后合成对其输出进行“map”。我们还看到函数箭头->在其输入中是逆变的，这意味着我们可以通过预合成对其输入进行“反映射”。

4. Positive and negative positions

好了，既然我们理解了什么是逆变，从技术上讲，让我们做一点工作来适应它因为它看起来有点奇怪，和我们的直觉相悖。由于逆变性似乎很自然地从函数签名中跳出来，让我们看看在更复杂的函数中会发生什么。

例如，在上一集关于map和参数化的内容中，我们遇到了以下奇怪的类型:

struct F3<A> {
  let run: (@escaping (A) -> Void) -> Void
}

我们注意到它有点像我们在Cocoa或其他库中可能遇到的回调。

现在A出现在函数箭头->的左边，所以我们很自然地认为这是一个逆变结构。然而，在上一集中，我们定义了一个map操作，并说明了这是map的唯一实现:

func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3<B> {
  return { f3 in
    return F3 { callback in
      f3.run(f >>> callback)
    }
  }
}

这显然是协变的，这里发生了什么? 注意到A出现在->的左边两次。这是一种双逆变的，而且不知何故它们相互中和。这类似于-1 * -1 = 1，或者如果你从几何上反映某物两次，你就会回到开始的地方，或者两个错误是如何得到一个正确的

这个与数字负号的类比非常强大，我们可以使用它作为一个工具来解开构造中类型参数的方差。我们首先说，如果类型参数出现在->的右侧，则它处于“正”位置;如果它出现在->的左侧，则它处于“负”位置。

// (A) -> B
//  -1    +1

B在正位置，A在负位置。

我们也可以用这个符号术语来表示整个表达式的符号。例如:

// ((A) -> Void) -> Void
//  |_|    |__|
//  -1      +1
// |___________|    |__|
//      -1           +1

在这里，**((A) -> Void)**项处于负位置，然后(A)在其内部处于负位置。

现在，要确定类型参数位置的符号，我们只需将从外层移动到内层时穿过的所有-1和+1相乘。在这个例子中，为了得到A，我们与-1交叉然后再与-1交叉，因此-1 * -1 = 1 A处于正位置。
让我们看一个更复杂的函数:

// (A) -> ((B) -> C) -> D)

这是一个在A中接受一个值并返回一个函数的函数。

在外层我们有两项

// (A) -> ((B) -> C) -> D)
// |_|    |______________|
// -1           +1

第二项有更多的层，深入研究一下，我们看到我们又多了两项:

// (A) -> ((B) -> C) -> D)
//         |_______|   |_|
//            -1       +1
// |_|    |______________|
// -1           +1

中间还有一层，我们再来看看:

// (A) -> ((B) -> C) -> D)
//         |_|   |_|
//         -1    +1
//         |_______|   |_|
//            -1       +1
// |_|    |______________|
// -1           +1

哇!让我们从外层到内层然后把所有的符号相乘看看A B C D的方差是多少

对于A，我们只有一层-1，所以A在负位置，是逆变的。
对于B，我们经过+1，然后-1，然后-1，所以B是正的，协变的。
对于C，我们经过+1，然后-1，然后+1，所以C是负的，是逆变的。
对于D，我们经过+1，然后+1，所以D是正的，是协变的。

我们看到B和D是协变的，A和C是逆变的，因此你应该能够分别在这些类型参数上定义map和contramap。

这是一个方便的工具，能够立即解开类型参数的方差。

5. What’s the point?

好吧，这很有趣，但也很紧张。现在我们看到了协方差和逆方差的概念由于分类的不同，我们可能已经对它们有点熟悉了。然后我们发现这只是函数方差的一种特殊情况，也就是函数的预合成和后合成，这使得它看起来非常简单尽管它的名字很吓人。

但是，是时候问一问:这有什么意义?我们能在日常代码中使用它吗?

是的!当然!逆变性是协方差的另一半，或者说对偶，协方差是我们经常遇到的对我们很有用的东西。所以我们可以很自然地找到逆变性的用处。这和代数数据类型的情况是一样的。很长一段时间以来，我们一直使用产品类型，结构体，因为我们只知道这些。然后有一天，我们被介绍到求和类型，枚举，它们起初看起来很奇怪，但我们发现它们有很多用处。

让我们来看一个特定的例子。大家可能都很熟悉Swift中的Set类型。它是一种无序集合类型，最多保存一个值的实例:

// Set<A>
let xs = Set<Int>([1, 2, 3, 4, 4, 4, 4])

关于这种类型的一个奇怪的事情是泛型被限制为Hashable，它继承自Equatable。所以你被限制在可以放入集合的值的类型上。这样做的原因是为了优化值的内部存储方式，它必须是某种哈希映射，比如[A: Bool]类型。它也有一个缺点，你不能有一个集合来保存A中的所有值，你也不能对一个集合进行反变换。

6. PredicateSet

还有另一种表示集合的方法，它只是一个简单的谓词函数:

struct PredicateSet<A> {
  let contains: (A) -> Bool
}

这完全跳过了如何在一个集合中存储值的问题，直接回答了这个问题:“这个集合是否包含一个特定的值”。

Set的许多用法可以用PredicateSet代替，例如:

let ys = PredicateSet { [1, 2, 3, 4].contains($0) }

我们来玩个小游戏吧!对于我所宣称的Set的每一个缺点，我将证明PredicateSet可以弥补这个缺点，相反地，对于PredicateSet的每一个缺点，我们将看到Set在这方面优于。

6.1. Set cannot hold infinitely many values

由于Set与存储值密切相关，所以它不可能存储无限多个值。Swift对“无限多个值”的回答通常是Sequence协议，但这对测试序列中是否包含一个值没有帮助。

另一方面，PredicateSet在本质上只是一个contains函数，它擅长于建模包含无限多个值的集合:

let evens = PredicateSet { $0 % 2 == 0 }
let allInts = PredicateSet<Int> { _ in true }
let longStrings = PredicateSet<String> { $0.count > 100 }

6.2. PredicateSet cannot be iterated over

实际上，因为PredicateSet只是一个函数，所以没有办法遍历a: A中**contains(a)**为true的所有值。

另一方面，Set当然可以很容易地做到这一点:

xs.forEach { print($0) }

6.3. Set cannot be inverted

因为集合不能包含无限多个值，所以它通常不能被反转。也就是说，不能将它转换为一个集合，该集合包含类型a中所有不在该集合中的值。

另一方面，PredicateSet对此没有问题。例如，我们可以将xs集合反转，使其包含不包含在集合中的所有整数。

let allIntsNot1234 = PredicateSet { !ys.contains($0) }

我们甚至可以为所有谓词集创建一个更通用的函数，但我们把它留着作为练习!

6.4. PredicateSet cannot conform to Equatable

一般来说，不能确定两个函数是否相等，即f:(A) -> B和g:(A) -> B，那么我们不能确定对于所有A: A, f(A) == g(A)。这意味着我们不能使PredicateSet: Equatable，因此永远无法知道两个集合是否相等，甚至一个是另一个的子集。这通常是非常重要的!

7. Set does not have map

这是一个很大的问题，可能会让我们的观众有点惊讶，但Set没有地图，至少不是我们期望的方式。根据我们在map和参数化的章节，我们期望Set上的map有以下形状:

func map<A, B>(_ f: @escaping (A) -> B) -> (Set<A>) -> Set<B> {
  fatalError("Unimplemented")
}

首先，这是不正确的，因为A和B需要被限制为Hashable。现在，Swift不需要这个，因为它试图帮助你，推断它，因为它知道Set需要Hashable。

所以在底层，它看起来像:

func map<A: Hashable, B: Hashable>(_ f: @escaping (A) -> B) -> (Set<A>) -> Set<B> {
  fatalError("Unimplemented")
}

但是现在我们通过约束类型参数破坏了函数的泛型性。它不再被允许在所有类型上工作，这正是让我们能够将参数化应用于map，并给予我们“theorems for free”的原因。

也不是所有类型都能符合Hashable，比如Func类型，所以这种形式的map肯定排除了一些有用的东西。

这张map有更多的问题，让我们看看如何实现它:

func map<A: Hashable, B: Hashable>(
  _ f: @escaping (A) -> B
  ) -> (Set<A>) -> Set<B> {

  return { xs in
    var ys = Set<B>()
    for x in xs {
      ys.insert(f(x))
    }
    return ys
  }
}

因为Set中的值是唯一的，因为它们符合Equatable，我们可以很明显的看出 map一个集合并得到更小的结果是可能的:

let zs: Set<Int> = [-1, 0, 1]
zs
  |> map(square)
// {0, 1}

这似乎很奇怪。到目前为止，我们的map还没有一幅具有这种破坏性。也许这看起来不是什么大问题，但这个问题表现出了一个更大的问题，那就是它打破了我们对map的构图直觉。回想一下，我们经常说“构图的构图是构图的构图”。这意味着:

// map(f >>> g) == map(f) >>> map(g)

我们已经看到这个属性对许多map都是正确的，包括数组、可选项、结果、元组上的第一个和第二个函数等等。我们还看到，它可以带来实际的性能提升，因为它允许我们一次对包含的值应用两个转换，而不是使用一个转换创建一个中间容器。

不幸的是，我们在Set上定义的映射完全打破了这一点。最快的方法是定义一个新的泛型类型和一个简单的Hashable实现:

struct Trivial<A>: Hashable {
  let value: A

  static func == (lhs: Trivial, rhs: Trivial) -> Bool {
    return true
  }

  var hashValue: Int {
    return 1
  }
}

那么这种类型会有什么问题呢?

zs
  |> map(Trivial.init >>> ^\.value)
// {-1, 0, 1}

zs
  |> map(Trivial.init)
  |> map(^\.value)
// {-1}

哎呀，真糟糕!这个问题可以在实际代码中体现出来!例如，您可能有一个等价的一致性，只测试字段的子集，比如可能只测试用户的id字段。然后，当您以各种方式转换一组用户时，您可能(甚至是临时)有两个彼此相等的用户，然后set将它们合并为单个值。

我们在这里看到的是，如果我们想从其他地图中得到所有相同的直觉，那么Set上的map就没有意义。

很不幸的是，Swift确实在Set中有一个map，但这只是因为Set符合序列协议。幸运的是，Swift的类型系统不够强，无法表示map转换到同一个容器中，因此该函数实际上返回的是数组，而不是set:

zs.map(Trivial.init).map(^\.value)
// [-1, 0, 1]

然而，我们仍然不能依赖结果数组的顺序，但至少我们没有丢失值。如果这个方法有不同于map的名字就好了因为它不共享其他map的任何属性。

Kayouyou's Den