PointFree Episode 13: The Many Faces of Map

1. Introduction
1. Swift’s maps
1. Parametricity and theorems for free
1. Define your own map
1. The f word
1. What’s the point?

1. Introduction

今天的话题很重要，这只是一个漫长而深刻旅程的开始。我们想要考虑表面上不起眼的map函数的所有荣耀。许多人指出，语言中map的存在是该语言具有“functional”倾向的有力指标。你会经常听到“语言ABC支持函数概念，如map、filter、reduce等”，并且总是先提到map! 这是为什么呢? !

Swift必须具有双重功能，因为它有两个map!一个在数组上，一个在可选类型上!

我们想要建立一种直觉，来解释为什么map在“functional-leaning”语言中如此普遍，事实上，在我们日常的Swift代码的阴影下，还隐藏着许多其他的maps，我们还没有探索。

2. Swift’s maps

让我们先浏览一下Swift给我们的所有map。在这个系列中，我们已经在这个系列上探索了很多map方法。它用于转换数组中的所有元素，并返回一个全新的数组:

[1, 2, 3]
  .map { $0 + 1 }

[1, 2, 3]
  .map(incr)

我们还定义了一个自由map函数因为我们看到它能更好地组合。让我们重新定义它，但也提供一个从头开始的实现，只是为了向每个人展示这个函数是多么简单:

func map<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    var result = [B]()
    xs.forEach { x in result.append(f(x)) }
    return result
  }
}

然后我们可以做各种有趣的事情，比如:

[1, 2, 3]
  |> map(incr)
[1, 2, 3]
  |> map(incr)
  |> map(square)

我们在玩这些东西时观察到的一个重要规律是，map组合上有突出优势，这具有性能暗示:

[1, 2, 3]
  |> map(incr >>> square)

到目前为止，标准库中还有另一个map，我们只简要提到过，那就是可选map。它允许你安全地展开可选的，执行转换，然后重新包装可选的:

Int?.some(2)
  .map(incr)
Int?.none
  .map(incr)

这意味着map允许您以一种非常安全且富有表现力的方式处理可选项，而不必为了获得内部的值而强行展开它们。

我们之前还在可选项上定义了一个自由map，因为它的可组合性非常好。让我们再做一次，但这次完全执行它，以显示它是多么简单:

func map<A, B>(_ f: @escaping (A) -> B) -> (A?) -> B? {
  return {
    switch $0 {
    case let .some(a): return .some(f(a))
    case .none:        return .none
    }
  }
}

Which can be used like so:

Int?.some(2)
  |> map(incr)
Int?.some(2)
  |> map(incr)
  |> map(square)
Int?.some(2)
  |> map(incr >>> square)

似乎在可选项上的map与在数组上的map具有相同的属性，因为它分布在函数组合上。因为可选项不是零成本抽象，这也有一些性能影响，尽管很小，因为我们没有创建多个可选项。

map满足的另一个属性我们还不需要使用或讨论。为了理解它，让我们看一些有点奇怪的东西:

[1, 2, 3]
  .map { $0 }
Int?.some(2)
  .map { $0 }

这是另一个属性。如果我们为map提供的转换逻辑不做任何事情，那么它将保持结构不变。对于map来说，这似乎是一个非常合理的属性。除了返回参数外什么也不做的函数有一个名字:恒等函数（the identity function）。我们可以这样定义它:

func id<A>(_ a: A) -> A {
  return a
}

这似乎是一个无用的函数，但这意味着我们可以重写之前的调用。

[1, 2, 3]
  .map(id)
Int?.some(2)
  .map(id)

有多少次你在compactMap(或flatMap)中使用{$0}闭包来删除nils ? 现在你可以使用id了!

[1, 2, nil, 3].compactMap(id)
[1, 2, nil, 3].flatMap(id)

在以后的剧集里也会有更多的用途。

我们在这里看到的是，当我们用id进行map时，我们不会改变所映射的值:map保留了恒等函数，就像它保留了函数组合一样:

// map(id) == id

当然，这对于数组和可选项也是成立的。

[1, 2, 3].map(id) == id([1, 2, 3]) // true
Int?.some(2).map(id) == id(Int?.some(2)) // true

恒等函数的另一个特点是，将它与其他函数组合在一起时，其他函数不变:

// f >>> id == f
// id >>> f == f

3. Parametricity and theorems for free

好吧，这很有趣，但那又怎样? 在我们的代码中，我们一直在做这类事情，但却没有什么深刻和美丽的东西，对吗?

好!我在这里告诉你，map是唯一定义的! 除了上面的方法，实际上没有其他方法可以在数组或可选项上定义map。这是自然界的普遍事实! 我们别无选择，只能像上面那样定义map。无论你如何进行哲学思考，在定义map时，没有自由意志!

