用C++学习函数式编程（一）

最近刚认识了函数式编程，觉得这个东西很神奇，我对于编程的思想之类的东西还是很感兴趣的，刚好找到了一本合适的书就叫《C++函数式编程》，作者是[塞尔维亚]伊凡·库奇。

为什么要学习函数式编程

很认同作者第一页的一句话，

假如只有一把锤子，那么很可能把所有的问题都看作钉子。反过来也是一样，如果碰到一个钉子，就会把手头的任何工具当作锤子。

我也认为学习编程的乐趣就是学到更多的解决问题的方法，或者说是巧妙的，优雅的解决方法。而且学习不同的编程方法，也是一种思维方式上的改变，能够让我们用不同的方式来思考问题，甚至是用不同的方式来认识世界和描述世界。

什么是函数式编程

函数式编程的主要思想是：不应该关注某些东⻄应该如何工作，而应该关注它应该做什么。

我的理解就是我们需要关注的是它的目的，一个函数是把什么输入变成了什么输出，而不是关注它如何实现的。

函数式编程的核心思想是纯函数，纯函数满足两个特点

只使用而不修改传递给它的实参。
相同实参多次调用将得到相同的结果，无副作用。

不过这在计算机上是不可能实现的，所以书上放宽了定义，只要没有可见副作用，看不到执行痕迹，就叫纯函数。

函数式编程的优势

没有副作用，可以并行化
代码简洁易读

其实按照一般文章，优势应该是放在为什么里面的，而且按照是为怎的顺序，应该先说是什么再说为什么，但是这是我的文章，我是先有了想学的理由，才了解是什么。学想东西可以有很多种理由，并不一定是因为知道它有什么优势所以才学，而且我也没有过多关注它的优势，我学习它只是想写出更加优美而巧妙的代码。

如何进行函数式编程

首先，我也认为我们应该尽量使用STL提供的算法，毕竟是经过标准委员会的审核的，无副作用且高效的，且未来标准库继续优化也能够给使用标准库编写的程序带来优化。

先来认识几个常用的高阶函数。

变换函数，transform

transform，接受四个参数，两个输入迭代器、一个输出迭代器和一个变换函数，将一对迭代器限定的范围上的每个元素应用变换函数的结果复制到输出迭代器上。

int str_len(string a){return a.size();}

transform(istream_iterator<string>(cin)
    ,istream_iterator<string>()
    ,ostream_iterator<int>(cout," ")
    ,str_len);

懒得想数据还有分配空间了，所以直接用了标准输入输出来举例子，顺便给没见过这种写法的人扩展一下见识，输入输出迭代器还可以这样用。

上面这个函数的意思就是，对于标准输入流读取的每个字符串获取长度，然后输出。

折叠函数，accumulate

accumulate接受4个参数，两个输入迭代器，一个初始值和一个二元谓词函数。这个函数非常有意思，可以实现很多有意思的事情。

它的流程大概是，将初始值作为二元谓词的第一个参数，第一个元素作为第二个参数，进行第一次谓词操作，之后将返回值作为下一次操作的第一个参数，元素作为第二个参数，以此类推，书上有个很好理解的图，

正向迭代器是左结合，如果想要实现右结合就使用反向迭代器。这个东西的使用方法取决于想象力，我看见这个东西的时候顿时就想通了如何用函数式编程来写动态规划了。

过滤函数，filter

一个好消息和一个坏消息，C++没有叫filter的函数，跟它功能相似的叫copy_if，但是好消息是，C++20的标准大多已经完善了，可以用range了，可以用管道来组合，比之前的用函数组合的方便很多，而且节省了中间变量。

copy_if接受四个参数，两个输入迭代器、一个输出迭代器和一个一元谓词，将一对迭代器限定的范围上的每个元素应用一元谓词，满足的元素复制到输出迭代器上。

copy_if(istream_iterator<int>(cin)
    ,istream_iterator<int>()
    ,ostream_iterator<int>(cout," ")
    ,[](int x){return x>5;});

组合使用

函数式编程有意思的地方就是，你可以通过组合高阶函数来实现算法，就像搭积木一样，接下来就是实战使用了。

作业实战

书上第二章的课后习题，写一个函数式的插入排序。

vector<int> order_insert(vector<int>A,int x){
    A.insert(lower_bound(A.begin(),A.end(),x),x);
    return A;
}
vector<int> insert_sort(vector<int>A){
    return accumulate(A.begin(),A.end(),vector<int>(),order_insert);
}

这个的大致流程就是，将每一个元素，在有序表中找到它应该在的位置然后进行有序插入。这里我还无意中实现了一个时间复杂度$O(n\ln n)$的插入排序（如果任意位置插入的时间复杂度是$O(1)$的话），这里关键就是lower_bound是二分查找实现的在有序容器中查找小于x的边界，时间复杂度是$O(\ln n)$。

扩展一下我之前说的动态规划的写法，来整点有意思的花活，一行流。

leetcode第64题，最短路径和，经典二维动规，不过我写的不够纯粹，有一个lambda里面不是直接return的。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        return accumulate(grid.begin(),grid.end(),[&grid]{vector A(grid[0].size(),numeric_limits<int>::max());A[0]=0;return move(A);}(),[](vector<int>&&p,vector<int>&c){return move(accumulate(c.cbegin(),c.cend(),pair{pair{p[0],p.cbegin()},vector<int>()},[](auto&&P,auto&x){return pair{pair{P.second.emplace_back(x+min(P.first.first,*P.first.second)),P.first.second+1},move(P.second)};}).second);}).back();
    }
};

提交结果，

原本的时间和内存过于惨不忍睹了，我只好手动使用move还有引用来优化了一下，让它看起来不会太难看。

结尾

折叠函数的管道版本在C++23也进入标准库了，不过我还没能用上，之后去找新版本的编译器来试一下。下一篇文章会介绍一些算法库里面的函数。