函数式程序设计 / 程序演算入门 Part 1

本文是对胡振江老师所教授的计算概论课实验班内容的期末复习笔记，但因为这部分内容很有意思，所以我会尽量写得通俗易懂，能够让大家也“云课堂”。考虑到大家都是 OIer，所以我也不会写得很啰嗦，保证大家的阅读体验。

首先简述一下这门课大致的学习路线：Haskell -> Agda -> Bird Meerteen Formalism。下面我们一个一个来说。

函数式编程（Functional Programming）

在这门课中首先你将会学习函数式编程的基本思想。函数式编程简单来说就是：只有常量，没有变量。各位对面向对象、面向过程这一类编程范式想必已经精通，但函数式编程和算法竞赛中学习的内容相去甚远。

C++ 对函数式编程的支持近乎为零。虽然官方在很努力地抄 Haskell 了，但是它自身的历史包袱以及应用场景就决定了没人用它写函数式编程。例如它难以方便地对函数进行变换。我们还是可以勉强用 C++ 来写一些函数式编程：

int fact(const int n) {
  return n == 0 ? 1 : fact(n - 1) * n;
}

这算是遵循 FP 思想写出来的最简单的函数式编程了，它的作用想必大家都了解，等价的 Haskell 代码如下：

fact :: Int -> Int -- 其实这行可以省略
fact n = if n == 0 then 1 else n * fact (n - 1)

想必大家还在疑惑函数式编程有什么用。客观来说它有很多用处，但是要说现阶段最能说服诸位且又能短时间理解的用处，我们会在后面提到。下面我们来说一个简单的用处：描述一个计算（Specification）。

课程中的例子是最大子段和。如果你要向计算机描述最大子段和的问题怎么做？我们可以定义一个函数，这个函数接受一个序列返回一个最大子段和。这样计算机就知道了最大子段和的计算要求。当然，聪明的各位肯定是会写最大子段和的线性算法的，但我们要探讨的不是这个算法，而是得到这个算法的过程。

我们能够“推理”出最大子段和的线性算法吗？

这个问题还是太模糊了，我们还缺很多前置知识，但是在这些前置知识里最先要确定的是问题的描述（Specification）。最大子段和最本质的含义是：一个序列所有子区间分别求和，再计算所得到的数中的最大值。我们需要把这个最本质的定义做出形式化地描述，再搞一些基本的推理规则（公理，就和大家写数学几何证明题一样），这样我们才能推导出最大子段和的线性算法。

也就是说，算法不都是凭空想出来的，一个算法是可以被推理出来的，听起来还不错？

要描述最大字段和问题当然得用我们的函数式语言描述，为什么 C++ 不行等会儿说。以 Haskell 为例：

mss :: [Int] -> Int
mss = maximum . map sum . concat . map tails . inits
-- 等价写法 （haskell 里一个函数多个参数是不需要加逗号的）
mss2 as = maximum (map sum (concat (map tails (inits as)))) 

我们使用了一堆函数的复合（composition）来描述最大子段和问题。下面来一一解释一下上面的函数（按从右往左的顺序）：

• inits 会求出一个序列的所有前缀：

  inits :: [t] -> [[t]]
  inits [] = [[]]
  -- (a : as) 是非空序列的表示，a 的类型为 t（表示第一个元素），as 类型为 [t] 表示之后的其他元素
  -- 在 Haskell 中列表拆第一个元素比拆最后一个元素快（语言特性）
  -- 冒号 : 在这里是运算符
  inits (a : as) = [] : map (a :) (inits as)

• tails 会求出一个序列的所有后缀：

  tails :: [t] -> [[t]]
  tails [] = [[]]
  tails (a : as) = (a : as) : tails as

• map f 会将一个序列里的元素$a_i$全部变成$f(a_i)$：

  -- (t -> p) 表示接受一个类型为 t 的值，返回一个类型为 p 的值的函数
  map :: (t -> p) -> [t] -> [p] 
  map f [] = []
  map f (a : as) = f a : map f as