这可能是真的吗? 但我们可以定义所有类型的函数，它们具有与map相同的签名，但却做一些与map完全不同的事情!让我们从这个存根开始:

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in

  }
}

我们可以将这个函数定义为只返回一个空数组。

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    return []
  }
}

见鬼，我还可以double数组:

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    return xs + xs
  }
}

🛑 Cannot convert return expression of type ‘[A]’ to return type ‘[B]’

哦，等等，x在[A]中，我需要得到[B]。我想我应该映射这个结果:

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    return (xs + xs).map(f)
  }
}

We can keep going!

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    return []
    return (xs + xs).map(f)
    return (xs + xs + xs).map(f)
    return xs.reversed().map(f)
    return Array(xs.prefix(1)).map(f)
    return Array(xs.prefix(2)).map(f)
    return Array(xs.suffix(1)).map(f)
    return Array(xs.suffix(2)).map(f)
  }
}

那么这到底有什么独特之处呢?

嗯，它是独特的，但有一个警告。虽然map在所有具有此签名的函数中不是唯一的，但它是唯一满足我们之前观察到的属性的函数:map(id) == id。我们定义的所有lift都没有这个属性。它们通过变换数组、取子集或重复元素来改变数组的结构。此外，我们不得不在shuffle之后使用map来转换数组，这并非巧合。我们也可以在shuffle之前调用map:

func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] {
  return { xs in
    return []
    return xs.map(f) + xs.map(f)
    return xs.map(f) + xs.map(f) + xs.map(f)
    return xs.map(f).reversed()
    return Array(xs.map(f).prefix(1))
    return Array(xs.map(f).prefix(2))
    return Array(xs.map(f).suffix(1))
    return Array(xs.map(f).suffix(2))
  }
}

我们在这里看到的是，因为这个函数签名是完全通用的，我们对A和B一无所知，除了我们有一个f可以把A转换成B，函数的执行是非常严格的。我们不能过滤掉，比如说，偶数因为我们不知道我们处理的是整数。我们不可能所有的值都等于其他的值因为我们不知道我们在处理的是Equatable东西。我们不能取所有大于某些值的值，因为我们不知道我们处理的是Comparable东西。

在执行过程中，我们没有太多的选择。我们被迫进入两种情况之一:要么用map(f)转换数据，然后应用我们的shuffling，要么用map(f)应用我们的shuffling并转换。

此的正式声明如下:

// If f, g are functions
// then lift(f) >>> map(g) == map(f) >>> lift(g)

这对任何lift函数都成立。这有点像map是足够普遍的，它可以“缠绕(intertwine)”自己的任何其他功能，有相同的签名。让我们来看一些具体的例子:

let xs = [1, 2, 3, 4, 5]
let f = incr
let g = { (x: Int) in String(x) }

let lhs = lift(f) >>> map(g)
let rhs = map(f) >>> lift(g)

lhs(xs) == rhs(xs) // true

它为true是有意义的，因为lift目前返回一个空数组。

lhs(xs) // []
rhs(xs) // []

但它仍然适用于我们定义的每一个lift! 我们可以为xs使用任何数组，为f和g使用任何函数(只要它们组成)，以及任何lift实现。这个等式是成立的。

因此，考虑到map与所有lift实现相互交织的普遍性质，我们可以得出什么结论。如果lift也满足lift(id) = id属性，那么lift和map之间的关系会怎样呢?

让我们假设lift(id)与id相同，看看会发生什么。鉴于我们之前的公式:

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

We can swap f out for id!

// lift(id) >>> map(g) == map(id) >>> lift(g)

We can now swap both lift(id) and map(id) out for id.

// id >>> map(g) == id >>> lift(g)

我们还知道函数的组合恒等式与函数本身是相同的，所以我们可以删除这些组合。

// map(g) == lift(g)

你瞧:map和lift的功能是一样的! 当我们要求lift(id) = id时，我们突然得到了map和lift必须是相等的事实!
这已经“证明”了map的普适性! 它独特的功能和它的签名保持了一致性。

我们在这里所掌握的基本思想被称为参数性，它只在支持参数多态性的语言中可见，Swift使用泛型就可以做到这一点。它允许您通过引入类型参数来编写适用于许多形状的代码。这与其他形式的多态性(如子类型多态性)形成对比，在子类型多态性中，您可以通过创建超类型的子类型(如子类化)来编写适用于多种形状的代码。

