【转】关于 Haskell 的一些思考

• 纯函数编程？
• 副作用？
• 单子？
• 链表？

Posted on 2019年3月23日by xris

不管白猫黑猫，能捉到老鼠就是好猫。

虽然学了一会儿的 Haskell ，不过并没有专门花时间去学习猫论，所以这篇文章大概不会很数学。

但是会很幼稚，如果有错误的话希望能指出。

纯函数编程？

Much of the risk in software lies in talking to the outside world, be it coping with bad or missing data, or handling malicious attacks.

软件的大部分风险，都来自于与外部世界进行交互：它需要程序去应付错误的、不完整的数据，并且处理恶意的攻击，诸如此类。

就从这篇文章的起因说起吧。

某日午饭， leader 突然和我谈起了函数式编程——根本原因大概还是因为我提了一句我平时在家会读 SICP 吧——然后问了我个问题：“Haskell 是如何将副作用和纯函数隔离开来的？”我当时只是含糊的给出了“通过类型系统限制了在纯函数中使用非纯的动作，带有非纯的动作的类型签名中均有 IO 这个‘标记’”这么个说法。但是这套理论甚至没能把我自己说服。

首先 IO 这东西不只是个标记，它本身是一个类型构造器。在 Haskell 中表示非纯的动作，如 main 的签名即为 IO () ，是通过 IO 这个构造器和 () 这个具体类型构造出的一个新的具体类型。 IO a 作为一个类型本身并没有特殊的含义，它只是在 a 的类型之外套了一层 IO 而已。

不过这引出了我的另一个问题：“为什么类型签名中不带有 IO 的纯函数无法调用带有非纯的动作， IO 到底特殊在哪里？”

让我纠结的是下面这种代码，和正常的可以通过编译的代码的区别是最后没有 return ：

import System.IO

fileGetContents :: FilePath -> String
fileGetContents filename = do
  handle <- openFile filename ReadMode
  contents <- hGetContents handle
  contents

代码很简单，读取一个指定文件。当然，这段代码不能通过编译。报错也比较诡异，超出我的理解范围。暂且不去理会报错。

当然，我知道要加 return ，但是为什么这个 return 是必须的？在相关资料的搜索过程中受到启发，想到 do 语句块实际上是 >> 和 >>= 的语法糖，于是试着改写了一下。

fileGetContents :: FilePath -> IO String
fileGetContents filename = openFile filename ReadMode >>= hGetContents

事实上到这里已经可以看出一些端倪了：我从拿到 IO String 开始，就从来没有把 String 从 IO 中取出来过。所谓的 contents 的类型是 String，不过只是 do 语句块造成的一个假象而已。

那么原因就很明显了：

首先 Haskell 将所有的系统调用都封装到了 IO 中，于是所有对外的、需要操作系统提供服务的动作都有了 IO 这个标记。其次 IO 具有传染性，只要函数过程中出现了 IO ，就不可能再将 IO 从类型中抹去（不考虑 unsafePerformIO ）。因此，在将所有需要操作系统提供服务的动作都装到 IO 类型中之后，自然而然的所有的副作用都逃不开 IO 了。

副作用？

曾经在 Haskell Wiki 上看到一种对 IO 的解释，如果把整个世界看作一个对象，那么所谓的 IO ，就是在纯函数链之间不停地传递并修改世界的过程。

副作用到底是什么？我曾经在 StackOverflow 上看到一个问题——为什么对于 Haskell 而言，内存分配不算副作用，但是读写硬盘就是副作用了？

当我们在讨论副作用的时候，一定会有一个作用域。动了不归自己管的东西，这就是副作用，所谓的 side effect 。

对于一个函数而言，作为程序的一部分，程序的全局状态就是不属于自己的，因此修改一个全局变量就是副作用。对于一个程序而言，作为计算机的一部分，硬盘、网络也不是独占的，因此修改了硬盘和网路状态也是副作用。

在现代操作系统上，一个程序独占了它所能访问的内存（特殊情况太多啦，懒得排除了，就当是这样吧），它在内存中所有的操作都只是改变自身的状态。更何况 Haskell 设计中并没有内存这种概念，函数仅仅是从输入映射到输出而已，动作只是通过操作系统和外界交互而已。

