針對list的高階算法，是允許用戶在使用時傳入別的元函數(shù)做參數(shù)的元函數(shù)。在函數(shù)式語言里對于list的高階元函數(shù)（如經(jīng)典的filter，map，fold...），可以輕松地讓用戶通過函數(shù)組合來擴展對list的操作。
下面我們先實現(xiàn)一個簡單的__any()高階元函數(shù)，它接收一個list以及一個單參元函數(shù)Pred做入?yún)ⅲㄔ撛瘮?shù)接受一個類型，返回一個BoolType類型）；__any()對list中每個元素調(diào)用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()的遞歸實現(xiàn)中，對list的頭元素調(diào)用Pred：Pred<Head>::Result，如果為真，則返回TrueType；否則對list的剩余尾list繼續(xù)調(diào)用__any()：Any<Tail, Pred>::Result>::Result；一直遞歸到空list，最后返回FalseType。
在這里我們用了元函數(shù)IfThenElse，由于它的惰性，我們可以在Pred為當前元素求值為TrueType的時候提前停止遞歸，后面的元素就不用再算了。另外也可以這樣實現(xiàn)：using Result = __bool(__value(typename Pred<Head>::Result) ? true : __value(typename Any<Tail, Pred>::Result))。這種實現(xiàn)用了三元表達式，但由于這種運行時技術缺乏惰性，所以實際上每個元素都被求值了！
接下來我們實現(xiàn)元函數(shù)__all()。它的入?yún)⒑?code>any()一樣，差別在于所有的元素應用Pred后都返回TrueType，__all()才會返回TrueType；只要有一個元素應用Pred后返回FalseType，則__all()返回FalseType。
參考了__any()的實現(xiàn)，我們輕松實現(xiàn)__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()的實現(xiàn)非常相像！事實上，我們可以借助__any()來實現(xiàn)__all()，從而消除這兩者之間的重復。
首先我們需要借助__any()計算list中是否有某一元素應用Pred后為假，如果沒有一個為假，則__all()返回真。我們知道客戶傳入給__all()的Pred是一個單參元函數(shù)，它在滿足條件后返回真。我們需要把客戶傳入的Pred轉變成另一個在滿足條件后返回假的單參元函數(shù)。于是我們實現(xiàn)了NegativeOf元函數(shù)，它是一個高階函數(shù)，接受一個返回值是BoolType的單參元函數(shù)，返回一個取反之后的單參元函數(shù)。
// 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()的新版本實現(xiàn)如下：
// "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庫自身的實現(xiàn)中對元函數(shù)的調(diào)用都使用的是其模板格式。如果使用每個元函數(shù)封裝過后的宏格式的話，實現(xiàn)如下：
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定義了一個單參元函數(shù)IsLargerThan2Bytes，它會判斷入?yún)㈩愋偷膕ize是否大于兩個字節(jié)。
接下來我們再來實現(xiàn)一個高階元函數(shù)__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()的入?yún)⑿枰粋€list和一個類型映射元函數(shù)。它會對入?yún)ist的每個元素調(diào)用映射函數(shù)，最終將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()的實現(xiàn)如下：
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庫一共實現(xiàn)了如下針對list的高階元函數(shù)：
__any(List, Pred(T))：對List中每個元素調(diào)用Pred，如果有一個返回TrueType，則__any返回TrueType，否則返回FalseType；__all(List, Pred(T))：對List中每個元素調(diào)用Pred，如果有所有都返回TrueType，則__all返回TrueType，否則返回FalseType；__transform(List1, List2, Func(T1, T2))：遍歷List1和List2，對兩個list中每對元素調(diào)用Func，根據(jù)Func的返回值類型組成一共新的List返回；__filter(List, Pred(T))：過濾List中所有調(diào)用Pred為真得類型，組成一個新的List返回；__map(List, Func(T))：將List中每個元素調(diào)用Func映射成一個新的類型，返回映射后類型組成的新List；__fold(List, Acc, Func(T1, T2))：折疊算法；將List所有元素按照Func給的算法折疊成一個值返回，Acc是折疊啟動參數(shù)；__sort(List, Compare(T1, T2))：將List按照傳入的Compare規(guī)則進行排序，返回排序后的新List；
上述沒有介紹到的List的高階算法的實現(xiàn)在這里就不再詳述了，感興趣的話請直接閱讀TLP的源碼。TLP的“tlp/test/TestList.cpp”文件中有這些元函數(shù)的詳細測試，通過測試也可以看到它們的詳細用法。
最后，高階元函數(shù)的強大之處是可以讓代碼在更高的抽象層次上進行復用和組合，通過更貼近領域的語義描述出操作意圖。如下測試用例中，我們想要計算一組類型中大于兩字節(jié)的所有類型的size之和，我們使用前面介紹的高階元函數(shù)進行組合來實現(xiàn)：
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位操作系統(tǒng)上的計算結果（指針、int和long都是8字節(jié)，short是4字節(jié)）。在計算中先通過__filter()在list中過濾出所有大于2字節(jié)的類型，然后通過__map()將過濾后的類型列表映射成對應的size數(shù)值列表，最后通過__fold()元函數(shù)進行累計求和。上述所有操作的抽象層次都將list作為一個整體，沒有降級到針對list內(nèi)部進行算法描述。
