函数式编程 - 有趣的Monoid（单位半群）

Monoid （中文： 单位半群 ，又名： 幺半群 ），一个来源于数学的概念；得益于它的抽象特性， Monoid 在函数式编程中起着较为重大的作用。

本篇文章将会以工程的角度去介绍 Monoid 的相关概念，并结合几个有趣的数据结构（如 Middleware 、 Writer ）来展现 Monoid 自身强大的能力及其实用性。

Semigroup（半群）

在开始 Monoid 的表演之前，我们首先来感受一下 Semigroup（半群） ，它在维基百科上的定义 为：

集合S和其上的二元运算·:S×S→S。若·满足结合律，即：∀x,y,z∈S，有(x·y)·z=x·(y·z)，则称有序对(S,·)为半群，运算·称为该半群的乘法。实际使用中，在上下文明确的情况下，可以简略叙述为“半群S”。

上面的数学概念比较抽象，理解起来可能比较麻烦。下面结合一个简单的例子来通俗说明：

对于自然数 1、2、3、4、5、... 而言，加法运算 + 可将两个自然数相加，得到的结果仍然是一个自然数，并且加法是满足结合律的：(2 + 3) + 4 = 2 + (3 + 4) = 9。如此一来我们就可以认为自然数和加法运算组成了一个半群。类似的还有自然数与乘法运算等。

通过以上的例子，半群的概念非常容易就能理解，下面我通过 Swift 语言的代码来对 Semigroup 进行实现：

// MARK: - Semigroup

infix operator <> : AdditionPrecedence

protocol Semigroup {
    static func <> (lhs: Self, rhs: Self) -> Self
}
复制代码

协议 Semigroup 中声明了一个运算方法，该方法的两个参数与返回值都是同一个实现了半群的类型。我们通常将这个运算称为 append 。

以下为 String 和 Array 类型实现 Semigroup ，并进行简单的使用：

extension String: Semigroup {
    static func <> (lhs: String, rhs: String) -> String {
        return lhs + rhs
    }
}

extension Array: Semigroup {
    static func <> (lhs: [Element], rhs: [Element]) -> [Element] {
        return lhs + rhs
    }
}

func test() {
    let hello = "Hello "
    let world = "world"
    let helloWorld = hello <> world
    
    let one = [1,2,3]
    let two = [4,5,6,7]
    let three = one <> two
}
复制代码

Monoid（单位半群）

定义

Monoid 本身也是一个 Semigroup ，额外的地方是它多了 单位元 ，所以被称作为 单位半群 。 单位元 在维基百科上的定义 为：

在半群S的集合S上存在一元素e，使得任意与集合S中的元素a都符合 a·e = e·a = a

举个例子，在上面介绍 Semigroup 的时候提到，自然数跟加法运算组成了一个半群。显而易见的是，自然数 0 跟其他任意自然数相加，结果都是等于原来的数： 0 + x = x 。所以我们可以把 0 作为单位元，加入到由自然数和加法运算组成的半群中，从而得到了一个单位半群。

下面就是 Monoid 在Swift中的定义：

protocol Monoid: Semigroup {
    static var empty: Self { get }
}
复制代码

可以看到， Monoid 协议继承自 Semigroup ，并且用 empty 静态属性来代表 单位元 。

我们再为 String 和 Array 类型实现 Monoid ，并简单演示其使用：

extension String: Monoid {
    static var empty: String { return "" }
}

extension Array: Monoid {
    static var empty: [Element] { return [] }
}

func test() {
let str = "Hello world" <> String.empty // Always "Hello world"
let arr = [1,2,3] <> [Int].empty // Always [1,2,3]
}
复制代码

组合

对于有多个 Monoid 的连续运算，我们现在写出来的代码是：

let result = a <> b <> c <> d <> e <> ...
复制代码