在1989年，也就是大约30年前，菲利普·瓦德勒发表了一篇名为《自由定理》的论文，证明了一个非常棒的结果。它本质上是说，给定一个适当的泛型函数，比如我们的map，就会有一个相应的定理可以自由地跳出来，就像我们的纠缠特性lift(f) >>> map(g) = map(f) >>> lift(f)。

这适用于任何完全泛型函数!举个例子:

func r<A>(_ xs: [A]) -> A? {
  fatalError()
}

这里隐藏着一个定理，它显示了数组上的映射与可选上的映射是如何相互缠绕的! 但我们要把细节留给练习!

4. Define your own map

标准库并不是我们唯一应该定义map的地方。你也应该根据自己的习惯类型来定义它们，只要它们符合规范。我们可以定义什么类型的map?

我们以前遇到过的一种类型是Result类型。

enum Result<A, E> {
  case success(A)
  case failure(E)
}

它的免费map会是什么样子?

func map<A, B, E>(_ f: @escaping (A) -> B) -> (Result<A, E>) -> Result<B, E> {
  return { result in
    switch result {
    case let .success(a):
      return .success(f(a))
    case let .failure(e):
      return .failure(e)
    }
  }
}

给定一个函数(A) -> B, map将它提升到一个函数(Result< A, E>) -> Result<B, E>，在其中转换结果的成功情况。这允许您安全地展开结果以获得它的值，应用转换，然后将其包装回结果中。

What’s this look like in use?

Result<Int, String>.success(42)
  |> map(incr) // .success(43)
Result<Int, String>.failure("Error")
  |> map(incr) // .failure("Error")

我们看到，它映射了success的一面，而保留了failure。

现在，你可能会想:为什么我们只绘制结果的成功一面? 你想知道这一点是完全正确的，事实是没有特别好的理由。map函数被定义为一次只操作一个类型，因此我们必须选择一方。我们选择的立场只不过是社会的惯例。但是我们也可以很容易地定义一个故障情况的映射它是完全有效的。社区可能会选择成功案例，因为作为程序员，我们通常更关注“快乐”路径而不是错误路径。

这并不与map的唯一性相矛盾，因为我们这里有两个不同的映射在两个不同的泛型参数上。对于数组和可选项，我们只有一个泛型。我们真正拥有的是每个泛型参数都有一个唯一的map实现。

在以后的章节中，我们将探索一种方法，将这两个映射连接到一个概念中，这实际上将大大简化我们的类型。

既然我们发现用我们自己的类型来定义map完全没问题，让我们用一些例子来说明这个函数有多常见。举个例子:

struct F1<A> {
  let value: A
}

我甚至不想给它命名，让我们抽象地关注类型。它是一个封装泛型值A的包装器。让我们定义这样一个类型上的map是什么样子的:

func map<A, B>(_ f: @escaping (A) -> B) -> (F1<A>) -> F1<B> {
  return { f1 in

  }
}

我们知道这是它应该有的形状，那么我们可以实现它吗?

func map<A, B>(_ f: @escaping (A) -> B) -> (F1<A>) -> F1<B> {
  return { f1 in
    F1(value: f(f1.value))
  }
}

因此，映射这个类型中的值意味着简单地展开值，用f转换它，然后再次包装它。

那么，map(id) == id是否为真呢?让我们考虑一下body。

//return { f1 in
//  F1(value: f(f1.value))
//}

用id替换f

//return { f1 in
//  F1(value: id(f1.value))
//}

id保持它的值不变。

//return { f1 in
//  F1(value: f1.value)
//}

并且f1和**f1 (value: f1.value)**是等价的。

//return { f1 in
//  f1
//}

It’s the identity function!

//return { $0 }

的确，似乎我们已经为F1偶然发现了一个真正的map。

让我们试另一个!看看这种类型:

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

它只是一个函数的包装器。我声明，可以为B型泛型参数定义一个类似映射的函数:

func map<A, B, C>(_ f: @escaping (B) -> C) -> (F2<A, B>) -> F2<A, C> {
  return { f2 in
    return F2 { a in

    }
  }
}

我们在这里能做什么? 我们有一些在A中的东西，我们有一些把A变成B的东西，我们有一些把B变成C的东西! Well it pretty much writes itself:

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

我们甚至可以通过使用我们最喜欢的操作符来缩短它:

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

同样，我们可以看到map(id) == id当我们用id替换f时

//return { f2 in
//  F2(apply: f2.apply >>> id)
//}

我们知道，组合成id会使另一个函数不变。

//return { f2 in
//  F2(apply: f2.apply)
//}

现在我们来看看等价类型。

//return { f2 in
//  f2
//}

再来一次恒等函数。

//return { $0 }

这是F2上唯一定义的map。

现在您可能想知道我们是否可以在F2的A一般参数上定义一个map，这似乎是合理的。