• concat 表示把一个 [[t]] 类型的列表“拍扁”拼成一个 [t] 类型的列表：

  concat :: [[t]] -> [t]
  concat [] = []
  -- ++ 是运算符表示列表的拼接
  concat (a : as) = a ++ concat as

• sum 是对一个列表中所有元素求和

  -- 之前的 t、p 都是任意类型（类似 C++ 的模板），而这里的 Int 是具体的类型
  sum :: [Int] -> Int 
  sum [] = 0
  sum (a : as) = a + sum as

• maximum 表示对一个列表中所有元素求最大值：

  maximum :: [Int] -> Int 
  maximum [] = 0
  maximum (a : as) = max a (maximum as)

不熟悉 Haskell 的同学可能有点看不下去了，所以我们给出与之等价的 C++ 实现：

//by Yao
#include <iostream>
#include <vector>
#include <functional>
#include <climits>
using std::cout;
using std::vector;
using std::ostream;
using std::function;
#define L vector
#define F function

// 调试用
ostream & operator<<(ostream & out, const L<int> vs) {
  out << "[ ";
  for(int x : vs) out << x << " ";
  out << "]\n";
  return out;
}
// 模拟 : 运算符
// 这是一个高阶函数，也就是说返回值为函数的函数
//  L<int> as = {1, 2, 3};
//  cout << cons(5)(as);
template<class t> 
F< L<t>(L<t>) > cons(const t a) {
  return [=](const L<t> as) {
    L<t> res = as;
    res.insert(res.begin(), a);
    return res;
  };
}
//  F<int(int)> square = [](int x) { return x * x; };
//  cout << map(square)(L<int>{1,2,3,4,5});
template<class t, class p>
F< L<p>(L<t>) > map(const F<p(t)> f) {
  return [=](const L<t> vs) {
    if(vs.empty()) return L<p>{};
    const t a = vs[0];
    const L<t> as = L<t>(vs.begin() + 1, vs.end());
    return cons(f(a))(map(f)(as));
  };
}
//  for(auto xs : inits(L<int>{1,2,3,4,5})) {
//    cout << xs;
//  }
template<class t>
L<L<t>> inits(const L<t> vs) {
  if(vs.empty()) return {{}};
  const t a = vs[0];
  const L<t> as = L<t>(vs.begin() + 1, vs.end());
  return cons(L<t>{})(map(cons(a))(inits(as)));
}
//  for(auto xs : tails(L<int>{1,2,3,4,5})) {
//    cout << xs;
//  }
template<class t>
L<L<t>> tails(const L<t> vs) {
  if(vs.empty()) return {{}};
  const t a = vs[0];
  const L<t> as = L<t>(vs.begin() + 1, vs.end());
  return cons(cons(a)(as))(tails(as));
}
//  cout << cat(L<int>{1,2,3,4,5})({3,4,5,6,7});
template<class t>
F< L<t>(L<t>) > cat(const L<t> as) {
  return [=](const L<t> bs) {
    if(as.empty()) return bs;
    const auto a = as[0];
    const auto ass = L<t>(as.begin() + 1, as.end());
    return cons(a)(cat(ass)(bs));
  };
}
//  cout << concat(L<L<int>>{{1,2},{3,4},{5, 6, 7}});
template<class t>
L<t> concat(const L<L<t>> vs) {
  if(vs.empty()) return L<t>{};
  const auto a = vs[0];
  const auto as = L<L<t>>(vs.begin() + 1, vs.end());
  return cat(a)(concat(as));
}
//  cout << sum({1,2,3,4,5});
int sum(const L<int> vs) {
  if(vs.empty()) return 0;
  const auto a = vs[0];
  const auto as = L<int>(vs.begin() + 1, vs.end());
  return a + sum(as);
}
//  cout << maximum({1,2,3,4,5});
int maximum(const L<int> vs) {
  if(vs.empty()) return INT_MIN;
  const auto a = vs[0];
  const auto as = L<int>(vs.begin() + 1, vs.end());
  return std::max(a, maximum(as));
}
int mss(L<int> vs) {
  // 尖括号里的类型无法省略不然会 CE
  return maximum(map<L<int>, int>(sum)(concat(map<L<int>, L<L<int>>>(tails<int>)(inits(vs)))));
}
int main () {
  cout << mss({1,2,-4,4,5});
  return 0;
}

