函数式编程在 C 中的应用

Question

函数式作为一种独特的编程范式，本着一切皆为函数的思想使它与传统的命令式编程、声明式编程形成了鲜明的差异。说到函数式编程，大部分人首先想到的是像 Lisp、ML、Haskell、Scala 这样的主打函数式编程的“纯”函数式语言，不过，这些语言从使用人数上来说算是小众语言，对于绝大部分的程序，命令式编程仍然占到主流。随着近些年来一些热门语言，如 Python、JavaScript 对函数式编程的越来越强的支持，函数式的思想可以说是逐渐成为了编程人员不可不知的一种主流编程范式。在这篇文章中我会讨论函数式编程在一门“古老”的语言——C++中的应用。可以看到，即使是 C++这种偏向底层的系统级开发语言，近几年来也逐步加入了对函数式编程越来越多的支持。

函数式编程简介

函数式编程相比传统的编程范式有许多特点，我们可以在这里简单列举一些主要的特点：

1. 函数被认为是“一等公民”：函数可以像其他数据类型一样，被很容易地定义，被赋值传递等。
2. 强调“无副作用”的函数/引用透明：函数内部不会修改任何的外部状态，且函数的返回值仅取决于传入的参数。
3. 变量是 不可变（immutable） 的：变量不同于命令式编程的储存单元，不能被赋值，只能说是计算得到了一个新变量。
4. 强调基于表达式而不是语句：表达式只是一个单独的计算过程，而语句一般表示“执行某个（产生副作用）的操作”，这与上面一点也是对应的。

正是有了这些特点的“约束”，函数式编程与之而来的也有许多命令式编程望而止步的优点，比如善于以一些短小精悍的小函数，逐步组建为一个功能强大的程序，在减少了代码重复的同时，也加快了程序开发速度；由于有了引用透明，函数在什么时候求值均可以，所以可以 惰性求值 ；由于函数不会修改外部状态产生副作用，代码可以完美转换到并行执行而不用担心数据竞争的问题…

C++这门语言从基于命令式的 C 语言发展而来，从源头上就和函数式编程“背道而驰”。比如函数不能随处定义传递；绝大部分函数都是有副作用的，还有专门为了副作用而生的函数（如 printf ）；基于语句而非表达式等。这就造成了很大的割裂，背后的原因也很明显，在 C 语言出现的那个年代，由于计算器的性能极低且极其昂贵，人们更偏向于“面向机器编程”，因此更接近机器底层的寄存器模型的 C 语言受到了广泛欢迎。不过到了今天，接近底层机器不再是优势，随着程序规模的膨胀，具有更好抽象能力、更接近数学的函数式编程方式更加受到人们的青睐。C++一直以来的设计目标是一种“多范式语言”，认为没有一种编程范式是适用于任何情况的，对各种编程范式的均支持才会有更强的表达能力。随着近几年的发展演变，C++引入了越来越多的函数式思想，让我们真正看到了函数式编程可以走入实际应用之中。

函数式编程与 C++

有人将函数式与命令式的区别总结为：

函数式编程关心数据的映射，命令式编程关心解决问题的步骤

命令式编程就好像告诉计算机每一步要做什么，而函数式编程则告诉计算机问题的定义是什么，余下的让计算机自行求解。举个例子，要求一个列表 [1,2,3,...] 的和，在命令式编程中我们会用一个 for 循环，定义累加变量，告诉计算机每一步要加上一个数：

c++

auto s = 0;
for (auto i = 0; i < L.size(); i++)
	s = s + L[i];

而在函数式编程中，根本没有循环这种结构，我们只需要告诉计算机求和的定义是什么就可以了：比如求和可以看做是列表的头加上剩余列表的求和，且空列表的和为 0。从这个简单的定义我们就可以得到如下的 ML 程序：

ml

fun sum [] = 0
  | sum (x::L) = x + sum L

显而易见，下面的程序比上面的程序更加简短，且不会出现循环条件错误，忘记初始化等等 bug。

如果单对函数式编程泛泛而谈，我们可能很难摸清其具体的轮廓。更好的方式是寻找函数式编程中的具体 特性 ，如果 C++对这些特性有足够的支持，那么它就足够用于函数式编程（当然，纯函数式的语言表达这些特性一般会更简单）：