Haskell 程序本身其实并不知道所谓的内存、硬盘是什么，一个 Haskell 程序只知道函数和动作之分。换句话说，它只知道做什么事情只改变自己状态，做什么事情需要外界的服务。而什么是自己的、什么是外界，其实是编译器来决定的。

因此，这些由编译器隐藏在抽象之后的，对内存的读写不应当被认为是副作用。

可是我还是感觉，上面的说法也有自相矛盾之处。如果我把有没有改变外界的状态作为区分函数和动作的标准，那程序自身作为这个世界的一部分，程序状态的改变也导致了世界状态的改变——一个间接的例子是，大量指令的执行会导致 CPU 的温度升高，会导致风扇开始转动，如果风扇因为什么原因卡住，甚至可能会导致 CPU 烧毁，机壳融化，导致火灾，导致破产，导致我失业，再也不写 Haskell 了。

当然我是开玩笑的。

那究竟什么是 Haskell 语义中副作用呢？结合一开始对 IO 的思考，我认为只有程序需要外界的服务才算是“副作用”。具体的“外界”是什么还是编译器，或者从代码上来说是库作者决定的。

反正 FFI 已经被编译器认为是带副作用的了，还能折腾到哪儿去呢？

单子？

A monad is just a monoid in the category of endofunctors, what’s the problem?

单子不过是自函子范畴上的幺半对象罢了，这有什么问题？

引用的这句话看起来很吓人，不过其实只是一个不懂加法交换律但是知道整数加法是个阿贝尔群的法国小学生（我和法国小学生的共同点大概是，法国小学生不会加法，而我不懂范畴论）。

来一个一个解释——

范畴 category，就是猫（不要想太多，真的只是博主不懂而已）。如所有的集合自成一个范畴，集合范畴 Set 。我们主要是在 Haskell 的类型范畴 Hask 上讨论。范畴自身又形成一个范畴，写作 Cat 🐱。

对象 object ，是一个范畴论概念。一个范畴可以有多个对象，举例有 Set 中的每个集合都是一个对象， Hask 中的每个类型都是一个对象。

态射 morphism 是对象间的映射。一个很具体的例子是，在集合范畴中，一个函数将定义域（这个集合对象）映射到值域（这个集合对象），则函数就是集合范畴的态射。

函子 functor 是范畴间的映射。而自函子 endofunctor 则是将一个范畴映射回本身的函子。

这也是后来我为什么不喜欢在 C++ 语境中用 functor 来表示一个可调用对象的原因。

自函子和恒等函数 identity 很像，区别在于，函数作用于值（这不是范畴论语境下的概念，只是平时说的函数和值而已），而函子作用于范畴。另外其实还有一个自同态 endomorphism ，当然啦它作用于对象。

自然变换 natural transformation ，虽然没用到，不过提一下，它是函子之间的映射。后面会提到“函子的组合函子”，有点拗口，不过其实就是一个自然变换。

幺半对象 monoid object ，是从幺半群 monoid 引申出来的概念。在集合范畴中它就是幺半群。幺半群就是一种集合和二元运算的组合。这个作用在集合上的运算满足结合律。而且还要有一个单位元。任何元素和单位元，不论是从左还是右的运算，结果都是该元素本身（之所以这么说是因为没有交换律）。

比较数学地定义幺半对象，是一个存在以下态射的对象 MM：

• \(\mu\) 态射，也就是 join 态射，定义是 \(M\otimes M\to M\)
• \(\eta\) 态射，也就是 unit 态射，定义是 \(I\to M\)

这里的 \(I\) 是终对象 terminal object 。不太想继续展开来解释，总之这个 \(I\) 在集合范畴中表示的就是只有一个元素的集合，特别的， \(\eta\) 在幺半群中就是单位元幺元。

正是因为范畴论中没有“集合的元素”，也就是“对象的成员”这种概念才把 \(\eta\) 定义搞得看起来这么奇怪，但是这个定义到了别的地方（比如 Hask 范畴中）又显得十分自然，自然到让人感觉精妙。

