函数式编程——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 中则是 <gt; ），具体实现如下所示：

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 是如何利用它们来构建一个函数响应式框架的。

参考

1. Haskell
2. Scheme )
3. Functors, Applicatives, And Monads In Pictures
4. Three Useful Monads
5. Swift Functors, Applicative, and Monads in Pictures
6. 什么是 Monad (Functional Programming)？函子到底是什么?ApplicativeMonad
7. 函数式语言的宗教
8. Functional Programming Design Patterns
9. Railway Oriented Programming
10. 函数式编程 - 一篇文章概述Functor(函子)、Monad(单子)、Applicative)
11. Improved operator declarations