1. 纯函数 （Pure Function）：函数不产生可以观测的副作用。C++中并没有明确表示纯函数的方式，不过只要函数本身没有对外部状态的修改，我们就可以认为它是纯函数。不过，并不是所有函数都是纯函数，总会有一些操作，它们不能以纯函数的形式表示（如 IO 操作），这时候我们可以放宽要求，允许一定的非纯函数，不过我们仍然可以让非纯函数的数量减到最少。

2. 对 递归 的支持：由于函数式编程中变量是不可变的，自然也就没有了循环结构，这时，如果算法需要迭代，唯一的途径只有递归，因此在函数式编程中需要大量用到递归，需要语言对递归有较好的支持，比如自动将尾递归转换为循环等。

3. 高阶函数 （High-Order Function）：参数为函数或者返回值为函数的函数，也就是函数要能够作为一等公民。在 C++中，高阶函数可以以函数指针或函数对象（Function Object）实现，比如一个函数对象就是重载了 operator() 运算符的类的实例：

   c++

   struct Add {
   	int operator()(int a, int b) { return a + b; }
   };

   C++11 及以后引入了 匿名函数 （Lambda Function），其本质上与函数对象相同，不过进一步简化了函数定义的语法，让函数可以随处进行定义和传递：

   c++

   auto Add = [](auto a, auto b) { return a + b; };

4. 偏应用的函数 （Partially Applied Functions）与 柯里化 （Currying）：对函数的部分参数提前进行绑定，得到需要剩下参数的函数。比如上面定义的 Add 函数，如果要改造为柯里化的形式，可以在 C++中写作：

   c++

   auto PartialAdd = [=](auto a) {
   	return [=](auto b) { return Add(a, b); };
   };

   这样，在应用时就可以提前绑定一个参数，在得到返回的函数后绑定剩下的一个参数：

   c++

   auto f = PartialAdd(2);
   auto x = f(5);			// x = 7; 

5. 闭包 （Closure）：闭包是自动捕获了外部状态的函数，在 C++中体现为有成员变量的函数对象。不过在 C++11 后的 Lambda 函数，我们可以很方便的捕获外部变量形成闭包。比如上面的 PartialAdd 函数就应用到了闭包，其外层函数捕获了 Add 函数，其内层函数捕获了传入 a 参数和 Add 函数。捕获的表示在两个方括号 [] 之间， [=] 表示的是默认以值拷贝的方式捕获，与之对应的还有 [&] 表示默认以引用的方式捕获。

6. 模式匹配 （Pattern Match）：模式匹配也是函数式编程中的一大利器，在递归时作为分支选择必不可少的攻击。可惜 C++中对模式匹配的支持尚且不强，运行时的函数只能通过 if 语句手动进行匹配，不过，C++对于编译时的模版元编程中还是支持了一定的模式匹配。

7. 惰性求值 （Lazy evaluation）：惰性求值可以让表达式的计算推延到实际使用时再进行，可以避免不必要的计算。在 C++中也有相应的方法实现惰性求值。

从上面可以看出 C++11 以后对函数式编程有着足够的支持，在一些方面不亚于函数式语言。我们可以从不同的几个实例来感受一下 C++中的函数式编程是什么样的。

实例

1. 高阶函数、泛型、闭包

在 C++中有多种对象都都可以被认为是函数。运用鸭子类型（Duck Typing）的说法：任何“可以像函数一样调用的东西就是函数”。前面说到，C++中主要有 3 种类型的函数：函数指针、函数对象（重载 operator() 的类对象）、匿名函数。要进一步地深入使用函数式，我们可以用数学化的方式表达类型。比如平时我们常见的函数声明方式一般是这样：

c++

int sqrThenAdd(int x, int y) { return x * x + y; }

这个函数的类型我们可以表示为 (int * int) -> int ，因为它可以看做是一个变化：将一个 int 二元组变换为一个 int 。在函数式语言中也可以很自然地得到如下定义与其类型：

ml

- fun sqrThenAdd (x : int, y : int) : int = x * x + y;
val sqrThenAdd = fn : int * int -> int

C++11 后也可以写成这种更自然的表示法：

auto sqrThenAdd(int x, int y) -> int { return x * x + y; }