除此，还要满足两个性质：

• 结合律 \(\mu\circ(M\otimes\mu)=\mu\circ(\mu\otimes M)\)
• 单位元 \(\mu\circ(\eta\otimes M)=1_M=\mu\circ(M\otimes\eta)\)

看起来有点鬼畜，不过把括号展开了看起来就很明显了。 \(\circ\) 就是函子的组合运算。 \(\lambda\otimes M\) 或 \(M\otimes\lambda\) 是将 \(\lambda\) 态射的 \(\to\) 箭头两边对应位置都挂上一个 \(M\) 。 \(M\) 在 \(\otimes\) 左就挂原等式左边， \(\otimes\) 右就挂原等式右边。

只要展开就能看出结合律了（注意 \(f\circ g\) 先应用 \(g\) 再应用 \(f\)）：

• \[\mu\circ(M\otimes\mu)=\mu\circ(M\otimes(M\otimes M)\to M\otimes M)=\mu\]
• \[\mu\circ(\mu\otimes M)=\mu\circ((M\otimes M)\otimes M\to M\otimes M)=\mu\]

所以实际上一开始的那句话只是对于单子数学定义的一个描述，你找不到一个更合适的形容。或者索性可以直接说，它就是单子的定义。很无聊吧。

在 Haskell 中，单子被定义为一类 typeclass ：

class Applicative m => Monad (m :: * -> *) where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a

为什么这组成了一个单子呢？当然，首先它是一个自函子，因为它的所有态射都在 Haskell 的类型范畴 Hask 上，实际上 Haskell 中所有的 Functor 都是自函子。

其次， return 函数（在类型上的态射）就是 unit 函子。而 join 就是 Haskell 中的 Control.Monad.join 函数，它的定义是 join = (>>= id) 。看它们的类型签名，恰好和幺半对象中两个态射的定义一致。

至于结合律 join . fmap join = join . join 是很自然的事情。由于 join 实际上相当于将一对嵌套的 Monad 拍平的过程，那么两个 join 不管怎么结合的结果都是将三层 Monad 拍平。结合律是显而易见的。

join 的两种不同结合方式造成的唯一区别就是拍的顺序： join . fmap join 是先拍平内层再整体拍平， join . fmap join 则是从外面开始拍平。

顺便提提几个无关紧要的东西。 ES2019 中 Array 的 flat 对应 Haskell 中 Monad [] 的 join ， Array 的 flatMap 对应 Haskell 中 Monad [] 的 >>= 。 Rust 的标准库中也有类似的东西 std::iter::FlatMap 。这也是我顶上放这张图的原因。

而另一边 C++20 的 std::flat_map 则是一个完全无关的玩具（它是个类 std::map 的容器），很废柴的。

链表？

Thinking recursively.

我曾经疑惑过为什么 Haskell 要采用列表作为主要的存储方式，更何况它是在冯诺伊曼架构大行其道的年代设计的。

Haskell 被广为诟病的 String 和 ByteString 之别的根本原因也是因为 String 的定义是一个 [Char] ，字符链表。慢！比 Python 还慢！

后来在 pre C++11 写模板写多了注意到， 链表有着极其优美的递归结构。就比如说 List 的 tail :: [a] -> [a] 还是 List 本身， List 无论从中间哪里分开两段都是 List 。

而数组和变长数组就做不到，数组本质上是一个类型和大小的二元组，它的 tail 不是本身，而是一个更小一点的数组。于是对数组做这种 tail 操作，从类型上来说就变得比较丑陋。更何况更复杂的 map fold 系列呢（其实链表本身就是一个 fold 。这不怪链表，要怪 fold 过于🐮🍺）？

基于 List 的数据类型和高阶类型也为科里化提供了设计上的简洁和方便，而且显得十分优雅。科里化在 Haskell 的函数类型中就是一个不停去掉 head （就可以吃）的过程。

而在范畴论中，链表的结构对应着 Catamorphism 。虽然我一直没搞懂 catamorphism 是个什么东西，不过我们都知道 -morphism 是个挺高大上的东西，拿来装逼就是了。