若 Monoid 的数量居多，又或者它们是被包裹在一个数组或Sequence中，我们就很难像上面那样一直在写链式运算，不然代码会变得复杂难堪。此时可以基于 Sequence 的 reduce 方法来定义我们的 Monoid 串联运算 concat ：

extension Sequence where Element: Monoid {
    func concat() -> Element {
        return reduce(Element.empty, <>)
    }
}
复制代码

如此一来我们就可以很方便地为位于数组或Sequence中的若干个 Monoid 进行串联运算：

let result = [a, b, c, d, e, ...].concat()
复制代码

条件

在开始讨论 Monoid 的条件性质前，我们先引入一个十分简单的数据结构，其主要是用于处理计划中即将执行的某些任务，我把它命名为 Todo ：

struct Todo {
    private let _doIt: () -> ()
    init(_ doIt: @escaping () -> ()) {
        _doIt = doIt
    }
    func doIt() { _doIt() }
}
复制代码

它的使用很简单：我们先通过一个即将要处理的操作来构建一个 Todo 实例，然后在适当的时机调用 doIt 方法即可：

func test() {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")
    }

    // Wait a second...

    sayHello.doIt()
}
复制代码

这里还未能体现到它的强大，接下来我们就为它实现 Monoid ：

extension Todo: Monoid {
    static func <> (lhs: Todo, rhs: Todo) -> Todo {
        return .init {
            lhs.doIt()
            rhs.doIt()
        }
    }

    static var empty: Todo {
        // Do nothing
        return .init { }
    }
}
复制代码

在 append 运算中我们返回了一个新的 Todo ，它需要做的事情就是先后完成左右两边传入的 Todo 参数各自的任务。另外，我们把一个什么都不做的 Todo 设为单位元，这样就能满足 Monoid 的定义。

现在，我们就可以把多个 Todo 串联起来，下面就来把玩一下：

func test() {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")
    }

    let likeSwift = Todo {
        print("I like Swift.")
    }

    let likeRust = Todo {
        print("And also Rust.")
    }

    let todo = sayHello <> likeSwift <> likeRust

    todo.doIt()
}
复制代码

有时候，任务是按照某些特定条件来判断是否被执行，比如像上面的 test 函数中，我们需要根据特定的条件来判断是否要执行三个 Todo ，重新定义函数签名：

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool)

为了能够实现这种要求，通常来说有以下两种较为蛋疼的做法：

// One
func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")
    }

    let likeSwift = Todo {
        print("I like Swift.")
    }

    let likeRust = Todo {
        print("And also Rust.")
    }

    var todo = Todo.empty
    if shouldSayHello {
        todo = todo <> sayHello
    }
    if shouldLikeSwift {
        todo = todo <> likeSwift
    }
    if shouldLikeRust {
        todo = todo <> likeRust
    }

    todo.doIt()
}

// Two
func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")
    }

    let likeSwift = Todo {
        print("I like Swift.")
    }

    let likeRust = Todo {
        print("And also Rust.")
    }

    var arr: [Todo] = []
    if shouldSayHello {
        arr.append(sayHello)
    }
    if shouldLikeSwift {
        arr.append(likeSwift)
    }
    if shouldLikeRust {
        arr.append(likeRust)
    }
    arr.concat().doIt()
}
复制代码

这两种写法都略为复杂，并且还引入了变量，代码一点都不优雅。

这时，我们就可以为 Monoid 引入条件判断：

extension Monoid {
    func when(_ flag: Bool) -> Self {
        return flag ? self : Self.empty
    }

    func unless(_ flag: Bool) -> Self {
        return when(!flag)
    }
}
复制代码

在 when 方法中，如果传入的布尔值为 true ，那么此方法将会原封不动地把自己返回，而如果传入了 false ，函数则返回一个单位元，相当于丢弃掉 现在的自己 （因为单位元跟任意元素进行 append 运算结果都是元素本身）。 unless 方法则只是简单地互换一下 when 参数中的布尔值。