不过，一般在函数式语言中我们不会明确标注类型，取而代之的是使用 泛型 ，并让编译器推导相关类型。这样既减少了对类型思考的负担，也增强了程序的适用范围。在 C++中也可以实现这个目标，比如使用模版函数：

template <typename Arithmetic1, typename Arithmetic2>
auto sqrThenAdd(Arithmetic1 x, Arithmetic2 y) -> decltype(auto) { return x * x + y; }

在这里， Arithmetic 代指一个泛型类型，返回值的 decltype(auto) 表示让编译器自动推导返回表达式的类型作为返回类型。当我们以 sqrThenAdd(1, 2) 调用时，编译器会将其推导为 (int * int) -> int ；而当我们以 sqrThenAdd(1.0, 2.0) 调用时，编译器会推导为 (double * double) -> double ，这里就体现了一个重要的特性—— 静态多态 ，极大地增强了函数的适用范围。不过，过大的范围也不是好事，比如这里的 Arithmetic 仅指代算术类型，即有 * 、 + 运算符的数据类型，对于其他类型这段程序是没有意义的。目前阶段的 C++要实现这个限制较为麻烦，而在 C++20 后即将引入了 Concept 较好地解决了这个问题。

另一种更为符合函数式的函数定义语法是匿名函数。在 C++14 之后加入的 Generic Lambda 让匿名函数也很好地支持了泛型，比如下面这个例子：

c++

auto mapThenAdd = [](auto f, auto x, auto y) { return f(x) + y; };

其中除了 auto 标识符并没有任何类型声明，其类型会像模版一样自动推导。可以看到 f 在函数体内被调用，是一类函数参数。 mapThenAdd 自身就是一个高阶函数，其作用是对参数 x 应用 f 函数并加上 y 。按照函数式语言中的数据类型定义， mapThenAdd 接受的是一个有 3 个元素的元组，如果我们想要柯里化的函数形式，需要对其的部分做绑定。在函数式编程中我们可能会写出以下的程序：

ml

fun mapThenAdd (f, x, y) = f(x) + y;
fun bind (f, arg) = fn (x, y) => f(arg, x, y);
val sqrThenAdd = bind(mapThenAdd, fn x => x * x);
val r = sqrThenAdd(2, 3);	(* r = 7 *)

上面这段程序将 mapThenAdd 函数的 f 参数提前进行绑定， bind 函数就是完成这个工作的高阶函数，传入其中的 f 和 arg 都被 闭包 绑定了下来，在绑定了一个平方函数后就返回了完成 sqrThenAdd 功能的函数。通过这个方法，我们也可以很容易地对这个函数进行柯里化。在 C++中实现相同功能也一样很简单：

c++

auto bind = [](auto f, auto arg) {return [=](auto x, auto y) {return f(arg, x, y);};};
auto sqrThenAdd = bind(mapThenAdd, [](auto x) {return x * x;});
auto r = sqrThenAdd(2, 3);	// r = 7

从上面的这些例子中，我们一窥了 C++中的函数式编程，有了这些语言上的基础，我们才得以将其逐步应用在更加实用且复杂的场合。

2. STL 中的函数式编程

STL（Standard Template Library）标准模版库是 C++的自带库，虽然 C++一直以来被认为是“面向对象语言”，也常常被用作“C with class”，但是 STL 的作者却很少地用到了面向对象的编程范式，而是大量用到了以模版为支撑的泛型编程与函数式编程的范式，在使用 STL 时就能明显的感到这一点。比如排序函数 std::sort 的用法：

c++

std::vector<int> ns {3, 7, 5, 2, 1};
std::sort(ns.begin(), ns.end(), [](int x, int y) {return x < y;});

这里 std::sort 的第三个参数是用于比较大小的谓词，也就是一个匿名函数。常见的比较谓词在标准库中已经写好了，比如上面程序中的小于谓词可以写作：

c++

std::sort(ns.begin(), ns.end(), std::less<int>());

在函数式编程中被大量使用的“三件套”：Map、Filter、Fold 在 STL 中也都有对应物。通过这 3 个函数的任意组合，我们可以创建处理变换数据的 流水线 （Pipeline），实现强大的功能。

让我们用一段小程序体会一下：假设现在我想实现一个统计代码行数的功能，输入是一个代码文本文件名组成的序列，输出是所有代码的总行数，但是要避免计入一些琐碎的小文件，也就是说对于行数少于 10 行的文件不计入总行数中。如果习惯了传统编程思维，很容易写出下面的代码：