相信各位已经明白了 C++ 为什么不行，毕竟它不是专为函数式编程设计的语言，写起来太麻烦还很别扭。在函数式编程领域，Haskell 是王者之一。

你可能会说上面的 C++ 代码写法有很多复杂度较大而且很别扭的地方。这个是强行用 C++ 模拟函数式编程的结果。如果要以指令式编程来写，那当然又是另一种写法。

为什么我们非要用函数式编程来描述 Specification 呢？

• 为什么函数式可以：下面会讲。
• 为什么指令式不可以：胡老师并没有详细讲。所谓的不可以，其实是指没人这么干，我的理解是指令式编程如果要用数学语言描述，会涉及到状态变换，而这个过程目前还不太好做形式化地处理（太复杂了）。

回到最大子段和的 Specification：

mss = maximum . map sum . concat . map tails . inits

如果你习惯了 Haskell，你其实是可以把它从右往左“读出来”的：

1. 先求出原序列的所有前缀
2. 再把每个前缀变成它自己的后缀，这样我们就得到了原序列的所有子区间
3. 但是目前我们拿到的是个三维列表（数组），所以需要做一下顶层拼接转化为二维列表
4. 然后把每个子区间变成它的数字和（这样二维列表也就变成了一维列表）
5. 然后再把所有的数求出最大值

可以发现，函数式编程利用了基本函数的复合与变换，将原问题的语义清晰地表达出来。这也符合我们平时的语言习惯，函数就像是一个动作，一个指示。当然，这个方法并非万能，有些算法使用指令式语言来描述会更简洁。

高阶函数（High Order Function）

各位如果有仔细阅读上文的代码就会发现，Haskell 中大量使用了高阶函数。C++ 代码之所以如此丑陋就是因为我强行使用高阶函数写法来与 Haskell 代码形成准确对应。而在函数式编程里，高阶函数极其常见。把一个多参数函数变成高阶函数的方法不唯一（看用途），不过一个常见的方法叫做柯里化（curry）。以最大值函数为例，max(a, b) 是一个接收两个参数返回一个最大值的函数，我们可以将它改成 max(a)(b)，其中 max(a) 的返回值是一个函数，这个函数接收一个参数并将其与 a 比较，返回最大的那个。C++ 的写法见上文。多参数同理，f(a, b, c) 会被转化为 f(a)(b)(c)。

Haskell 的确有元组的概念，使用 (a, b) 的方式可以表示二元组（多元组也可），但是你几乎见不到使用元组来表示参数类型的函数，Haskell 的库函数几乎全部柯里化。在 Haskell 中，max a 会返回一个函数（作用同理），而 max a b 等价于 (max a) b。

柯里化的好处在于，我们可以更简洁地描述计算过程。比如说我们要把一个序列 as 中的数对 x 取最大值，那么使用 Haskell 来写就是 map (max a) as。而在 C++ 中你可能会需要用到 for 循环。

不妨对照上文 Haskell 代码中的类型声明。以 map 为例：map :: (t -> p) -> [t] -> [p] 等价于 map :: (t -> p) -> ([t] -> [p]) （箭头符号默认右结合）。第一个参数的类型是一个从 t 类型到 p 类型的函数，第二个参数的类型是 [t]（类型为 t 的列表），返回值类型是 [p]。

序列变换函数