现在，我们就能优化一下刚刚 test 函数的代码：

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")
    }

    let likeSwift = Todo {
        print("I like Swift.")
    }

    let likeRust = Todo {
        print("And also Rust.")
    }

    let todo = sayHello.when(shouldSayHello) <> likeSwift.when(shouldLikeSwift) <> likeRust.when(shouldLikeRust)
    todo.doIt()
}
复制代码

比起之前的两种写法，这里优雅了不少。

一些实用的Monoid

接下来我将介绍几个实用的 Monoid ，它们能用在日常的项目开发上，让你的代码可读性更加简洁清晰，可维护性也变得更强（最重要是优雅）。

Middleware（中间件）

Middleware 结构非常类似于刚刚在文章上面提到的 Todo :

struct Middleware<T> {
    private let _todo: (T) -> ()
    init(_ todo: @escaping (T) -> ()) {
        _todo = todo
    }
    func doIt(_ value: T) {
        _todo(value)
    }
}

extension Middleware: Monoid {
    static func <> (lhs: Middleware, rhs: Middleware) -> Middleware {
        return .init {
            lhs.doIt($0)
            rhs.doIt($0)
        }
    }

    // Do nothing
    static var empty: Middleware { return .init { _ in } }
}
复制代码

比起 Todo ， Middleware 在 todo 闭包上设置了一个参数，参数的类型为 Middleware 中定义了的泛型。

Middleware 的作用就是让某个值通过一连串的中间件，这些中间件所做的事情各不相同，它们可能会对值进行加工，或者完成一些副作用（打Log、数据库操作、网络操作等等）。 Monoid 的 append 操作将每个中间件组合在一起，形成一个统一的入口，最终我们只需将值传入这个入口即可。

接下来就是一个简单使用到 Middleware 的例子，假设我们现在需要做一个对富文本 NSAttributedString 进行装饰的解析器，在里面我们可以根据需要来为富文本提供特定的装饰（修改字体、前景或背景颜色等），我们可以这样定义：

// MARK: - Parser
typealias ParserItem = Middleware<NSMutableAttributedString>

func font(size: CGFloat) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.font: UIFont.systemFont(ofSize: size)], range: .init(location: 0, length: str.length))
    }
}

func backgroundColor(_ color: UIColor) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.backgroundColor: color], range: .init(location: 0, length: str.length))
    }
}

func foregroundColor(_ color: UIColor) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.foregroundColor: color], range: .init(location: 0, length: str.length))
    }
}

func standard(withHighlighted: Bool = false) -> ParserItem {
    return font(size: 16) <> foregroundColor(.black) <> backgroundColor(.yellow).when(withHighlighted)
}

func title() -> ParserItem {
    return font(size: 20) <> foregroundColor(.red)
}

extension NSAttributedString {
    func parse(with item: ParserItem) -> NSAttributedString {
        let mutableStr = mutableCopy() as! NSMutableAttributedString
        item.doIt(mutableStr)
        return mutableStr.copy() as! NSAttributedString
    }
}

func parse() {
    let titleStr = NSAttributedString(string: "Monoid").parse(with: title())
    let text = NSAttributedString(string: "I love Monoid!").parse(with: standard(withHighlighted: true))
}
复制代码

如上代码，我们首先定义了三个最基本的中间件，分别可用来为 NSAttributedString 装饰字体、背景颜色和前景颜色。 standard 和 title 则将基本的中间件进行组合，这两个组合体用于特定的情境下（为作为标题和作为正文的富文本装饰），最终文字的解析则通过调用指定中间件来完成。

通过以上的例子我们可以认识到： Todo 和 Middleware 都是一种对行为的抽象，它们之间的区别在于 Todo 在行为的处理中并不接收外界的数据，而 Middleware 可从外界获取某种对行为的输入。

Order

试想一下我们平时的开发中会经常遇到以下这种问题：