c++

int count_lines_in_files(const std::vector<std::string> &files) {
    int  total_lines = 0;
    char c           = 0;

    for (const auto &f : files) {
        int           lines = 0;
        std::ifstream in(f);

        while (in.get(c)) {
            if (c == '\n')
                lines++;
        }

        if (lines >= 10)
            total_lines += lines;
    }

    return total_lines;
}

即使是一段简单的逻辑也用到了二重循环和几个维护局部状态的变量。这样写出来的程序确实能用，但是我们很快可以发现它的缺点：容易不小心出现 bug，比如局部变量忘记初始化、循环条件错误、状态设置错误等；此外程序显得啰嗦，修改起来也并不方便。

如果换成函数式的思想，需要将程序的“可变状态”减少，因为一旦状态一多，出错的可能性就大幅增加。稍加思索我们就可以发现这段程序所做的操作都在“三件套”描述的范围内：

1. Map：将文本文件名转换为文件的行数，转换函数的类型为 std::string -> int
2. Filter：筛选出不少于 10 的行数，谓词函数的类型为 int -> bool
3. Fold：计算出满足条件的行数之和，折叠函数为求和运算

通过使用 STL 中“三件套”的对应物，我们可以写出以下程序：

c++

int count_lines_in_files(const std::vector<std::string> &files) {
    std::vector<int> lines(files.size());

    auto count_lines = [](std::string file) -> int {
        std::ifstream in(file);
        return std::count(std::istreambuf_iterator<char>(in),
                          std::istreambuf_iterator<char>(),
                          '\n');
    };
    auto pred = [](int i) -> bool { return i < 10; };

    std::transform(files.begin(), files.end(), lines.begin(), count_lines); // Map
    auto lines_end = std::remove_if(lines.begin(), lines.end(), pred);		// Filter
    return std::accumulate(lines.begin(), lines_end, 0, std::plus<int>());	// Foldl
}

可以看到，高阶函数 std::transform 、 std::remove_if 、 std::accumulate 定义好了 Map、Filter、Fold 的操作，而我们只需要传入符合我们要求的函数，就可以描述出我们需要的功能，相比于命令式编程要清晰明了许多。另外，使用函数式的好处就是可以很轻易的复用已有的代码，比如在 count_lines 就用到了标准中的 std::count 函数来统计文件中的换行符的个数，其另外一个版本 std::count_if 就可以自己传入判断谓词，这样不管是什么我们外部的条件怎么变化，这个算法都可以适用。

在命令式的程序啰嗦且繁杂易出错的情况下，函数式程序仍然可以清晰地表述，并且更加符合人类的思维，这也是函数式的重大优点之一。此外还有一个函数式的闪光点：易于并行化。因为算法的高度复用性和引用透明性，函数式程序可以很轻易地变为并行程序，且不用当心各种竞争问题。实际上，函数式的并行算法只要在描述各种操作的高阶函数中完成一次就行，任何其他地方的调用都可以享受到并行的好处。比如只要将上面的代码加一个 std::execution::par 的标签就可以变为并行的版本：

c++

std::transform(std::execution::par, files.begin(), files.end(), 
			   lines.begin(), count_lines);

此外，函数式编程中还经常会用到一些常见的**“算术数据类型”**（Algebraic data type），它们在 STL 也有对应产物。比如在 Sumed Type 对应 std::variant 与 std::optional 、Product Type 对应 std::pair 与 std::tuple 等。这些原本在函数式语言中普遍使用的类型的引入也让平时的命令式编程得到了改进。

3. 模版元编程与函数式编程

C++的另一大亮点就是对编译期编程的支持。编译期编程是一个庞大的话题，甚至可以写一本上千页厚的书。不过我们还是可以简单地了解一下编译期编程与模版元编程，因为它们其实与函数式编程非常接近。

模版元编程，顾名思义，是基于 C++的模版而来的编程方式。C++的模版被创造的初衷是对泛型编程的支持，也就是创造出于类型无关的算法。不过人们很快发现它能做的事远远不止如此。由于模版中有着对 模式匹配 （Pattern Matching）的支持，它完全可以看做是一类纯函数式编程语言。举个经典的例子——计算斐波那契数列：

