Getting started with functional programming

开始函数式编程

higher-order functions-高阶函数

所有FP语言的主要特点是函数可以像普通值一样处理。它们可以存储到变量中，放入集合和结构中，作为参数传递给其他函数，并作为结果从其他函数返回。

将其他函数作为参数或返回新函数的函数称为高阶函数。

下面这两个模式在FP中很常见：

filter: (collection<T>, (T → bool)) -> collection<T>
transform: (collection<In>, (In -> Out)) -> collection<Out>

STL中的高阶函数示例

如何求一组数的平均值？

double average_score(const std::vector<int>& scores)
{
    int sum = 0;
    for (int score : scores)
    {
        sum += score;
    }
    return sum / (double)scores.size();
}

利用std::accumulate:

double average_score(const std::vector<int>& scores)
{
    return std::accumulate(
        scores.cbegin(), scores.cend(),
        0
    ) / (double)scores.size();  // 初始值为0并求范围的和
}

在c++17中，可以实现并行计算：

double average_score(const std::vector<int>& scores)
{
    return std::reduce(
        std::execution::par,
        scores.cbegin(), scores.cend(),
        0
        ) / (double) scores.length();
}

也可以增加一个函数对象，改为求乘积：

double scores_product(const std::vector<int>& scores)
{
    return std::accumulate(
        scores.cbegin(), scores.cend(),
        1,
        std::multiplies<int>()
    );
}

Folding

上述std::accumulate算法就是folding概念的实现。Folding将一般的迭代过程抽象成递归结构。

它首先将传递给它的初始值和集合中的第一项相加，然后将该结果与集合中的下一项进行相加，以此类推，一直重复，直到集合的末尾。如下图所示：

下面是计算一个string中’\n’的个数的算法：

int f(int pre_count, char ch)
{
    return c != '\n' ? pre_count : pre_count + 1;
}int count_lines(const std::string& s)
{
    return std::accumulate(
        s.cbegin(), s.cend(),
        0,
        f
    );
}

其中：

f: (R, T) -> R -- 集合元素类型为T， 初值类型为R

对于那个累加的版本，也可以这样理解，将f看作是+运算：

这种从范围的开始来处理元素的叫做left-fold。

还有right-fold，它表示从范围的结束也就是最后一个元素开始处理，一直到第一个元素。

下图是左右折叠的区别：

C++并不提供right-fold的算法，但是可以通过反向迭代器crbegin和 crend来实现相同的效果