函数式编程——Functor、Applicative、Monad

了解函数式编程的同学可能或多或少都听说过 函子（Functor）、适用函子（Applicative）、单子（Monad）等概念，但是，能真正理解的人可能就比较少了。网上有很多相关的文章，甚至有一些书籍也开辟了章节进行了介绍，但是能解释清楚的，寥寥无几。最近，我出于阅读 RxSwift 源码，花时间研究了这几个概念。本文是我在理解函子、适用函子、单子等概念之后作出的总结。

本文使用的示例编程语言为 Swift。

基本概念

类型构造体

类型构造体（Type Constructor），简而言之，即：以泛型作为参数来构建具体类型的类型，可以简称为泛型类。通过类型构造体，我们能够抽象出更加通用的数据类型。Swift 中内置的 Optional<Wrapped> 和 Array<Element> 都是类型构造体。

不相交联合体

不相交联合体（Disjoint Union）类似于 C 语言中的 联合体（Union）数据类型，可以认为是一种包装类型，能够在同一个位置上容纳不同类型的单个实例。函数式编程中常用的数据结构 Either 类型就是一种不相交联合体类型，如下所示为一个容纳 Int 类型的 Either 类：

enum Either {
    case left(Int)
    case right(Int)
}

泛型不相交联合体

当我们将 类型构造体 和 不相交联合体 组合在一起使用时，能够抽象出更加通用的泛型不相交联合体类型。如下所示，Either 类可以通过为 L 和 R 绑定不同的泛型类型来定义一个包装类。

enum Either<L, R> {
    case left(L)
    case right(R)
}

在 Swift 中，内置的 Optional 类型就是一种可以通过泛型进行绑定的包装类，如下所示：

enum Optional<Wrapped> {
    case none
    case some(Wrapped)
}

Swift 中的 Array 也是一种特殊包装类，不过，Array 只能绑定一种泛型类型。

下文，我们将通过自定义一种不相交联合体 Result 类型，分别介绍函子、适用函子、单子。

enum Result<T> {
    case success(T)
    case failure
}

Functor

在普通情况下，使用函数对一个值进行操作，如：对 Int 值进行 +3 操作，我们可以定义一个 plusThree 函数：

func plusThree(_ addend: Int) -> Int {
    return addend + 3
}

上述 plusThree 能够对 Int 类型进行 +3 操作，但似乎无法对包装类 Result 进行同样的操作。那么如何解决这个问题呢？函子（Functor）就是用于解决该场景下的问题。

函子能够将普通函数应用到一个包装类型。

Swift 中，默认实现了 map 方法（在 Haskell 中是 fmap）的类型就是函子，即 map 方法能够将普通函数应用到一个包装类型。如：

Result.success(2).map(plusThree)
// => .success(5)

// 使用尾随闭包语法
Result.success(2).map { $0 + 3 }
// => .success(5)

我们以 Result 类型为例，通过实现 map 方法，使其成为函子。如下所示：

extension Result {
    // 满足 Functor 的条件：map 方法能够将 普通函数 应用到包装类
    func map<U>(_ f: (T) -> U) -> Result<U> {
        switch self {
        case .success(let x): return .success(f(x))
        case .failure: return .failure
        }
    }
}

map 实现的具体原理是：通过模式匹配将取出包装类中的值，并将普通函数应用到该值上，最终将计算结果再放到包装类中用于返回。其过程如下图所示：

出于简化目的，我们可以为 map 方法定义一个中缀运算符 <^>（在 Haskell 中则是 <$>），具体实现如下所示：

precedencegroup ChaningPrecedence {
    associativity: left
    higherThan: TernaryPrecedence
}
infix operator <^>: ChaningPrecedence
func <^><T, U>(f: (T) -> U, a: Optional<T>) -> Optional<U> {
    return a.map(f)
}

<^> 的使用方法如下所示：

let result1 = plusThree <^> Result.success(10)
// => success(13)

在 Swift 中，内置的 Array 类型就是函子，其默认实现的 map 方法可以将普通方法应用到 Array 类型，最终返回一个 Array 类型。如下所示：

let arrayA = [1, 2, 3, 4, 5]
let arrayB = arrayA.map { $0 + 3 } 
// => [4, 5, 6, 7, 8]

在 RxSwift 中，Observable 类型也是函子，其默认实现的 map 方法可以将普通方法应用到 Observable 类型，最终返回一个 Observale 类型。如下所示：

let observe = Observable<Int>.just(1).map { $0 + 3 }

Applicative