c++

template <int i>
struct Fib { static constexpr int value = Fib<i-1>::value + Fib<i-2>::value; };

template <>
struct Fib<1> { static constexpr int value = 1; };

template <>
struct Fib<0> { static constexpr int value = 0; };

const int x = Fib<20>::value;	// x = 6765

这个程序和函数式的程序如出一辙：

ml

fun Fib 0 = 0
  | Fib 1 = 1
  | Fib i = Fib(i-1) + Fib(i-2);

模版编程所做的事情很简单，C++编译器对于每次出现的模版类型，会将其模版参数代入， 实例化 出特定参数的类型，如果这个类型本身内部引用别的模版类型，实例化的过程就会递归进行…是不是很像函数式编程中的递归过程？这里模版参数就对应着函数参数，类型名对应着函数名，类型内部定义对应着函数体。此外 C++在对类型实例化时还会应用模式匹配，也就是说，匹配“最合适”的类型。在上面的例子中， Fib<1> 和 Fib<0> 被称作是 偏特化 的类型，就如同在函数式语言中匹配的特例一样，当实例化到它们的时候，编译器会选择最具体、最合适的偏特化类型，从而形成递归的终止条件。

让我们试试用元编程实现经典的找零问题：给定整数 n、一批硬币 L，是否能找出总值为 n 的硬币子集。实现的大致思路是，每次取出列表中的第一枚硬币，如果该硬币的数额比当前总值小，则有两种选择：一是使用该硬币，二是不使用该硬币；如过该硬币的数额比当前总值大，那么一定不能使用该硬币。该算法在 C++中可以用如下的模版元编程实现：

c++

template <int Select, int N, int X, int...Ls>
struct Change_Impl;

template <int N, int... Ls>
struct Change {
    static constexpr int solution_count = Change_Impl<2, N, Ls...>::value;
};

template <int N, int X, int...Ls>
struct Change_Impl<2, N, X, Ls...> {
    static constexpr int value = Change_Impl<int(X <= N), N, X, Ls...>::value;
};

template <int N, int X, int...Ls>
struct Change_Impl<1, N, X, Ls...> {
    static constexpr int value = Change<N - X, Ls...>::solution_count 
        					   + Change<N, Ls...>::solution_count;
};

template <int N, int X, int...Ls>
struct Change_Impl<0, N, X, Ls...> {
    static constexpr int value = Change<N, Ls...>::solution_count;
};

template <>
struct Change<0> { static constexpr int solution_count = 1; };

template <int N>
struct Change<N> { static constexpr int solution_count = 0; };

int main() {
    return Change<10, 1, 3, 6, 4, 5>::solution_count;	// 3 种(1+3+6,6+4,1+4+5)
}

看起来十分复杂，但是仔细看的话，这个程序只是在简单地使用模式匹配。传入 Change 的第一个模版参数为目标总额，其余的模版参数为硬币数额列表，以一个变长模版参数包表示 int... Ls 。底下两行匹配的是硬币列表为空时的情况，当此时的目标金额为 0 时则有一种解决方法；否则没有解决方案。为了方便模式匹配，还定义了 Change_Impl 结构体，它仅接收非空列表，并会对目标金额与首枚硬币的金额进行判断，依次作为匹配依据。 Change 最后会得到找零方案的个数，比如硬币列表为 [1, 3, 6, 4, 5] ，目标金额为 10 时得到的找零方案有 3 种。

可以看出，模式匹配让我们可以很方便的实现判断逻辑，配合递归可以实现复杂的逻辑。借助函数式编程的思想，模版元编程也可以有很强的表达能力。

总结

本文简单的概述了一些函数式思想在 C++中的应用，这种简洁高效的编程范式让 C++这门被广泛运用的语言有了更强的表达能力。我们也看到了，函数式编程让我们的思维从“告诉计算机每一步的步骤”转变为“告诉计算机问题是什么”，从而得到更接近数学的抽象能力，也让程序免于 Bug 的灾难。不过，函数式编程也不是万能的，有许多问题不能用“纯函数式”的思想实现。而 C++这门多范式语言让我们有了更加丰富的选择：不管是命令式、面向对象、函数式，还是泛型编程，都可以作为工具，只要我们将它们用在合适的地方。