然而，这样做有一个小问题。我们现在还不想透露，所以我们把它留作本集的练习，我们会在以后的一集里介绍它!

再来一个怎么样?

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

哇，这个真奇怪! 它是一个函数的包装器，它接受一个函数作为参数，但不返回任何东西。这个形状应该让人想起你处理过的回调api，即使是在UIKit和Cocoa中。例如，在UIKit中你经常呈现视图控制器，在那个签名中你会发现这个形状:

//URLSession.shared.dataTask(with: <#T##URL#>, completionHandler: <#T##(Data?, URLResponse?, Error?) -> Void#>) -> Void

我们能在这个奇怪的东西上定义map吗!让我们看看!

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

    }
  }
}

天啊，我们到底能做什么! 好吧，让我们来看一些类型，看看它们是如何匹配的:

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

这些是怎么连接在一起的? 好吧，唯一匹配的是f的输出和callback的输入匹配，所以我们可以从这里开始:

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

好吧，现在，最后一行正是我们需要提供给f3.run的内容!

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

同样，我们可以很容易地验证map(id) == id如果我们把f换成id。

//return { f3 in
//  return F3 { callback in
//    f3.run(id >>> callback)
//  }
//}

复合让我们的callback保持不变。

//return { f3 in
//  return F3 { callback in
//    f3.run(callback)
//  }
//}

现在F3直接把它的回调函数传递给block:

//return { f3 in
//  return F3(run: f3.run)
//}

所有的东西都被整齐地折叠成恒等函数!

//return { f3 in
//  f3
//}

Our map is indeed the universal map for this type.

//return { $0 }

现在，我们对这些类型使用了非常抽象的名称，以便不去关注它们的任何特定性质，因为这些对于定义map都无关紧要。
你甚至可能知道一些或所有这些类型的专有名称，如果不知道，你很快就会在未来的Point-Free剧集中知道。

看到我们刚刚定义的所有地图的签名也很有趣:

// func map   <A, B>(_ f: (A) -> B) -> (F1   <A>) -> F1   <B>
// func map<R, A, B>(_ f: (A) -> B) -> (F2<R, A>) -> F2<R, B>
// func map   <A, B>(_ f: (A) -> B) -> (F3   <A>) -> F3   <B>

令人惊讶的是，我们可以用所有这些类型来定义map，我们得到了一幅独一无二的map。

5. The f word

既然我们已经知道map是一个如此普遍的概念，你可能会认为它应该有个名字。现在，在Point-Free上，我们已经花了很长时间来介绍一些概念，带有很多动机，而没有陷入术语中。然而，我们仍然希望我们的观众知道这些术语，以便他们可以继续学习这些主题。

所以，我想我们已经准备好定义第一个函数式编程术语了，它有一点可怕的名声。我们要说“f”这个词:“functor”。

是的，这里我们要抓住的概念是一个函子。functor是一种带有functor类函数的类型。数组是一个functor，因为它有map。Optional是一个functor，因为它有map。Result是一个functor，因为它有map。所有这些从F1到F3的奇怪类型都是functor，因为它们有map!

所有这些看起来完全不同的类型都被functor的概念联系在一起，因为它们带有一个映射函数，允许人们将函数带入它们的世界。

现在，关于“functor”这样一个抽象的名称的一个伟大的事情是，它没有包袱，人们选择如何理解这个概念。我们刚刚探索的每种类型，无论是Result、Array、Optional还是F1到F3，都有自己特定于领域的方法来直观地了解它们所代表的内容。例如，一个可选的有点像一个容器，里面有一个可能不存在的值。数组就像一个可以容纳很多值的容器。对于所有这些事情，没有单一的直觉。

因此，我们认为避免对functor过于直观的描述，而只依赖于它最基本的属性是有帮助的:它有一个map函数，并且map函数必须满足map(id) == id的属性。然后我们得到了map保持函数复合的奇妙性质，即map(f >>> g) == map(f) >>> map(g)。

6. What’s the point?

我们已经深入抽象了。这种map知识如何适用于日常代码?

理解map的普遍属性对于了解它来自哪里以及如何为我们自己的类型定义它非常重要! 我们很习惯在Array和Optional中使用map，因为这些函数都是Swift自带的，而且我们已经开始看到我们可以以同样的表达能力处理这两种类型。我们可以也应该在我们自己的类型上定义它，这样我们就可以以同样的、富有表现力的方式处理我们的类型。

虽然参数性和“免费定理”可能看起来很学术，但它们帮助我们认识到Swift的类型系统是多么强大，以及它如何推动我们把我们写的代码看作是发现，而不是发明!

Kayouyou's Den