针对list的高阶算法，是允许用户在使用时传入别的元函数做参数的元函数。在函数式语言里对于list的高阶元函数（如经典的filter，map，fold...），可以轻松地让用户通过函数组合来扩展对list的操作。
下面我们先实现一个简单的__any()高阶元函数，它接收一个list以及一个单参元函数Pred做入参（该元函数接受一个类型，返回一个BoolType类型）；__any()对list中每个元素调用Pred，如果Pred对某一个元素返回TrueType，则__any()返回TrueType；否则如果Pred对所有的元素都返回FalseType，则__any()返回FalseType。
// "tlp/list/algo/Any.h"
template<typename TL, template<typename T> class Pred> struct Any;
template<template<typename T> class Pred>
struct Any<NullType, Pred>
{
using Result = FalseType;
};
template<typename Head, typename Tail, template<typename T> class Pred>
struct Any<TypeElem<Head, Tail>, Pred>
{
using Result = typename IfThenElse<typename Pred<Head>::Result, TrueType, typename Any<Tail, Pred>::Result>::Result;
};
#define __any(...) typename Any<__VA_ARGS__>::Result
__any()的递归实现中，对list的头元素调用Pred：Pred<Head>::Result，如果为真，则返回TrueType；否则对list的剩余尾list继续调用__any()：Any<Tail, Pred>::Result>::Result；一直递归到空list，最后返回FalseType。
在这里我们用了元函数IfThenElse，由于它的惰性，我们可以在Pred为当前元素求值为TrueType的时候提前停止递归，后面的元素就不用再算了。另外也可以这样实现：using Result = __bool(__value(typename Pred<Head>::Result) ? true : __value(typename Any<Tail, Pred>::Result))。这种实现用了三元表达式，但由于这种运行时技术缺乏惰性，所以实际上每个元素都被求值了！
接下来我们实现元函数__all()。它的入参和any()一样，差别在于所有的元素应用Pred后都返回TrueType，__all()才会返回TrueType；只要有一个元素应用Pred后返回FalseType，则__all()返回FalseType。
参考了__any()的实现，我们轻松实现__all()如下：
template<typename TL, template<typename T> class Pred> struct All;
template<template<typename T> class Pred>
struct All<NullType, Pred>
{
using Result = TrueType;
};
template<typename Head, typename Tail, template<typename T> class Pred>
struct All<TypeElem<Head, Tail>, Pred>
{
using Result = typename IfThenElse<typename Pred<Head>::Result, typename All<Tail, Pred>::Result, FalseType>::Result;
};
#define __all(...) typename All<__VA_ARGS__>::Result
可以看到，__all()和__any()的实现非常相像！事实上，我们可以借助__any()来实现__all()，从而消除这两者之间的重复。
首先我们需要借助__any()计算list中是否有某一元素应用Pred后为假，如果没有一个为假，则__all()返回真。我们知道客户传入给__all()的Pred是一个单参元函数，它在满足条件后返回真。我们需要把客户传入的Pred转变成另一个在满足条件后返回假的单参元函数。于是我们实现了NegativeOf元函数，它是一个高阶函数，接受一个返回值是BoolType的单参元函数，返回一个取反之后的单参元函数。
// tlp/func/NegativeOf.h
template<template<typename T> class Pred>
struct NegativeOf
{
template<typename U>
struct Apply
{
using Result = typename Not<typename Pred<U>::Result>::Result;
};
};
#define __negative_of(...) NegativeOf<__VA_ARGS__>::template Apply
最终__all()的新版本实现如下：
// "tlp/list/algo/All.h"
template<typename TL, template<typename T> class Pred>
struct All
{
using Result = typename Not<typename Any<TL, NegativeOf<Pred>::template Apply>::Result>::Result;
};
TLP库自身的实现中对元函数的调用都使用的是其模板格式。如果使用每个元函数封装过后的宏格式的话，实现如下：
template<typename TL, template<typename T> class Pred>
struct All
{
using Result = __not(__any(TL, __negative_of(Pred)));
};
相关的测试用例如下：
FIXTURE(TestAdvancedAlgo)
{
__func_forward_1(IsLargerThan2Bytes, __bool((sizeof(_1) > 2)));
TEST("any one of the list satisfied the given prediction")
{
ASSERT_TRUE(__any(__type_list(char, short, int), IsLargerThan2Bytes));
};
TEST("none of the list satisfied the given prediction")
{
ASSERT_FALSE(__any(__type_list(char, short), IsLargerThan2Bytes));
};
TEST("all of the list satisfied the given prediction")
{
ASSERT_TRUE(__all(__type_list(int, long), IsLargerThan2Bytes));
};
TEST("any of the type in list not satisfied the given prediction")
{
ASSERT_FALSE(__all(__type_list(int, long, short), IsLargerThan2Bytes));
};
}
上面的fixture中我们使用前面介绍过的__func_forward_1定义了一个单参元函数IsLargerThan2Bytes，它会判断入参类型的size是否大于两个字节。
接下来我们再来实现一个高阶元函数__map()，它的用法如下面的测试用例：
TEST("map the list to it's size value list")
{
__func_forward_1(TypeSize, __int(sizeof(_1)));
using List = __type_list(int, char, short, long);
using Expected = __value_list(4, 1, 2, 8);
ASSERT_EQ(__map(List, TypeSize), Expected);
};
__map()的入参需要一个list和一个类型映射元函数。它会对入参list的每个元素调用映射函数，最终将list映射成一个新的list返回。__map()可以组合使用，如下：
TEST("map the type in list to it's twice pointer type list")
{
template<typename T> struct TransToPointer { using Result = T*; };
using List = __type_list(int, const char);
using Expected = __type_list(int**, const char**);
ASSERT_EQ(__map(__map(List, TransToPointer), TransToPointer), Expected);
};
__map()的实现如下：
template<typename TL, template<typename T> class Func> struct Map;
template<template<typename T> class Func>
struct Map<NullType, Func>
{
using Result = NullType;
};
template<typename Head, typename Tail, template<typename T> class Func>
struct Map<TypeElem<Head, Tail>, Func>
{
using Result = TypeElem<typename Func<Head>::Result, typename Map<Tail, Func>::Result>;
};
#define __map(...) typename Map<__VA_ARGS__>::Result
TLP库一共实现了如下针对list的高阶元函数：
-
__any(List, Pred(T))：对List中每个元素调用Pred，如果有一个返回TrueType，则__any返回TrueType，否则返回FalseType； -
__all(List, Pred(T))：对List中每个元素调用Pred，如果有所有都返回TrueType，则__all返回TrueType，否则返回FalseType； -
__transform(List1, List2, Func(T1, T2))：遍历List1和List2，对两个list中每对元素调用Func，根据Func的返回值类型组成一共新的List返回； -
__filter(List, Pred(T))：过滤List中所有调用Pred为真得类型，组成一个新的List返回； -
__map(List, Func(T))：将List中每个元素调用Func映射成一个新的类型，返回映射后类型组成的新List； -
__fold(List, Acc, Func(T1, T2))：折叠算法；将List所有元素按照Func给的算法折叠成一个值返回，Acc是折叠启动参数； -
__sort(List, Compare(T1, T2))：将List按照传入的Compare规则进行排序，返回排序后的新List；
上述没有介绍到的List的高阶算法的实现在这里就不再详述了，感兴趣的话请直接阅读TLP的源码。TLP的“tlp/test/TestList.cpp”文件中有这些元函数的详细测试，通过测试也可以看到它们的详细用法。
最后，高阶元函数的强大之处是可以让代码在更高的抽象层次上进行复用和组合，通过更贴近领域的语义描述出操作意图。如下测试用例中，我们想要计算一组类型中大于两字节的所有类型的size之和，我们使用前面介绍的高阶元函数进行组合来实现：
TEST("calculate the total size of the types that larger than 2 bytes")
{
using List = __type_list(char, short, int, long, char*, short*, int*, long*);
ASSERT_EQ(__fold(__map(__filter(List, IsLargerThan2Bytes), TypeSize) , __int(0), Add), __int(44));
};
上述测试是在64位操作系统上的计算结果（指针、int和long都是8字节，short是4字节）。在计算中先通过__filter()在list中过滤出所有大于2字节的类型，然后通过__map()将过滤后的类型列表映射成对应的size数值列表，最后通过__fold()元函数进行累计求和。上述所有操作的抽象层次都将list作为一个整体，没有降级到针对list内部进行算法描述。
网友评论