前言
黑魔法,应用场景 :
1.实现宿生语言
2.压榨机器性能 : 表达式模板,循环展开...特别是在高性能计算领域...可以获得媲美手工展开的高效代码
3.作为实现各种库的基本组件 :Stl,Boost,标准库都大量运用了模板元技术
很多人比较排斥这个东西...一些炫技模板元代码能看得人头皮发麻...
个人觉得实用就行,工具终究是为人服务的
just enjoy it ??
推荐的资料
《C++ Templates》
《C++模板元编程》
C++11模板元入门 https://www.cnblogs.com/qicosmos/p/4480460.html
C++高质量社区 http://purecpp.org/
Part 1 实现一个基于C++的宿生Lisp方言
基本约定
建议先看看江南的博客入个门 :C++11模板元入门 https://www.cnblogs.com/qicosmos/p/4480460.html
这是一个类型的世界,首先定义三种基本类型
1.与值关联的类型 : integral_constant
2.类型的类型
3.元计算类型
当然这是一种定义风格,三种类型并无严格区别,可以相互代替...只是会带来巨大的混乱(个人经验
所以直接严格划分三种类型...就不容易在类型的世界迷失
1.integral_constant
c++11中的标准库元函数,先看源代码
template <typename T,T v>
struct integral_constant
{
using value_type = T ;
using type = integral_constant<T,v>;
static constexpr T value = v;
constexpr operator value_type()
{
return value;
}
};
看几个栗子
using true_type = integral_constant<bool, true>;
using ten = integral_constant<int,10>;
ten::value_type val = 10;
cout << ten::type::type::type::value << endl;
cout << ten() << endl;
(typedef和using指令等效,using指令更直观,元表达式一复杂,采用using指令更清晰
可以观察到 integral_constant作为一个元函数,可以生成一个新类型,新类型绑定一个值和该值的类型
并且特别的是 :integral_constant::type指向类型本身,这一点的用处比较大,后面还会说,先观察到即可
类型2.类型的类型
特征十分明显 :结构体为空 (建议元编程的时候全部采用struct,struct与class没什么区别,仅仅默认访问权限、继承全部为public
template<typename a,typename b>
struct sum : integral_constant<typename a::value_type,a::value + b::value>
{};
int main()
{
using ten = integral_constant<int,10>;
using five = integral_constant<int,5>;
cout << sum<ten,five>::value << endl;
return 0;
}
继续观察样例,可以看到sum完成了两个数的加法
观察点1 : 第二行 typename a::value_type,为什么要加奇怪的typename?因为c++模板的特殊性质,编译器在看到a::value_type的时候并不能分析出来a::value_type是成员变量还是类型,所以需要显式说明
观察点2 : sum的结构体为空,所以sum是"类型的类型",但是,sum却完成一个元函数行为 :计算两数和。既然"类型的类型"可以进行元计算,为什么我们还需要划分出一个元计算类型?
答案是"类型的类型"可以进行元计算,但是完成不了复杂的元计算,因为在"类型的类型"做元计算的时候,声明不了新类型,导致只能实现一句代码的元计算,做不了复杂计算
类型3.元计算类型
特征也十分明显:没有继承行为,结构体内部充满一些using指令,用来做元计算
template<typename a,typename b>
struct sum
{
using result = integral_constant<typename a::value_type,a::value + b::value>;
};
int main()
{
using ten = integral_constant<int,10>;
using five = integral_constant<int,5>;
cout << sum<ten,five>::result() << endl;
return 0;
}
类似于c/c++中的函数,元函数也有"函数名" : sum,"函数参数" :typename a,typename b,"返回值" result
观察点1.我们约定,元函数的"返回值"全部定义为result
观察点2.cout << sum<ten,five>::result() << endl; result是类型,我们可以通过类似 cout << int() << endl;的形式来打印元信息,重载一下流输出即可,后面还会涉及
观察点3.我们约定,元函数不继承任何类型
lisp方言基本类型与操作
1.基本类型,如整形,字符串
2.null类型
3.pair
4.元函数car,cdr
有一个非常庞大的证明和实践体系证明上述简单类型/操作能实现非常复杂的计算,是图灵完备的
1.基本类型
整形
template<int val>
struct number : integral_constant<int,val> {};
字符串 : 因为c++11不滋滋模板字符串,所以不能直接定义(因为 "string"的类型是const cahr* const 两个相同的字符串常量拥有不同的常量地址,模板不能识别这种
因为本次模板元实战主要在模板,我采用了一种取巧的办法 :把字符串压进unsigned long long int(简记为ull,可以滋滋长度在8及以下的任何字符串
constexpr ull stoull(const char *p,ull now = 0)
{
return *p == 0 ? now : stoull(p + 1,now * 255 + *p);
}
template<ull val>
struct string : public integral_constant<ull,val> {};
#define str(x) string<stoull(x)>
这样就可以很方便的用str("string")来产生字符串类型
浮点 : 因为c++的历史原因,模板也不滋滋浮点常量,取巧的办法是定义一个pair<int,int> 即"int.int",与主题关系不大,故不再赘述
2.null类型
为什么要把null单独说明呢...因为空类型相当重要,设计良好的空类型可以很好的简化很多设计
struct null : integral_constant<ull,stoull("null")> {};
特别是,空类型要保证null::type == null,这样才能契合进元计算的整体框架
也可以看到integral_constant的重要性,integral_constant是一个很重要的基础设施
3.pair类型
和c++中的pair类似,只不过first -> car,second -> cdr(仅仅是遵循lisp方言惯例,没什么特别含义
template<typename T,typename U>
struct pair
{
using car = T;
using cdr = U;
};
4.元函数car,cdr
没啥好说的,注意我们预定result为元函数返回值
template<typename T>
struct car
{
using result = typename T::car;
};
template<typename T>
struct cdr
{
using result = typename T::cdr;
};
有些用过lisp的人可能要说了,你怎么没有实现一个cons?这个直接pair<type,type>即可,没必要重复...毕竟我们是在做宿生语言,适当的修改使得宿生更契合宿主,没必要严格实现
实现一个异类字典
先看效果
using table = list<pair<str("a"),str("value_a")>,
pair<str("b"),integral_constant<bool,0>>,
pair<number<10>,str("x")>
>;
cout << table_find<table,str("12")>::result() << endl; // null
cout << table_find<table,str("a")>::result() << endl; // value_A
cout << table_find<table,number<10>>::result() << endl; // x
看起来很复杂?我们分三步实现
1.实现list
2.实现table_find
3.实现输出
1.实现list
template<typename ...T>
struct list;
template<typename T,typename ...arg>
struct list<T,arg...> : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};
不会模板参数包的建议百度
首先
template<typename ...T>
struct list;
声明了一个list
template<typename T,typename ...arg>
struct list<T,arg...> : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};
然后两个模板偏特化,看起来挺清晰的,就是list<a,b,c> = pair<a,pair<b,pair<c,null>>>;
就没了...参数包用起来qs很好用
因为list对类型没有啥要求,所以直接实现了一个异类字典
2.实现table_find
template<typename list,typename key>
struct table_find
{
using check = integral_constant<bool,is_same<typename car<typename car<list>::result>::result,key>::value>;
using if_found = typename cdr<typename car<list>::result>::result;
using if_not_found = typename table_find<typename cdr<list>::result,key>::result;
using result = typename conditional<check::value,if_found,if_not_found>::type;
};
template<typename key>
struct table_find<null,key>
{
using result = null;
};
首先观察第二个偏特化,找遍字典还没找到,那就无了,返回null
然后看第一个
首先看结尾处的
using result = typename conditional<check::value,if_found,if_not_found>::type;
conditional是c++11模板元函数,就是实现一个if-else的逻辑 ::type就是拿到元计算结果(这与我们定义::result作为元函数计算结果不同)
注意typename告诉编译器这是个类型,不然会报错
using check = integral_constant<bool,is_same<typename car<typename car<list>::result>::result,key>::value>;
check是判断条件,is_same也是标准库元函数,判断两个类型是不是一样
因为字典本质上是个pair<a,pair<b,pair<c,null>>>用car,cdr把对应部分提取出来比较即可,(car,cdr为了方便可以直接写作宏,car(type)这样。我为了使得代码直观易懂,没有写
using if_found = typename cdr<typename car<list>::result>::result;
using if_not_found = typename table_find<typename cdr<list>::result,key>::result;
没找到就递归调用table_find即可,因为我们对元函数定义的约定,这对于熟悉递归的人非常直观
另外,我们可以直观观察到
值(类型)只能被创造,不能被摧毁
这句话相当重要,这是函数式编程语言的特色,我编写代码的时候忽然领悟了这句话的精髓...这是函数式编程风格的一个重要特色,一块基石
还可以观察到,我们通过using指令创造新类型,相当于在元函数里面声明新变量,元函数通过约定,变得直观易懂
运算结果通过result返回
...tabld_find就完成了,仍有一些注意点
因为模板元的特性,建议增量开发模板元程序...不然报错一报若干行...初学者很容易懵逼...
偏特化,参数包基本操作,不会的多练练
实现输出
下面结尾c++输出风格,如果你喜欢printf()这样的,原理一样
cout << integral_constant<int,10>() << endl;
cout << table_find<table,str("12")>::result() << endl; // null
首先integral_constant里面重载了类型转换运算符,编译器会自动转化,我们只需要写自己类型的输出格式即可
template<ull val>
ostream& operator << (ostream& os,string<val>)
{
std::string ret;
ull now = val;
while (now)
ret.push_back(now % 255),
now /= 255;
reverse(ret.begin(),ret.end());
return os << ret;
}
ostream& operator << (ostream& os,null)
{
return os << "null";
}
template<typename T,typename U>
ostream& operator << (ostream& os,pair<T,U>)
{
return os << "(" << T() << "," << U() <<")";
}
注意ostream& operator << (ostream& os,string);第二个没参数,只有类型
因为信息都在类型里面,参数写不写无所谓,你写的话,编译器自动会优化掉
调用的时候func(type()),编译器就能演绎类型了,func(type)这样是不行滴,因为违背了c\c++参数传递规则
就是函数重载 + 模板特化,大多数输出就这三种特化方式...都在这了...比较简单,照猫画虎即可
list<number<10>,str("22")> : [10,22]
list的输出比较麻烦一点,因为要控制输出格式 + 参数包,代码里有,原理没区别,不赘述了
小结
至此,我们实现了一个字典...难者不会,会者不难...写熟练之后还是挺简单的
小练习,实现一个length的元函数,计算list,字典的元素个数
多动手,练习是必须滴
template<typename T>
struct length
{
using result = number<1 + length<typename cdr<T>::result>::result::value>;
};
template<>
struct length<null>
{
using result = number<0>;
};
实现一个归并排序
1.实现merge : 按顺序合并两个list得到新的list
2.实现split : 切割一个list为长度差不超过1的两个list
3.实现sort_merge : 合并两个有序list为一个有序list
4.实现sort : 排序一个list
1.实现merge : 按顺序合并两个list得到新的list
这里需要一个技巧 : 模板的模板参数,不会的百度一下
模板的模板参数,在这里的作用是拿到list内部的类型,常规手段拿不到
其实模板的模板参数类似于函数的实参演绎,只不过挪到了编译期,作用依旧是推导类型
template<typename list1,typename list2>
struct merge {};
template<typename ...args1,template<typename ...args1> class list1,
typename ...args2,template<typename ...args2> class list2
>
struct merge<list1<args1...>,list2<args2...>>
{
using result = list<args1...,args2...>;
};
template<typename ...args1,template<typename ...args1> class list1>
struct merge<list1<args1...>,list<null>>
{
using result = list<args1...>;
};
template<typename ...args2,template<typename ...args2> class list2>
struct merge<list2<null>,list2<args2...>>
{
using result = list<args2...>;
};
template<>
struct merge<list<null>,list<null>>
{
using result = list<null>;
};
结构就是一个声明 + 4个偏特化...后面三个偏特化很简单,重点看第一个偏特化
template<typename ...args1,template<typename ...args1> class list1,
typename ...args2,template<typename ...args2> class list2
>
struct merge<list1<args1...>,list2<args2...>>
{
using result = list<args1...,args2...>;
};
这里的merge其实可以通过lisp形式完成...(偷个懒顺便练习一下模板的模板参数...后面还会用lisp的风格写元函数的
元函数体里面很直观,就是拿到两个list的参数,合并到一个新的list就完了
重点在于模板的模板参数,因为是偏特化,所以template中的顺序无所谓,编译器会推导出正确的类型
template<typename ...args1> class list1因为模板类才有模板的模板参数,c++要求在这里写一个class...(比较憨,但是你得写...以后的标准可能改进这一点...
merge就没了...(偷懒成功,大雾
2.实现split : 切割一个list为长度差不超过1的两个list
split的实现就很lisp了,先康代码
template<typename T,typename first = list<null>,typename second = list<null>>
struct split
{
using car = typename car<T>::result;
using cdr = typename cdr<T>::result;
using new_first = typename merge<first,list<car>>::result;
using new_second = typename merge<second,list<car>>::result;
using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
typename split<cdr,new_first,second>::result,
typename split<cdr,first,new_second>::result
>::type;
};
template<typename first,typename second>
struct split<null,first,second>
{
using result = pair<first,second>;
};
老样子,先看简单的第二个特化...
split概念上是一个带参数的dfs(T,first,second),运算结果存在参数里面,T为空的时候运算结束,返回参数作为计算结果
再看
template<typename T,typename first = list<null>,typename second = list<null>>
struct split
{
using car = typename car<T>::result;
using cdr = typename cdr<T>::result;
using new_first = typename merge<first,list<car>>::result;
using new_second = typename merge<second,list<car>>::result;
using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
typename split<cdr,new_first,second>::result,
typename split<cdr,first,new_second>::result
>::type;
};
首先,first,second默认为list<null>
。模板也可以设默认type。运算结果是一个pair<list<>,list<>>
注意偏特化不能有默认参数
cout << split<a>::result() << endl;
思路很直观,比较一下两个参数first,second的长短,给短的添加当前元素
这里有一个阴间坑 : 如果你split实现的不对,比如 [1,2] -> [1,2],[] 也就是没有正确切割...split会编译通过,但是在某些计算中模板会报一大推错...
老样子,conditional实现一下,给短的添加一个元素即可...注意我们不能销毁、改写一个已经存在的类型...必须生成新的类型,代码很直观...
其实这样子的元函数已经和普通函数差别不大了...这得益于我们的约定 : 严格区分三种类型,从而带来实现上的方便
3.实现sort_merge : 合并两个有序list为一个有序list
template<typename list1,typename list2,typename ret = list<null>>
struct sort_merge
{
using car1 = typename car<list1>::result;
using car2 = typename car<list2>::result;
using cdr1 = typename cdr<list1>::result;
using cdr2 = typename cdr<list2>::result;
using ret1 = typename merge<ret,list<car1>>::result;
using ret2 = typename merge<ret,list<car2>>::result;
using result = typename conditional<car1::value <= car2::value,
typename sort_merge<cdr1,list2,ret1>::result,
typename sort_merge<list1,cdr2,ret2>::result
>::type;
};
template<typename list1,typename ret>
struct sort_merge<list1,null,ret>
{
using result = typename merge<ret,list1>::result;
};
template<typename list2,typename ret>
struct sort_merge<null,list2,ret>
{
using result = typename merge<ret,list2>::result;
};
老样子,先看简单的偏特化:)
和slpit类似,计算结果带在参数ret里面
只有一个list的时候,直接和ret合并返回,注意合并顺序
template<typename list1,typename list2,typename ret = list<null>>
struct sort_merge
{
using car1 = typename car<list1>::result;
using car2 = typename car<list2>::result;
using cdr1 = typename cdr<list1>::result;
using cdr2 = typename cdr<list2>::result;
using ret1 = typename merge<ret,list<car1>>::result;
using ret2 = typename merge<ret,list<car2>>::result;
using result = typename conditional<car1::value <= car2::value,
typename sort_merge<cdr1,list2,ret1>::result,
typename sort_merge<list1,cdr2,ret2>::result
>::type;
};
明显cdr,car写成宏更好用(大雾
很直观了...这里再强调一下,为什么,类型的类型也可以计算,但是我们不用
类型的类型通过继承做元计算的时候,没办法声明新类型
这导致了它的计算能力大大下降...直接写元函数,简单直观,没必要用一些诡异的技巧折磨自己
sort_merge就没了
4.实现sort : 排序一个list
万事俱备...轻松愉快
template<typename T>
struct mysort
{
using split_res = typename split<T>::result;
using left = typename car<split_res>::result;
using right = typename cdr<split_res>::result;
using left_ans = typename mysort<left>::result;
using right_ans = typename mysort<right>::result;
using result = typename sort_merge<left_ans,right_ans>::result;
};
template<typename T>
struct mysort<list<T>>
{
using result = list<T>;
};
是8是很直观...某种意义上编译期排序并不比普通排序难...来个栗子

因为函数式编程语言在语法简洁性上有巨大优势
lisp 2.0
约定
为了写出这样的阳间代码 : (是不是比lisp 1.0 阳间了很多)
#define split(type) typename Split<type>::result
#define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
template<typename T,typename first = list<null>,typename second = list<null>>
struct Split
{
using new_first = merge(first,list<car(T)>);
using new_second = merge(second,list<car(T)>);
using len_first = length(new_first);
using len_second = length(new_second);
using result = typename conditional<len_first::value < len_second::value,
_split(cdr(T),new_first,second),
_split(cdr(T),first,new_second)
>::type;
};
template<typename first,typename second>
struct Split<null,first,second>
{
using result = pair<first,second>;
};
我们约定 :
1.所有的元函数首字母大写,并且每个元函数都有一个对应的宏,宏名仅首字母小写 如#define split(type) typename Split<type>::result
2.所有的类型的类型,改称为元类型 所有的类型无需搭配宏,比如pair<type,type>
遵循约定,我们就能写出非常阳间的代码
特例
using len_first = length(new_first);
using len_second = length(new_second);
using result = typename conditional<len_first::value < len_second::value,
typename Split<cdr(T),new_first,second>::result,
typename Split<cdr(T),first,new_second>::result
>::type;
使用integral_constant的value时,我们需要增加一个间接类型,因为宏里面和编译器约定了typename,就不能再使用::value这个成员
解决办法就是using指令加个间接层
-----------------------分割线----------------------以下均不是博客内容---------------------------------
代码,可能托管到github更好一点,后面再弄
/*
---- Author : XDU_mzb
---- lisp 2.0
*/
#include <bits/stdc++.h>
namespace DSL
{
using std::endl;
using std::cout;
using std::integral_constant;
using std::conditional;
using std::is_same;
using std::ostream;
using ll = long long int;
using ull = unsigned long long int;
constexpr ull stoull(const char *p,ull now = 0)
{
return *p == 0 ? now : stoull(p + 1,now * 255 + *p);
}
template<ull val>
struct string : public integral_constant<ull,val> {};
#define str(x) string<stoull(x)>
template<typename T,typename U>
struct pair
{
using car = T;
using cdr = U;
};
template<typename T>
struct Car
{
using result = typename T::car;
};
#define car(x) typename Car<x>::result
template<typename T>
struct Cdr
{
using result = typename T::cdr;
};
#define cdr(x) typename Cdr<x>::result
template<ll val>
struct number : integral_constant<ll,val> {};
struct null : str("null") {};
template<typename T,typename ...arg>
struct list : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};
#define table_find(table,value) typename Table_find<table,value>::result
template<typename list,typename key>
struct Table_find
{
using if_found = cdr(car(list));
using if_not_found = table_find(cdr(list),key);
using result = typename conditional<is_same<car(car(list)),key>::value,if_found,if_not_found>::type;
};
template<typename key>
struct Table_find<null,key>
{
using result = null;
};
template<typename T>
struct typeinfo
{
static std::string name()
{
return std::string("unknow_type::") + std::string("std::typeid::name::") + typeid(T).name();
}
};
#define CREATE_NAME(type,type_name) template<> struct typeinfo< type > { static std::string name() { return type_name; } }
CREATE_NAME(void,"void");
CREATE_NAME(long long int,"ll");
CREATE_NAME(null,"null");
CREATE_NAME(unsigned long long int,"ull");
CREATE_NAME(short,"short");
CREATE_NAME(int,"int");
CREATE_NAME(std::string,"std::string");
CREATE_NAME(bool,"bool");
CREATE_NAME(double,"double");
CREATE_NAME(float,"float");
template<ull val>
struct typeinfo<string<val>>
{
static std::string name()
{
return "string";
}
};
template<ll val>
struct typeinfo<number<val>>
{
static std::string name()
{
return "number";
}
};
template<typename T,T val>
struct typeinfo<integral_constant<T,val>>
{
static std::string name()
{
return "const_value::" + typeinfo<T>::name();
}
};
template<typename T,typename U>
struct typeinfo<pair<T,U>>
{
static std::string name()
{
return std::string("pair<") + std::string(typeinfo<T>::name()) + std::string(",") + std::string(typeinfo<U>::name()) + std::string(">");
}
};
template<typename ...args>
struct typeinfo<list<args...>>
{
static std::string name()
{
return std::string("[") + help(list<args...>()) + std::string("]");
}
template<typename T,typename ...args2>
static std::string help(list<T,args2...> r)
{
return typeinfo<T>::name() + _help(list<args2...>());
}
template<typename T>
static std::string help(list<T>)
{
return typeinfo<T>::name();
}
template<typename T,typename ...args3>
static std::string _help(list<T,args3...>)
{
return "," + typeinfo<T>::name() + _help(list<args3...>());
}
template<typename T>
static std::string _help(list<T>)
{
return "," + typeinfo<T>::name();
}
};
#undef CREATE_NAME
#define length(type) typename Length<type>::result
template<typename T>
struct Length
{
using len = length(cdr(T));
using result = number<1 + len::value>;
};
template<>
struct Length<null>
{
using result = number<0>;
};
template<ull val>
ostream& operator << (ostream& os,string<val>)
{
std::string ret;
ull now = val;
while (now)
ret.push_back(now % 255),
now /= 255;
reverse(ret.begin(),ret.end());
return os << ret;
}
ostream& operator << (ostream& os,null)
{
return os << "null";
}
template<typename T,typename U>
ostream& operator << (ostream& os,pair<T,U>)
{
return os << "(" << T() << "," << U() <<")";
}
template<typename T>
ostream& _print(ostream& os,list<T>)
{
return os << "," << T();
}
template<typename T,typename ...args>
ostream& _print(ostream& os,list<T,args...>)
{
cout << "," << T();
_print(os,list<args...>());
return os;
}
template<typename T,typename ...args>
ostream& print(ostream& os,list<T,args...>)
{
cout << T();
_print(os,list<args...>());
return os;
}
template<typename T>
ostream& print(ostream& os,list<T>)
{
cout << T();
return os;
}
template<typename ...args>
ostream& operator << (ostream& os,list<args...>)
{
os << "[";
print(os,list<args...>());
os << "]";
return os;
}
#define merge(typea,typeb) typename Merge<typea,typeb>::result
template<typename list1,typename list2>
struct Merge {};
template<typename ...args1,template<typename ...args1> class list1,
typename ...args2,template<typename ...args2> class list2
>
struct Merge<list1<args1...>,list2<args2...>>
{
using result = list<args1...,args2...>;
};
template<typename ...args1,template<typename ...args1> class list1>
struct Merge<list1<args1...>,list<null>>
{
using result = list<args1...>;
};
template<typename ...args2,template<typename ...args2> class list2>
struct Merge<list2<null>,list2<args2...>>
{
using result = list<args2...>;
};
template<>
struct Merge<list<null>,list<null>>
{
using result = list<null>;
};
#define sort_merge(typea,typeb) typename Sort_merge<typea,typeb>::result
#define _sort_merge(typea,typeb,typec) typename Sort_merge<typea,typeb,typec>::result
template<typename list1,typename list2,typename ret = list<null>>
struct Sort_merge
{
using car1 = car(list1);
using car2 = car(list2);
using cdr1 = cdr(list1);
using cdr2 = cdr(list2);
using ret1 = merge(ret,list<car1>);
using ret2 = merge(ret,list<car2>);
using result = typename conditional<car1::value <= car2::value,
_sort_merge(cdr1,list2,ret1),
_sort_merge(list1,cdr2,ret2)
>::type;
};
template<typename list1,typename ret>
struct Sort_merge<list1,null,ret>
{
using result = merge(ret,list1);
};
template<typename list2,typename ret>
struct Sort_merge<null,list2,ret>
{
using result = merge(ret,list2);
};
#define split(type) typename Split<type>::result
#define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
template<typename T,typename first = list<null>,typename second = list<null>>
struct Split
{
using new_first = merge(first,list<car(T)>);
using new_second = merge(second,list<car(T)>);
using len_first = length(new_first);
using len_second = length(new_second);
using result = typename conditional<len_first::value < len_second::value,
_split(cdr(T),new_first,second),
_split(cdr(T),first,new_second)
>::type;
};
template<typename first,typename second>
struct Split<null,first,second>
{
using result = pair<first,second>;
};
#define sort(type) typename Sort<type>::result
template<typename T>
struct Sort
{
using left = car(split(T));
using right = cdr(split(T));
using result = sort_merge(sort(left),sort(right));
};
template<typename T>
struct Sort<list<T>>
{
using result = list<T>;
};
int main()
{
using table = list<pair<str("a"),str("value_a")>,
pair<str("b"),integral_constant<bool,0>>,
pair<number<10>,str("x")>
>;
cout << typeinfo<integral_constant<bool,false>>::name() << endl;
cout << integral_constant<int,10>() << endl;
cout << length(table)() << endl;
cout << table_find(table,str("12"))() << endl; // null
cout << table_find(table,str("a"))() << endl; // value_A
cout << table_find(table,number<10>)() << endl; // x
using l = list<null,number<10>,str("200")>;
cout << null() << endl;
cout << l() << endl;
using a = list<number<10>,number<-1>,number<-100>,number<123>,number<-50>>;
using b = sort(a);
cout << "a : " << a() << endl;
cout << "b : " << b() << endl;
return 0;
}
#undef str
#undef null
}
int main()
{
DSL::main();
return 0;
}