现代C++函数式编程

导读：本文作者从介绍函数式编程的概念入手，分析了函数式编程的表现形式和特性，最终通过现代C++的新特性以及一些模板云技巧实现了一个非常灵活的pipeline，展示了现代C++实现函数式编程的方法和技巧，同时也体现了现代C++的强大威力和无限可能。

1
概述

函数式编程是一种编程范式，它有下面的一些特征：

函数是一等公民，可以像数据一样传来传去
高阶函数
递归
pipeline
惰性求值
柯里化
偏应用函数

C++98/03中的函数对象，和C++11中的Lambda表达式、std::function和std::bind让C++的函数式编程变得容易。我们可以利用C++11/14里的新特性来实现高阶函数、链式调用、惰性求值和柯理化等函数式编程特性。本文将通过一些典型示例来讲解如何使用现代C++来实现函数式编程。

2
高阶函数和pipeline的表现形式

高阶函数就是参数为函数或返回值为函数的函数，经典的高阶函数就是map、filter、fold和compose函数，比如Scala中高阶函数：

map

numbers.map((i: Int) => i * 2)

对列表中的每个元素应用一个函数，返回应用后的元素所组成的列表。

filter

numbers.filter((i: Int) => i % 2 == 0)

移除任何对传入函数计算结果为false的元素。

fold

numbers.fold(0) { (z, i) =>
a + i
}

将一个初始值和一个二元函数的结果累加起来。

compose

val fComposeG = f _ compose g _
fComposeG("x")

组合其它函数形成一个新函数f(g(x))。

上面的例子中，有的是参数为函数，有的是参数和返回值都是函数。高阶函数不仅语义上更加抽象泛化，还能实现“函数是一等公民”，将函数像data一样传来传去或者组合，非常灵活。其中，compose还可以实现惰性求值，compose的返回结果是一个函数，我们可以保存起来，在后面需要的时候调用。

pipeline把一组函数放到一个数组或是列表中，然后把数据传给这个列表。数据就像一个链条一样顺序地被各个函数所操作，最终得到我们想要的结果。它的设计哲学就是让每个功能就做一件事，并把这件事做到极致，软件或程序的拼装会变得更为简单和直观。

Scala中的链式调用是这样的：

s(x) = (1 to x) |> filter (x => x % 2 == 0) |> map (x => x * 2)

用法和Unix Shell的管道操作比较像，|前面的数据或函数作为|后面函数的输入，顺序执行直到最后一个函数。

这种管道方式的函数调用让逻辑看起来更加清晰明了，也非常灵活，允许你将多个高阶函数自由组合成一个链条，同时还可以保存起来实现惰性求值。现代C++实现这种pipeline也是比较容易的，下面来讲解如何充分借助C++11/14的新特性来实现这些高阶函数和pipeline。

3
实现pipeline的关键技术

根据前面介绍的pipeline表现形式，可以把pipeline分解为几部分：高阶函数，惰性求值，运算符|、柯里化和pipeline，把这几部分实现之后就可以组成一个完整的pipeline了。下面来分别介绍它们的实现技术。

高阶函数

函数式编程的核心就是函数，它是一等公民，最灵活的函数就是高阶函数，现代C++的算法中已经有很多高阶函数了，比如for_each, transform：

