[TOC] ### 组合与范畴 **函数式编程的本质是函数的组合，组合的本质是范畴（Category）**。 和搞编程的一样，数学家喜欢将问题不断加以抽象从而将本质问题抽取出来加以论证解决，范畴论就是这样一门以抽象的方法来处理数学概念的学科，主要用于研究一些数学结构之间的映射关系（函数）。 在范畴论里，一个范畴(category)由三部分组成： * 对象(object). * 态射(morphism). * 组合(composition)操作符， #### 范畴的对象 这里的对象可以看成是一类东西，例如数学上的群，环，以及有理数，无理数等都可以归为一个对象。**对应到编程语言里，可以理解为一个类型，比如说整型，布尔型等**。 #### [态射](https://github.com/EasyKotlin/chapter8_fp#态射) **态射指的是一种映射关系，简单理解，态射的作用就是把一个对象 A 里的值 a 映射为 另一个对象 B 里的值 b = f(a)，这就是映射的概念**。 态射的存在反映了对象内部的结构，这是范畴论用来研究对象的主要手法：对象内部的结构特性是通过与别的对象的映射关系反映出来的，动静是相对的，**范畴论通过研究映射关系来达到探知对象的内部结构的目的。** #### [组合操作符](https://github.com/EasyKotlin/chapter8_fp#组合操作符) **组合操作符，用点(.)表示，用于将态射进行组合**。**组合操作符的作用是将两个态射进行组合**，例如，假设存在态射` f: A -> B, g: B -> C`， 则 `g.f : A -> C.` **一个结构要想成为一个范畴, 除了必须包含上述三样东西，它还要满足以下三个限制**: * **结合律**： `f.(g.h) = (f.g).h` 。 * **封闭律**：如果存在态射 f, g，则必然存在` h = f.g` 。 * **同一律**：对结构中的每一个对象 A， 必须存在一个单位态射 Ia: A -> A， 对于单位态射，显然，对任意其它态射 f, 有` f.I = f`。 在范畴论里另外研究的重点是**范畴与范畴之间的关系**，就正如对象与对象之间有态射一样，**范畴与范畴之间也存在映射关系，从而可以将一个范畴映射为另一个范畴，这种映射在范畴论中叫作函子(functor）**，具体来说，对于给定的两个范畴 A 和 B，函子的作用有两个: * 将范畴 A 中的对象映射到范畴 B 中的对象。 * 将范畴 A 中的态射映射到范畴 B 中的态射。 显然，**函子反映了不同的范畴之间的内在联系。跟函数和泛函数的思想是相同的**。 而我们的函数式编程探究的问题与思想理念可以说是跟范畴论完全吻合。**如果把函数式编程的整个的世界看做一个对象，那么FP真正搞的事情就是建立通过函数之间的映射关系，来构建这样一个美丽的编程世界。** 很多问题的解决（证明）其实都不涉及具体的（数据）结构，而完全可以只依赖映射之间的组合运算(composition)来搞定。这就是函数式编程的核心思想。 如果我们把`程序`看做图论里面的一张图G，`数据结构`当作是图G的节点Node（数据结构，存储状态）， 而`算法`逻辑就是这些节点Node之间的Edge (数据映射，Mapping)， 那么这整幅图`G(N,E)`就是一幅美妙的抽象逻辑之塔的`映射图`， 也就是我们编程创造的世界：  #### 函数是"第一等公民" 函数式编程（FP）中，函数是"第一等公民"。 所谓"第一等公民"（first class），有时称为 闭包或者 仿函数（functor）对象， 指的是**函数与其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。这个以函数为参数的概念，跟C语言中的函数指针类似。** 举例来说，下面代码中的print变量就是一个函数（没有函数名），可以作为另一个函数的参数: ~~~ val print = fun(x:Any){println(x)} listOf(1,2,3).forEach(print) ~~~ #### 高阶函数（Higher order Function） **FP 语言支持高阶函数，高阶函数就是多阶映射。高阶函数用另一个函数作为其输入参数，也可以返回一个函数作为输出。** 代码示例： ~~~ fun isOdd(x: Int) = x % 2 != 0 fun length(s: String) = s.length fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C { return { x -> f(g(x)) } } ~~~ 测试代码： ~~~ fun main(args: Array<String>) { val oddLength = compose(::isOdd, ::length) val strings = listOf("a", "ab", "abc") println(strings.filter(oddLength)) // [a, abc] } ~~~ 输出结果 ``` [a, abc] Process finished with exit code 0 ``` 这个compose函数，其实就是数学中的复合函数的概念，这是一个高阶函数的例子：传入的两个参数f , g都是函数，其返回值也是函数。 图示如下：  即下面的关系 ``` B=g(A)，C=f(B) C=f(B)=f(g(A)) ``` 这里的 ~~~ fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C ~~~ 中类型参数对应： ~~~ fun <String, Int, Boolean> compose(f: (Int) -> Boolean, g: (String) -> Int): (String) -> Boolean ~~~ 这里的`(Int) -> Boolean`、`(String) -> Int`、`(String) -> Boolean`都是函数类型。 其实，**从映射的角度看，就是二阶映射。对[a, ab, abc] 中每个元素 x 先映射成长度g(x) = 1, 2, 3 ， 再进行第二次映射：f(g(x)) %2 != 0 , 长度是奇数？返回值是true的被过滤出来**。 有了高阶函数，我们可以用优雅的方式进行模块化编程。 另外，高阶函数满足结合律：  #### 闭包（Closure） 闭包简单讲就是一个代码块，用`{ }`包起来。此时，程序代码也就成了数据，可以被一个变量所引用（与C语言的函数指针比较类似）。**闭包的最典型的应用是实现回调函数（callback）**。 闭包包含以下两个组成部分： * 要执行的代码块（由于自由变量被包含在代码块中，这些自由变量以及它们引用的对象没有被释放） * 自由变量的作用域 在PHP、Scala、Scheme、Common Lisp、Smalltalk、Groovy、JavaScript、Ruby、 Python、Go、Lua、objective c、swift 以及Java（Java8及以上）等语言中都能找到对闭包不同程度的支持。 **Lambda表达式可以表示闭包**。 #### [惰性计算](https://github.com/EasyKotlin/chapter8_fp#惰性计算) 除了高阶函数、闭包、Lambda表达式的概念，**FP 还引入了惰性计算的概念**。惰性计算（尽可能延迟表达式求值）是许多函数式编程语言的特性。 惰性集合**在需要时提供其元素，无需预先计算它们**，这带来了一些好处。 * 首先，您可以将耗时的计算推迟到绝对需要的时候。 * 其次，您可以创造无限个集合，只要它们继续收到请求，就会继续提供元素。 * 第三，map 和 filter 等函数的惰性使用让您能够得到更高效的代码（请参阅 参考资料 中的链接，加入由 Brian Goetz 组织的相关讨论）。 在惰性计算中，表达式不是在绑定到变量时立即计算，而是在求值程序需要产生表达式的值时进行计算。 一个惰性计算的例子是生成无穷 Fibonacci 列表的函数，但是对 第 n 个Fibonacci 数的计算相当于只是从可能的无穷列表中提取一项。 #### [递归函数](https://github.com/EasyKotlin/chapter8_fp#递归函数) 递归指的是一个函数在其定义中直接或间接调用自身的一种方法，它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决（复用函数自身）, 这样可以极大的减少代码量。递归分为两个阶段: 1、递推：把复杂的问题的求解推到比原问题简单一些的问题的求解; 2、回归：当获得最简单的情况后，逐步返回，依次得到复杂的解。 递归的能力在于用有限的语句来定义对象的无限集合。 使用递归要注意的有两点: （1）递归就是在过程或函数里面调用自身; （2）在使用递归时，必须有一个明确的递归结束条件，称为递归出口。 **PS**：除此之外·，FP还有λ演算、函数柯里化（Currying）、Y组合子(Y - Combinator)、没有"副作用"、引用透明性等特点，详情，可参考极简教程[第八章第一节8.1.3组合与范畴](https://github.com/EasyKotlin/chapter8_fp#813-组合与范畴)