何为函数式编程(FP, 即Functional Programming) ?

同系列传送门: haskell-basic

本节我们将介绍下函数式编程, 尽量不涉及代码, 都是概念上的东西
那么, 开始吧!

编程范式

概览

FP, 是一种名叫函数式的, 强大的编程范式, 因此, 我想先讲一讲什么是编程范式

编程范式是一种思考方式, 技术, 语言范式, 编程模型
在世界上, 有许多编程范式, 最主要的有:

编程范式实在太多, 但不用刻意去记忆, 这些都是些顾名思义的东西
记住FP与OOP这两个缩写即可, 这两个是最常被提及的, 其他的无需记忆

编程范式, 它就像是国家的意识形态一样, 具有指导意义, 对如何编程求解问题的思考方法有巨大影响
下面是一些编程范式的例子:

提示 如果你已经了解过以下范式, 直接跳到 总结 吧

• 面向过程:
  优点:
  解决问题时, 强调过程, 与人本身的思考方式一致, 符合直觉
  缺点:
  代码复用能力差, 扩展性差, 繁琐
  

• 面向对象:
  优点:
  将问题抽象为一个个对象, 通过建立模型, 使用继承/多态等来描述世界, 复用代码的能力强悍
  缺点:
  不能适用于所有问题, 硬套范式可能会让代码变得更加繁琐
  

• 逻辑式: 优点:
  通过建立 事实, 告诉编程器这些都是绝对正确的, 随后根据逻辑关系直接求解, 十分神奇
  缺点: 玄学编程, 可能想象不到怎么样建立出 能正确求解的前提条件/定义, 也可能因推理过于复杂, 导致性能低下
  

• 函数式: 优点: 通过以数学中的 函数 为指导, 强调结果, 不关注过程, 通过数据不可变极大减少复杂性
  缺点:
  学习难度较大, 性能因不可变数据, 不可避免地会低下一些
  

• 命令式:
  有些说法是命令式指类似汇编这种的, 还有的说命令式与面向过程叫法不同而已
  我其实也不是太能区分这两者, 大家在大多数情况下直接认为两者约等于即可
  毕竟都2022年了, 现在不太需要关注这些低级层面的差异了
  现在该关注的, 是更大差异的范式们, 比如面向过程与面向对象, 函数式与面向对象等等
  

• 声明式:
  指你编程依靠描述, 而非面向过程地去思考
  这种范式常见于一些DSL(领域特定语言), 以此简化在某领域下的开发
  DSL, 即为专门领域创造的语法, 是为了专注于该领域的开发, 比如HTML写网页, SQL写数据库
  特点是一旦脱离相关领域, 语法就不再便利
  

总结

各种编程范式有各自的特点, 人们通过研究它们, 探究高效的编程方式
编程范式并非严格的互相独立的, 它们大多在概念上也存在交集

比如:

• 面向过程/面向对象 && 命令式
• 函数式/逻辑式 && 声明式
• 混合一种, 两种, 甚至各种范式

再比如, 现代的编程语言, 一般都汲取了函数式编程中的思想
比如匿名函数, 高阶函数等在函数式语言中较低级的概念, 被一些面向对象的语言使用后, 也能爆发出不俗的威力
再比如 Rust 中的 Option/Result, 有着 Haskell 的影子

相信经过本小节, 你对什么是编程范式有了一个初步的认知
接下来, 我们就要专注于本节的主角, 函数式

简单来说, 函数式编程依靠着数学的威力, 将其引入编程的概念之中
让我们开始对函数式的正式介绍吧!

高阶函数

高阶函数(HOF, Higher-order Functions), 指一个作为参数, 或当作返回值的函数

你可能经常会听到这么一句话: 在 XXX 语言中, 函数被视为一等公民
函数被视为一等公民, 指函数地位突出, 不会被限制, 通常与那些不支持HOF的编程语言做比较
比如匿名函数, Lambda表达式, 闭包, 其实都是因为HOF(函数可以被当作参数传递)
(话说2022年了, 主流语言或多或少都支持HOF了, 连C语言都能模拟出来呢)