函子能够将普通函数应用到包装类中，那么如何将包装函数应用到包装类中呢？何为包装函数？包装函数可以理解为使用包装类将普通函数进行了封装。如下所示：

// 函数作为值，封装在 Result 类中
let wrappedFunction = Result.success({ $0 + 3 })

那么如何解决这个问题呢？适用函子（Applicative）就是用于解决该场景下的问题。

适用函子能够将包装函数应用到一个包装类型。

Swift 中，默认实现了 apply 方法的类型就是适用函子，即 apply 方法能够将包装函数应用到一个包装类型。

我们以 Result 类型为例，通过实现 apply 方法，使其成为适用函子。如下所示：

extension Result {
    // 满足 Applicative 的条件：apply 方法能够将 包装函数 应用到包装类
    func apply<U>(_ f: Result<(T) -> U>) -> Result<U> {
        switch f {
        case .success(let normalF): return map(normal)
        case .failure: return .failure
        }
    }
}

apply 实现的具体原理是：通过模式匹配分别从包装函数和包装类型中取出普通函数和值，将普通函数应用于值上，再将得到的结果放入包装类型，最终将返回包装类型。其过程如下图所示：

出于简化目的，我们可以为 apply 方法定义一个中缀运算符 <*>，具体实现如下所示：

infix operator <*>: ChainingPrecedence
func <*><T, U>(f: Result<(T) -> U>, a: Result<T>) -> Result<U> {
    return a.apply(f)
}

<*> 的使用方法如下所示：

let wrappedFunction: Result<(Int) -> Int> = .success(plusThree)
let result = wrappedFunction <*> Result.success(10)
// => success(13)

为了方便日常开发，我们可以为 Swift 的常用的 Optional 和 Array 类型实现 apply 方法，从而成为适用函子。如下所示：

extension Optional {
    func apply<U>(_ f: Optional<(Wrapped) -> U>) -> Optional<U> {
        switch f {
        case .some(let someF): return self.map(someF)
        case .none: return .none
        }
    }
}

extension Array {
    func apply<U>(_ fs: [(Element) -> U]) -> [U] {
        var result = [U]()
        for f in fs {
            for element in self.map(f) {
                result.append(element)
            }
        }
        return result
    }
}

Monad

函子可以将普通函数应用到包装类型；使用函子可以将包装函数应用到包装类型；单子（Monad）则可以将会返回包装类型的普通函数应用到包装类型。

适用函子能够回返回包装类型的普通函数应用到一个包装类型。

Swift 中，默认实现了 flatMap 方法（或称为 bind）的类型就是单子，即 flatMap 方法能够会返回包装类型的普通函数应用到一个包装类型。很多人喜欢用 降维 来形容 flatMap 的能力，其实 flatMap 能做的，不止如此。

我们以 Result 类型为例，通过实现 flatMap 方法，使其成为单子。如下所示：

extension Result {
    func flatMap<U>(_ f: (T) -> Result<U>) -> Result<U> {
        switch self {
        case .success(let x): return f(x)
        case .failure: return .failure
    }
}

出于简化目的，我们可以为 flatMap 方法定义一个中缀运算符 >>-（在 Haskell 中则是 >>=），具体实现如下所示：

func <*><T, U>(f: Result<(T) -> U>, a: Result<T>) -> Result<U> {
    return a.apply(f)
}

>>= 的使用方法如下所示：

func multiplyFive(_ a: Int) -> Result<Int> {
    return Result<Int>.success(a * 5)
}

let result = Result.success(10) >>- multiplyFive >>- multiplyFive
// => success(250)

在 RxSwift 中，Observable 类型也是单子，其默认实现的 flatMap 方法可以将会返回 Observable 类型的方法应用到 Observable 类型，最终返回一个 Observale 类型。如下所示：

let observe = Observable.just(1).flatMap { num in
    Observable.just("The number is \(num)")
}

总结

最后，我们总结一下函子、适用函子、单子的定义：

• 函子：可以通过 map 或 <^> 将普通函数应用到包装类型
• 适用函子：可以通过 apply 或 <*> 将包装函数应用到包装类型
• 单子：可以通过 flatMap 或 >>- 将会返回包装类型的普通函数应用到包装类型

通过对函子、适用函子、单子进行组合应用，我们可以最大化地释放出函数式编程的魅力。在 RxSwift 中，同样大量应用了函子、试用函子、单子。在后面的文章中，我们将进一步探索 RxSwift 是如何利用它们来构建一个函数响应式框架的。