在函数范式中构建程序
ifwinds 2019-07-01
什么是函数范式
函数式编程（英语：functional programming）
以λ演算为理论基础的编程范型, 将电脑运算视为数学上的函数计算, 并且避免使用程序状态以及易变对象.
电脑运算视为数学上的函数计算
数学上的函数只要遵守计算准则, 输入和输出是确定的, 是可以被组合、可以被严格推理的
$$f(x)=ax^2+bx+c$$
复杂的函数是由简单的函数组合而成的, 函数范式也是由简单运算一层层组合为复杂执行过程的
但电脑运算最大的障碍是电脑程序是会有副作用的
因此函数范式的核心问题即是如何处理这些副作用
副作用
- 变量
- IO操作(文件读写、网络操作等)
- 线程操作
- 与系统的交互(GUI、硬件交互等)
- 等
强类型
数学中函数是有严格定义域的, 即值的定义范围, 映射到程序中就是类型
换句话说我们定义一个类型实际就是在定义一个值的范围("范围"这个词可能不太准确，可能更类似“枚举”，比如“True”和“False”两个枚举的集合就是Boolean类型)
电脑运算视为数学上的函数计算另一个过程即是定义域的转换, 如果数学函数需要严格的定义域, 程序中需要严格的类型限定也是很自然的事情
fun plusOne(a: Int): Int
| 函数名 | 定义域 | 值域 |
|---|---|---|
| plusOne | a: Int | : Int |
从数据结构开始构建程序
程序 = 数据结构 + 算法OOP实际很多时候将数据结构和算法混杂到了一起, 函数范式则回归本源将两者分离:
函数式程序 = 数据结构 + 算法程序编写开始之前, 首先定义数据结构
函数式数据结构
OOP提倡针对不同问题定义不同的数据结构, 这导致定义的数据结构通常不通用, 比如不同XML解析库会定义不同的专用数据类型
函数范式则不同, 它们用很少一组关键数据结构（如list、set、map）来搭配专为这些数据结构深度优化过的操作。
在这些关键数据结构和操作构成的一套运转机构上，按需要插入另外的数据结构和高阶函数来调整以适应具体问题。
Example
创造值域:
sealed class ItemData data class ItemListData(...) : ItemData() data class ItemOptionData(...) : ItemData()
List<ItemData>
typealias Selecable<T> = Pair<T, Boolean> List<Selecable<ItemData>>
不可变数据类型
定义代数数据类型的一个基本限制是其中不能有变元, 这就是代数的的含义
所以我们在函数范式中只能定义不可变数据
从另一方面来解释这种限制:变量的存在往往是程序Bug的最终来源, 它的值依赖于运行时(线程切换状态、用户操作顺序、系统状态等等), 无法在测试期完全限制掉, 墨菲定律
函数式数据结构中的数据共享
当我们对一个已存在的列表xs在前面添加一个元素1的时候，返回一个新的列表，即Cons(1, xs),既然列表是不可变的，我们不需要去复制一份xs，可以直接复用它，这称为数据共享。
共享不可变数据可以让函数实现更高的效率。我们可以返回不可变数据结构而不用担心后续代码修改它，不需要悲观地复制一份以避免对其修改或污染。
所有关于更高效支持不同操作方式的纯函数式数据结构，其实都是找到一种聪明的方式来利用数据共享。
正因如此，在大型程序里，函数式编程往往能取得比依赖副作用更好的性能。
用组合代替继承
OOP中算法和数据结构是混合在一起放在叫做类的东西里, 因此对算法(通常算法需要操作数据结构)的扩展需要通过继承的方式来实现, 这种处理方式有两个问题:
- 多继承问题、难以组合
- 难以额外扩展
- 方法可以被复写意味着方法是
可变的
回溯上文, 我们说函数式程序 = 数据结构 + 算法, 数据结构被单独定义后, 算法就被独立出来了, 因此函数范式采用了更加灵活的方式组合这些算法
类型类
这些被分离出来的算法不同于OOP中的类, 所以函数范式中将之称之为类型类(typeclass)
private内聚一些内部方法以防止内部变量被非法操作后数据变得不符合预期因此函数范式中方法默认是
public的Example
interface Eq<in F> {
fun F.eqv(b: F): Boolean
}interface Show<in A> {
fun A.show(): String
}interface ShowEq<in A> : Eq<A>, Show<A> {
override fun A.show(): String = this.toString()
}interface CharEqInstance : Eq<Char> {
override fun Char.eqv(b: Char): Boolean = this == b
}
fun Char.Companion.eq(): Eq<Char> =
object : CharEqInstance {}QuickCheck
我们定义一个方法(函数)实际上就是在定义一个数学上的函数, 因此它应该是可以被严格验证的, 即指定定义域上值应该都能被映射到指定的值域
测试在数学意义上就是做这个验证的, 输入所有定义域上的可能值验证是否正确映射到了值域
传统的测试实际并没有覆盖全定义域, 因此可能导致某些额外情况. 函数范式中常用的测试框架QuickCheck即是尝试做全覆盖测试
这也是为什么提倡对函数参数进行强类型化, 没有足够的类型限制实际就是扩展了函数的定义域, 这一般有两种情况:
- 假定了输入数据的子域(比如参数是
String, 却假定格式为1.1.2) - 包含了实际自己处理不了的数据(比如不能处理空数据, 却标明可以为空)
甚至函数对象也是可以被生成的
Example
object EqLaws {
inline fun <F> laws(EQ: Eq<F>, noinline cf: (Int) -> F): List<Law> =
listOf(
Law("Eq Laws: identity") { EQ.identityEquality(cf) },
Law("Eq Laws: commutativity") { EQ.commutativeEquality(cf) }
)
fun <F> Eq<F>.identityEquality(cf: (Int) -> F): Unit =
forAll(Gen.int()) { int: Int ->
val a = cf(int)
a.eqv(a) == a.eqv(a)
}
fun <F> Eq<F>.commutativeEquality(cf: (Int) -> F): Unit =
forAll(Gen.int()) { int: Int ->
val a = cf(int)
val b = cf(int)
a.eqv(b) == b.eqv(a)
}
}副作用的分离
副作用在程序中是确实存在的, 问题是如何将之分离出去, 函数范式的处理方式可以看做建造一个管道, 管道本身是代数的、确定的, 而其中流淌的就是副作用
这些管道常见的有:IO、Single、Maybe等
对于必须存在的变量的处理方法就是, 将之放到安全的地方, 一般而言即线程安全
IO
IO不同于我们通常意义上的input/output操作的意思, 它是Haskell中用来抽象外部作用的特殊数据结构, 它隐含了一个叫RealWorld的上下文用于和外部环境进行交互(即副作用), 所有的副作用必须包含在其中
Example
Haskell:
putStrLn :: String -> IO ()
getLine :: IO String
main = do
name <- getLine
putStrLn ("Hey, " ++ name)Kotlin:
fun putStrLn(s: String): IO<Unit> fun getLine(): IO<String>
IO.monad().binding {
val s = readString().bind()
putStrLn(s).bind()
}Rx:
fun putStrLn(s: String): Completable fun getLine(): Single<String>
fun main() = getLine()
.flatMapCompletable { s -> putStrLn(s) }main().blockingAwait()