一句话概括: 函数能被轻松随意地传递, 很自由, 就像一等公民

不可变数据

不可变数据(Immutable Data), 指你无法修改已经存在的数据

换句话说, 当你想进行新运算, 得到新数据时, 不是替换进原有的数据, 而是新开辟一块空间来存放它
被创建的值, 你将永远无法修改, 就如同数学里那样, 相信我, 当你第一次学编程时, 总会对 变量 感到困惑

这也意味着, 你不再需要关注一些与计算机底层有关的奇技淫巧, 而是专注于问题本身
但有个道理亘古不变: 随着抽象等级的提高, 就越偏移底层, 可能会造成更多的资源浪费

而且, 可变性还会影响并发性, 出现一些奇奇怪怪的错误, 得学习各种锁模型或其他同步机制
但不可变的数据能够有效降低并发的难度

而且也别太担心效率, 虽然肯定会低点, 但也没小瞧现代编译器的疯狂优化啊
比如每次计算不一定会产生新值, 而是通过共享内存, 达到重复使用旧值

副作用

副作用(Side Effects), 指与外界发生的交互

假设有这么一个函数:
它接受一个参数作为文件名, 进行读取, 输出内容, 即使这么简单, 也做不到相同的输入, 能得到相同的输出
可能你无权读取文件, 可能文件不存在, 可能文件被修改过, 所以, 输入一个固定路径, 不一定能得到固定的输出

因此, 这种IO操作, 便是种副作用, 因为它涉及到与外界的交互, 可能产生无法预测的事情
这种超脱于语言, 来自更真实世界的交互, 我们称之为 副作用

副作用包括, 但不限于:

• 发送网络请求
• 访问系统状态
• 操作数据库
• 操作DOM
• IO操作
• 修改函数外部的变量
• 使用具有副作用的函数 (传播性)

你会注意到 修改函数外部的变量, 它也可以看作 与外界的交互
比如, 若该函数修改了一个函数外部的值, 并且返回值依靠这个不固定的值
那么这将无法保证相同输入, 能得到相同输出

但是, 程序就是依靠副作用来产生价值的, 副作用让我们能够更改外部条件, 进行交互
绝对的没有副作用, 意味着这个程序绝对的没用

引用透明

引用透明(RT, Referential Transparency), 指某个表达式, 能替换为它计算得到的值, 且替换前后的语义一定等价

引用透明性, 是个存在于众多学说中的知识, 不光是计算机, 还有数学, 哲学, 语言学等
以下是数学中的 RT, 简单来讲, 就是等式推导:

f(x) = (x+1)^2^ f(2) = (2+1)^2^ = (3)^2^ = 9

可以看到, 2+1可以被3代替, 且替换前后的语义一致, 这便是数学中的 RT, 或者称呼它为 等式推导:
某个 父表达式 由许多 子表达式 组成, 如果可以将这些 子表达式 替换为它们计算得到的对应值, 就能简化这个 父表达式
计算机中的 RT, 也差不多是这个意思, 只要某个表达式能被替换, 且语义不变, 就具有 RT

总而言之, 就是替换, 替换, 还是替换
即使效率变化, 只要语义不变就行, 这有利于让推导问题变得容易, 删除大量冗杂的代码, 方便进行重构等

RT 还能与 non-RT(非引用透明) 进行对比, 体现 RT 的好处:
若有这么个函数:

double_x(x: Int): Int {
    println(x);
    return x+x;
}

那么, 它就不具有 RT, 因为它涉及到了 IO操作(打印了x)
此时进行替换的话, 比如 double_x(10) -> 20, 因为后者少了次打印, 语义不一致
假设你将其中10次对 double_x(x) 的调用, 都用 x+x 来替换, 那你将缺少10次打印

