針對(duì)list的高階算法，是允許用戶在使用時(shí)傳入別的元函數(shù)做參數(shù)的元函數(shù)掀潮。在函數(shù)式語(yǔ)言里對(duì)于list的高階元函數(shù)（如經(jīng)典的filter菇夸，map，fold...）仪吧，可以輕松地讓用戶通過(guò)函數(shù)組合來(lái)擴(kuò)展對(duì)list的操作庄新。
下面我們先實(shí)現(xiàn)一個(gè)簡(jiǎn)單的__any()高階元函數(shù)，它接收一個(gè)list以及一個(gè)單參元函數(shù)Pred做入?yún)ⅲㄔ撛瘮?shù)接受一個(gè)類(lèi)型薯鼠，返回一個(gè)BoolType類(lèi)型）择诈；__any()對(duì)list中每個(gè)元素調(diào)用Pred，如果Pred對(duì)某一個(gè)元素返回TrueType出皇，則__any()返回TrueType羞芍；否則如果Pred對(duì)所有的元素都返回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()的遞歸實(shí)現(xiàn)中荷科，對(duì)list的頭元素調(diào)用Pred：Pred<Head>::Result，如果為真纱注，則返回TrueType畏浆；否則對(duì)list的剩余尾list繼續(xù)調(diào)用__any()：Any<Tail, Pred>::Result>::Result；一直遞歸到空l(shuí)ist狞贱，最后返回FalseType刻获。
在這里我們用了元函數(shù)IfThenElse，由于它的惰性瞎嬉，我們可以在Pred為當(dāng)前元素求值為T(mén)rueType的時(shí)候提前停止遞歸蝎毡，后面的元素就不用再算了。另外也可以這樣實(shí)現(xiàn)：using Result = __bool(__value(typename Pred<Head>::Result) ? true : __value(typename Any<Tail, Pred>::Result))氧枣。這種實(shí)現(xiàn)用了三元表達(dá)式沐兵，但由于這種運(yùn)行時(shí)技術(shù)缺乏惰性，所以實(shí)際上每個(gè)元素都被求值了便监！
接下來(lái)我們實(shí)現(xiàn)元函數(shù)__all()痒筒。它的入?yún)⒑?code>any()一樣，差別在于所有的元素應(yīng)用Pred后都返回TrueType茬贵，__all()才會(huì)返回TrueType簿透；只要有一個(gè)元素應(yīng)用Pred后返回FalseType，則__all()返回FalseType解藻。
參考了__any()的實(shí)現(xiàn)老充，我們輕松實(shí)現(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()的實(shí)現(xiàn)非常相像螟左！事實(shí)上啡浊，我們可以借助__any()來(lái)實(shí)現(xiàn)__all()觅够，從而消除這兩者之間的重復(fù)。
首先我們需要借助__any()計(jì)算list中是否有某一元素應(yīng)用Pred后為假巷嚣，如果沒(méi)有一個(gè)為假喘先，則__all()返回真。我們知道客戶傳入給__all()的Pred是一個(gè)單參元函數(shù)廷粒，它在滿足條件后返回真窘拯。我們需要把客戶傳入的Pred轉(zhuǎn)變成另一個(gè)在滿足條件后返回假的單參元函數(shù)。于是我們實(shí)現(xiàn)了NegativeOf元函數(shù)坝茎，它是一個(gè)高階函數(shù)涤姊，接受一個(gè)返回值是BoolType的單參元函數(shù)，返回一個(gè)取反之后的單參元函數(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()的新版本實(shí)現(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庫(kù)自身的實(shí)現(xiàn)中對(duì)元函數(shù)的調(diào)用都使用的是其模板格式思喊。如果使用每個(gè)元函數(shù)封裝過(guò)后的宏格式的話，實(shí)現(xiàn)如下：
template<typename TL, template<typename T> class Pred>
struct All
{
using Result = __not(__any(TL, __negative_of(Pred)));
};
相關(guān)的測(cè)試用例如下：
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中我們使用前面介紹過(guò)的__func_forward_1定義了一個(gè)單參元函數(shù)IsLargerThan2Bytes次酌，它會(huì)判斷入?yún)㈩?lèi)型的size是否大于兩個(gè)字節(jié)恨课。
接下來(lái)我們?cè)賮?lái)實(shí)現(xiàn)一個(gè)高階元函數(shù)__map()，它的用法如下面的測(cè)試用例：
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)⑿枰粋€(gè)list和一個(gè)類(lèi)型映射元函數(shù)岳服。它會(huì)對(duì)入?yún)ist的每個(gè)元素調(diào)用映射函數(shù)庄呈，最終將list映射成一個(gè)新的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()的實(shí)現(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庫(kù)一共實(shí)現(xiàn)了如下針對(duì)list的高階元函數(shù)：
__any(List, Pred(T))：對(duì)List中每個(gè)元素調(diào)用Pred，如果有一個(gè)返回TrueType斜纪，則__any返回TrueType贫母，否則返回FalseType；__all(List, Pred(T))：對(duì)List中每個(gè)元素調(diào)用Pred盒刚，如果有所有都返回TrueType腺劣，則__all返回TrueType，否則返回FalseType因块；__transform(List1, List2, Func(T1, T2))：遍歷List1和List2橘原，對(duì)兩個(gè)list中每對(duì)元素調(diào)用Func，根據(jù)Func的返回值類(lèi)型組成一共新的List返回涡上；__filter(List, Pred(T))：過(guò)濾List中所有調(diào)用Pred為真得類(lèi)型趾断，組成一個(gè)新的List返回；__map(List, Func(T))：將List中每個(gè)元素調(diào)用Func映射成一個(gè)新的類(lèi)型吩愧，返回映射后類(lèi)型組成的新List芋酌；__fold(List, Acc, Func(T1, T2))：折疊算法；將List所有元素按照Func給的算法折疊成一個(gè)值返回雁佳，Acc是折疊啟動(dòng)參數(shù)脐帝；__sort(List, Compare(T1, T2))：將List按照傳入的Compare規(guī)則進(jìn)行排序同云，返回排序后的新List；
上述沒(méi)有介紹到的List的高階算法的實(shí)現(xiàn)在這里就不再詳述了堵腹，感興趣的話請(qǐng)直接閱讀TLP的源碼炸站。TLP的“tlp/test/TestList.cpp”文件中有這些元函數(shù)的詳細(xì)測(cè)試，通過(guò)測(cè)試也可以看到它們的詳細(xì)用法疚顷。
最后旱易，高階元函數(shù)的強(qiáng)大之處是可以讓代碼在更高的抽象層次上進(jìn)行復(fù)用和組合，通過(guò)更貼近領(lǐng)域的語(yǔ)義描述出操作意圖荡含。如下測(cè)試用例中咒唆，我們想要計(jì)算一組類(lèi)型中大于兩字節(jié)的所有類(lèi)型的size之和，我們使用前面介紹的高階元函數(shù)進(jìn)行組合來(lái)實(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));
};
上述測(cè)試是在64位操作系統(tǒng)上的計(jì)算結(jié)果（指針释液、int和long都是8字節(jié)全释，short是4字節(jié)）。在計(jì)算中先通過(guò)__filter()在list中過(guò)濾出所有大于2字節(jié)的類(lèi)型误债，然后通過(guò)__map()將過(guò)濾后的類(lèi)型列表映射成對(duì)應(yīng)的size數(shù)值列表浸船，最后通過(guò)__fold()元函數(shù)進(jìn)行累計(jì)求和。上述所有操作的抽象層次都將list作為一個(gè)整體寝蹈，沒(méi)有降級(jí)到針對(duì)list內(nèi)部進(jìn)行算法描述李命。