if 满足条件1 {
    执行优先级最高的操作...
} else if 满足条件2 {
    执行优先级第二的操作
} else if 满足条件3 {
    执行优先级第三的操作
} else if 满足条件4 {
    执行优先级第四的操作
} else if ...
复制代码

这里可能存在一个问题，那就是优先级的情况。假设某一天程序要求修改将某个分支操作的优先级，如将优先级第三的操作提升到最高，那此时我们不得不改动大部分的代码来完成这个要求：比方说将两个或多个 if 分支代码的位置互换，这样改起来那就很蛋疼了。

Order 就是用于解决这种与条件判断相关的优先级问题：

// MARK: - Order
struct Order {
    private let _todo: () -> Bool
    init(_ todo: @escaping () -> Bool) {
        _todo = todo
    }
    
    static func when(_ flag: Bool, todo: @escaping () -> ()) -> Order {
        return .init {
            flag ? todo() : ()
            return flag
        }
    }
    
    @discardableResult
    func doIt() -> Bool {
        return _todo()
    }
}

extension Order: Monoid {
    static func <> (lhs: Order, rhs: Order) -> Order {
        return .init {
            lhs.doIt() || rhs.doIt()
        }
    }

    // Just return false
    static var empty: Order { return .init { false } }
}
复制代码

在构建 Order 的时候，我们需要传入一个闭包，在闭包中我们将处理相关的逻辑，并返回一个布尔值，若此布尔值为 true ，则代表此Order的工作已经完成，那么之后优先级比它低的Order将不做任何事情，若返回 false ，代表在这个Order里面我们并没有做好某个操作（或者说某个操作不符合执行的要求），那么接下来优先级比它低的Order将会尝试去执行自身的操作，然后按照这个逻辑一直下去。

Order的优先级是通过它们排列的顺序决定的，比方说 let result = orderA <> orderB <> orderC ，那么优先级就是 orderA > orderB > orderC ，因为我们在定义 append 的时候使用到了短路运算符 || 。

静态方法 when 能够更加简便地通过一个布尔值和一个无返回值闭包来构建Order，日常开发可自行选择使用Order本身的构造函数还是 when 方法。

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Order.when(shouldSayHello) {
        print("Hello, I'm Tangent!")
    }
    
    let likeSwift = Order.when(shouldLikeSwift) {
        print("I like Swift.")
    }
    
    let likeRust = Order.when(shouldLikeRust) {
        print("And also Rust.")
    }
    
    let todo = sayHello <> likeSwift <> likeRust
    todo.doIt()
}
复制代码

如上面例子中，三个 Order 的操作要么全部都不会执行，要么就只有一个被执行，这取决于 when 方法传入的布尔值，执行的优先级按照 append 运算的先后顺序。

Array

文章已在之前为 Array 实现了 Monoid ，那么 Array 在日常的开发中如何可以利用 Monoid 的特性呢，我们来看下面的这个代码：

class ViewController: UIViewController {
    func setupNavigationItem(showAddBtn: Bool, showDoneBtn: Bool, showEditBtn: Bool) {
        var items: [UIBarButtonItem] = []
        if showAddBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .add, target: self, action: #selector(add)))
        }
        if showDoneBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .done, target: self, action: #selector(done)))
        }
        if showEditBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .edit, target: self, action: #selector(edit)))
        }
        navigationItem.rightBarButtonItems = items
    }
    
    @objc func add() { }
    @objc func done() { }
    @objc func edit() { }
}
复制代码

就像在之前讲 Todo 那样，这样的代码写法的确不优雅，为了给ViewController设置rightBarButtonItems，我们首先得声明一个数组变量，然后再根据每个条件去给数组添加元素。这样的代码是没有美感的！

我们通过使用 Array 的 Monoid 特性来重构一下上面的代码：