这只是个简单的例子, 你完全能将函数中的 println(x), 换成其他具有副作用, 而非单纯数运算的表达式
使用这些 non-RT 的家伙, 你将丧失进行恒等的能力, 问题推导更加复杂, 排查错误十分困难
你将需要额外使用复杂的工具, 去分析一段复杂的代码
这通常是一些 BUG 的来源

RT, 即引用透明, 注定与副作用互斥

纯函数

纯函数(Pure Functions), 表示引用透明的函数

引用透明的性质, 一个表达式可以拥有, 一个函数也可以拥有, 我们把这样的函数叫纯函数, 仅此而已
相对应的, 还有纯操作, 纯表达式, 纯代码等等差不多意思的表述, 知道就好

因为纯函数的引用透明性, 它不会去修改外界状态, 不去交互, 只是根据参数, 自给自足地算出结果而已
简单概括: 纯函数是一个独立的函数, 外面发生了什么鸟事, 和我有屁关系

一个函数独立, 可能没啥, 一堆函数独立, 表示它们可以一起计算, 因为它们之间没有交互, 比如:
有三个纯函数: f(x), h(x), g(x), 那么 f(x) + h(x) + g(x) 中, 三个函数直接并行计算即可
这意味着, 像 Haskell 这种语言, 本身就具有强大的并发性

但纯函数不是神, 无可避免要依靠副作用, 即使如此, 你也应尽量将 非纯函数 中纯的部分抽离出来

Lambda演算

你绝对绝对使用过 lambda(λ), 比如各大语言中的匿名函数:

// 在列表中先取出大于 0 的数, 然后转化为字符串  
let list = list.filter(|i| i > 0).map(|i| i.to_string());

这并非特定于编程语言的概念, lambda 演算被广泛运用于各种领域, 它的地位实际上与图灵机相同
诸如 "柯里化" 等特性都源自于 lambda 演算, 鼎鼎有名的 LISP, ML, Haskell 等众多语言, 都源自于 lambda 演算

它存在着三条重要的法则:

• Alpha转换: 重命名操作, 变量的名称是不重要的
  比如上述的 filter(|i| > 0) 可以写作 filter(|x| x > 0)
  
• Beta规约: 将参数值替换掉标识符
  比如 filter(|x| x > 0) 中, 用 10 代入到 x 进行运算
  别小看这条法则, 这是最最重要的一条, 也是后面讲的时候花费篇幅最长的一条
  这条法则, 使得 lambda 是图灵等价的一种理论, 也是之所以可以图灵完备的难的时候非常难)
  
• Eta化简: 避免等价函数的无意义膨胀, 阐明了不同形式的 lambda 的内在相等性
  |x| x.to_string() 等价于 |x| to_string(x) 等价于 to_string
  这会晓得为什么有些语言中, 当你传入这样闭包时, 会建议你改写成第三种形式了吧?
  

你肯定知道编程语言中的 Bool 类型, 还有 if/then/else 语句
lambda 演算不仅可以定义数字类型, 还能表达 布尔类型/重复/递归/分支 等
在之后的章节, 我们会利用上述的三条法则, 了解如何用 haskell 自己写一套 bool 类型, 与 if-else 语句
(其实很简单~~)

示例

以上是对函数式的小小概括
还有诸如柯里化, 惰性求值, 多态性, 类型约束等内容, 将会放在后面配合代码讲解

为了吸引小崽子们来学 Haskell, 能骗几个是几个, 特意来几段无比简洁的代码

• 埃氏筛求素数:

primes = filterPrime [2..]
  where filterPrime (p:xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]

• 斐波那契数列:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

• 快速排列:

qsort [] = []
qsort (x : xs) = qsort sList ++ [x] ++ qsort bList
  where (sList, bList) = partition (< x) xs

• 辗转相除法求最大公约数:

gcd' x y
  | y == 0 = x
  | otherwise = gcd' y (x `mod` y)

感谢你的观看, 咋们下期见!!
先让我鸽几天 :)