std::vector vec{1,2,3,4,5,6,7,8,9}
//接受一个打印的Lambda表达式
std::for_each(vec.begin(), vec.end(), [](auto i){ std::cout decltype(f(std::forward(param)))
{
return f(std::forward(param));
}
//test code
auto add_one = [](auto a) { return 1 + a; };
auto result = 2 | add_one; //result is 3

除了data和函数通过|连接之外，还需要实现函数和函数通过|连接，我们通过可变参数来实现：

template
inline auto operator|(fn_chain && chain, F&& f)
{
return chain.add(std::forward(f));
}

//test code
auto chain = fn_chain() | (filter >> [](auto i) { return i % 2 == 0; }) | ucount | uprint;

其中fn_chain是一个可以接受任意个函数的函数对象，它的实现将在后面介绍。通过|运算符重载我们可以实现类似于unix shell的pipeline表现形式。

柯里化

函数式编程中比较灵活的一个地方就是柯里化(currying)，柯里化是把多个参数的函数变换成单参数的函数，并返回一个新函数，这个新函数处理剩下的参数。以Scala的柯里化为例：

未柯里化的函数

def add(x:Int, y:Int) = x + y

add(1, 2) // 3
add(7, 3) // 10

柯里化之后

def add(x:Int) = (y:Int) => x + y

add(1)(2) // 3
add(7)(3) // 10

currying之后add(1)(2)等价于add(1,2)，这种currying默认是从左到右的，如果希望从右到左呢，然而大部分编程语言没有实现更灵活的curring。C++11里面的std::bind可以实现currying，但要实现向左或向右灵活的currying比较困难，可以借助tuple和前面介绍的tuple_apply来实现一个更灵活的currying函数对象。

template
class curry_functor {
private:
F f_;                      ///< main functor
Before before_;          ///< curryed arguments
After after_;             ///< curryed arguments

public:

curry_functor(F && f) : f_(std::forward(f)), before_(std::tuple()), after_(std::tuple()) {}
curry_functor(const F & f, const Before & before, const After & after) : f_(f), before_(before), after_(after) {}

template
auto operator()(Args... args) const -> decltype(tuple_apply(f_, std::tuple_cat(before_, make_tuple(args...), after_)))
{
      // execute via tuple
      return tuple_apply(f_, std::tuple_cat(before_, make_tuple(std::forward(args)...), after_));
}

// currying from left to right
template
auto curry_before(T && param) const
{
      using RealBefore = decltype(std::tuple_cat(before_, std::make_tuple(param)));
      return curry_functor(f_, std::tuple_cat(before_, std::make_tuple(std::forward(param))), after_);
}
// currying from righ to left
template
auto curry_after(T && param) const
{
      using RealAfter = decltype(std::tuple_cat(after_, std::make_tuple(param)));
      return curry_functor(f_, before_, std::tuple_cat(after_, std::make_tuple(std::forward(param))));
}
};

template
auto fn_to_curry_functor(F && f)
{
return curry_functor(std::forward(f));
}

//test code
void test_count()
{
auto f = [](int x, int y, int z) { return x + y - z; };
auto fn = fn_to_curry_functor(f);

auto result = fn.curry_before(1)(2, 3); //0
result = fn.curry_before(1).curry_before(2)(3); //0
result = fn.curry_before(1).curry_before(2).curry_before(3)(); //0

result = fn.curry_before(1).curry_after(2).curry_before(3)(); //2
result = fn.curry_after(1).curry_after(2).curry_before(2)();  //1
}

从测试代码中可以看到这个currying函数对象，既可以从左边currying又可以从右边currying，非常灵活。不过使用上还不太方便，没有fn(1)(2)(3)这样方便，我们可以通过运算符重载来简化书写，由于C++标准中不允许重载全局的operater()符，并且operater()符无法区分到底是从左边还是从右边currying，所以我们选择重载操作符来分别表示从左至右currying和从右至左currying。

// currying from left to right
template
auto operator>(const UF & f, Arg && arg) -> decltype(f.template curry_after(std::forward(arg)))
{
return f.template curry_after(std::forward(arg));
}

有了这两个重载运算符，测试代码可以写得更简洁了。

void test_currying()
{
auto f = [](int x, int y, int z) { return x + y - z; };
auto fn = fn_to_curry_functor(f);

auto result = (fn  decltype(call_impl(std::forward(arg), std::make_index_sequence{}))
{
      return call_impl(std::forward(arg), std::make_index_sequence{});
}

public:
fn_chain() : functions_(std::tuple()) {}
fn_chain(std::tuple functions) : functions_(functions) {}

// add function into chain
template< typename F >
inline auto add(const F& f) const
{
      return fn_chain(std::tuple_cat(functions_, std::make_tuple(f)));
}

// call whole functional chain
template
inline auto operator()(Arg&& arg) const -> decltype(call(std::forward(arg)))
{
      return call(std::forward(arg));
}
};

// pipe function into functional chain via | operator
template
inline auto operator|(fn_chain && chain, F&& f)
{
return chain.add(std::forward(f));
}

#define tfn_chain fn_chain()

//test code
void test_pipe()
{
auto f1 = [](int x) { return x + 3; };
auto f2 = [](int x) { return x * 2; };
auto f3 = [](int x) { return (double)x / 2.0; };
auto f4 = [](double x) { std::stringstream ss; ss decltype(std::get(functions_)(std::forward(arg)))
{
      return std::get(functions_)(std::forward(arg));
}

template
auto call_impl(Arg&& arg, const std::index_sequence&) const ->decltype(call_impl(std::get(functions_)(std::forward(arg)), std::index_sequence{}))
{
      return call_impl(std::get(functions_)(std::forward(arg)), std::index_sequence{});
}

在调用call_impl的过程中，将std::index_sequence不断展开，先从tuple中获取第I个function，然后调用获得第I个function的执行结果，将这个执行结果作为下次调用的参数，不断地递归调用，直到最后一个函数完成调用为止，返回最终的链式调用的结果。

至此我们实现具备惰性求值、高阶函数和currying特性的完整的pipeline，有了这个pipeline，我们可以实现经典的流式计算和AOP，接下来我们来看看如何利用pipeline来实现流式的mapreduce和灵活的AOP。

4
实现一个pipeline形式的mapreduce和AOP

前面的pipeline已经可以实现链式调用了，要实现pipeline形式的mapreduce关键就是实现map、filter和reduce等高阶函数。下面是它们的具体实现：

// MAP
template
auto fn_map(const C& container, const F& f) -> C
{
using resultType = decltype(f(std::declval()));
C result;
for (const auto& item : container)
      result.push_back(f(item));
return result;
}

// REDUCE (FOLD)
template
TResult fn_reduce(const C& container, const TResult& startValue, const F& f)
{
TResult result = startValue;
for (const auto& item : container)
      result = f(result, item);
return result;
}

// FILTER
template
C fn_filter(const C& container, const F& f)
{
C result;
for (const auto& item : container)
      if (f(item))
         result.push_back(item);
return result;
}

这些高阶函数还需要转换成支持currying的functor，前面我们已经定义了一个普通的函数对象转换为柯里化的函数对象的方法：

template
auto fn_to_curry_functor(F && f)
{
return curry_functor(std::forward(f));
}

通过下面这个宏让currying functor用起来更简洁：

#define make_globle_curry_functor(NAME, F) define_functor_type(F); const auto NAME = fn_to_curry_functor(tfn_##F());

make_globle_curry_functor(map, fn_map);
make_globle_curry_functor(reduce, fn_reduce);
make_globle_curry_functor(filter, fn_filter);

我们定义了map、reduce和filter支持柯里化的三个全局函数对象，接下来我们就可以把它们组成一个pipeline了。

[quote]void test_pipe()
{
//test map reduce
vector slist = { "one", "two", "three" };

slist | (map >> [](auto s) { return s.size(); })
      | (reduce >> 0 >> [](auto a, auto b) { return a + b; })
      | [](auto a) { cout  [](auto s) { return s.size(); })
      | (reduce >> 0 >> [](auto a, auto b) { return a + b; })
      | ([](int a) { std::cout

现代C++函数式编程

浏览过的版块