class ViewController: UIViewController {
    func setupNavigationItem(showAddBtn: Bool, showDoneBtn: Bool, showEditBtn: Bool) {
        let items = [UIBarButtonItem(barButtonSystemItem: .add, target: self, action: #selector(add))].when(showAddBtn)
            <> [UIBarButtonItem(barButtonSystemItem: .done, target: self, action: #selector(done))].when(showDoneBtn)
            <> [UIBarButtonItem(barButtonSystemItem: .edit, target: self, action: #selector(edit))].when(showEditBtn)
        navigationItem.rightBarButtonItems = items
    }
    
    @objc func add() { }
    @objc func done() { }
    @objc func edit() { }
}
复制代码

这下子就优雅多了~

Writer Monad

Writer Monad 是一个基于 Monoid 的 Monad（单子） ，旨在执行操作的过程中去顺带记录特定的信息，如Log或者历史记录。若你不了解 Monad 没有关系，这里不会过多提及与它的相关，在阅读代码时你只需要搞清楚其中的实现原理即可。

// MARK: - Writer
struct Writer<T, W: Monoid> {
    let value: T
    let record: W
}

// Monad
extension Writer {
    static func `return`(_ value: T) -> Writer {
        return Writer(value: value, record: W.empty)
    }
    
    func bind<O>(_ tran: (T) -> Writer<O, W>) -> Writer<O, W> {
        let newOne = tran(value)
        return Writer<O, W>(value: newOne.value, record: record <> newOne.record)
    }
    
    func map<O>(_ tran: (T) -> O) -> Writer<O, W> {
        return bind { Writer<O, W>.return(tran($0)) }
    }
}

// Use it
typealias LogWriter<T> = Writer<T, String>
typealias Operation<T> = (T) -> LogWriter<T>

func add(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 + num, record: "\($0)加\(num), ") }
}
func subtract(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 - num, record: "\($0)减\(num), ") }
}
func multiply(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 * num, record: "\($0)乘\(num), ") }
}
func divide(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 / num, record: "\($0)除\(num), ") }
}

func test() {
    let original = LogWriter.return(2)
    let result = original.bind(multiply(3)).bind(add(2)).bind(divide(4)).bind(subtract(1))
    // 1
    print(result.value)
    // 2乘3, 6加2, 8除4, 2减1,
    print(result.record)
}
复制代码

Writer 为结构体，其中包含着两个数据，一个是参与运算的值，类型为泛型T，一个是运算时所记录的信息，类型为泛型W，并且需要实现 Monoid 。

return 静态方法能够创建一个新的 Writer ，它需要传入一个值，这个值将直接保存在 Writer 中。得益于 Monoid 单位元的特性， return 在构建 Writer 的过程中直接将 empty 设置为 Writer 所记录的信息。

bind 方法所要做的就是通过传入一个能将运算值转化成 Writer 的闭包来对原始 Writer 进行转化，在转化的过程中 bind 将记录信息进行 append ，这样就能帮助我们自动进行信息记录。

map 方法通过传入一个运算值的映射闭包，将 Writer 内部的运算值进行转换。

其中， map 运算来源于函数式编程概念 Functor ， return 和 bind 则来源于 Monad 。大家如果对此有兴趣的可以查阅相关的内容，或者阅读我在之前写的有关于这些概念的文章。

利用 Writer Monad ，我们就可以专心于编写代码的业务逻辑，而不必花时间在一些信息的记录上， Writer 会自动帮你去记录。

尾

这篇文章没有提及到的 Monoid 还有很多，如 Any 、 All 、 Ordering ...，大家可以通过查阅相关文档来进行。

对于 Monoid 来说，重要的不是在于去了解它相关的实现例子，而是要深刻地理解它的抽象概念，这样我们才能说认识 Monoid ，才能举一反三，去定义属于自己的 Monoid 实例。

事实上 Monoid 的概念并不复杂，然而函数式编程的哲学就是这样，希望通过一个个细微的抽象，将它们组合在一起，最终成就了一个更为庞大的抽象，构建出了一个极其优雅的系统。