学习英语的基础是单词，单词背够了才能有效学习更多的内容。函数式编程同理，对于没有接触过函数式编程的同学来说，你们目前的词汇量都几乎为零，你们平时所编写的函数大多是为了降低耦合或者做模块化处理，归属于面向对象的范式。为了方便大家理解后续内容，我们列出一些基本的函数来打打基础。节约时间，这里只会列出有关列表的函数。

当然，为了让大家快捷地理解 Haskell 代码，我们先讲讲 Haskell 代码中的列表的定义，以及它的用途。

在 Haskell 中构造列表有两种方式：[] 代码任意类型的空列表（具体类型由上下文决定），而 (a : as) 表示将元素 a 插入到列表 as 的开头形成的列表（不会改变 as 的值）。顺带一提，Haskell 的类型检查是吊打 C++ 的，所以你在有的代码中没有看到类型声明是正常的事情，因为编译器会推断。

[] 和 : 均可以理解为函数。[] 是不接受参数的函数（参数列表为空），而 : 是接受两个参数的函数。

-- 列表的映射函数，用法见上文
map :: (t -> p) -> [t] -> [p] 
map f [] = []
map f (a : as) = f a : map f as

-- 列表的拼接。
-- 打括号的意思是 ++ 是一个二元运算符。Haskell 可以定义各种千奇百怪的自定义运算符
-- ++ 的用法很多。a ++ b 是正常用法，等价于 (++) a b（当成函数用）
-- 同理 (++) a 的返回值是一个函数，这个函数接受一个参数 b，返回在 b 前面拼接 a 的结果
-- 针对二元运算符 Haskell 有一些巧妙的语法糖，(++) a 等价于 (a ++)，上文的 (a :) 同理。
-- 类似，(++ b) a = (a ++) b = a ++ b = (++) a b = ((++) a) b，所有二元运算符都可以这么用。
-- 这里相当于做了一个 switch。如果第一个是空列表就返回第二个。否则就递归把 as 和 b 拼起来再在开头插入 a
(++) :: [t] -> [t] -> [t]
[] ++ b = b
(a : as) ++ b = a : (as ++ b)

-- 右结合的运算
-- 例如 foldr (+) 0 [1,2,3,4,5] 返回值为 1 + (2 + (3 + (4 + (5 + 0))))
-- 同理 foldr f 0 [1,2,3] = f 1 (f 2 (f 3 0))
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f e [] = z
foldr f e (a : as) = f a (foldr f e as)

-- 左结合的运算
-- 例如 foldl (+) 0 [1,2,3,4,5] 返回值为 ((((0 + 1) + 2) + 3) + 4) + 5
-- 同理 foldl f 0 [1,2,3] = f (f (f 0 1) 2) 3
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e [] = z
foldl f e (a : as) = foldl f (f e a) as

-- 与 foldr 差不多，唯一的区别是它会把中间计算结果全部返回
-- scanr max 0 [1, 2, 3, 2, 1] = [3, 3, 3, 2, 1, 0]
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr f e [] = [e]
scanr f e (a : as) = let (xs : xss) = scanr f e as in f a xs : (xs : xss)

-- 与 foldl 差不多，唯一的区别是它会把中间计算结果全部返回
-- scanl max 0 [1, 2, 3, 2, 1] = [0, 1, 2, 3, 3, 3]
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e [] = [e]
scanl f e (a : as) = e : scanl f (f e a) as

-- 把一个元素转化为一个单元素列表
singleton :: a -> [a]
singleton x = [x]

-- 返回自身的函数
id :: a -> a
id x = x

有了这些基础，我们已经可以做一些基本的程序演算了，大家不妨尝试证明以下定理（=== 表示等价于，不是赋值符号）：

concat . map singleton === id

这里 === 表示两个函数等价，也就是说无论接受什么参数等式两边都返回相同结果（这个参数必须同时满足左右两边的类型要求）

其实观察 concat 可以发现，它的递归写法等价于 foldr (++) []，因此大家可以再尝试证明

foldr (++) [] === foldl (++) []

这些证明都非常简单，目的是让大家理解这样的函数式语言的思维表达方式。