用Haskell写的快排:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (p:xs) = left ++ p:right
where
left = qsort $ filter (<p) xs
right = qsort $ filter (>=p) xs
用C++模板写的快排:
template<class T>
struct qsort;
template<>
struct qsort<null> : null {};
template<class p, class xs>
struct qsort<list<p, xs> > {
typedef typename qsort<typename filter<less<p>, xs>::type>::type left;
typedef typename qsort<typename filter<notless<p>, xs>::type>::type right;
typedef typename concat<left, list<p, right> >::type type;
};
不要理会那些晦涩的语法, 凭直觉去看就够了.
记得刚刚接触STL的时候感觉头文件functional是个很鸡肋的东西. 好好的”+”不写, 偏偏要整个plus出来, 即使是把它跟for_each组合起来, 我也没看出什么特别吸引人的地方.
一年前刚刚接触boost的时候感觉bind很神奇, 特别是在发现js中的匿名函数的写法之后更是感觉bind来的正是时候.
不知不觉地, 当bind嵌套起来, 往往代码就通不过编译了, 每每看到一层层缩进的bind时总是会头皮一阵发麻. 即使是boost::lambda也没让我感觉好到哪里去, 凡是遇到函数组合的时候, 代码就变得令人晦解起来. 那似乎是第一次, 我对boost感觉有点反感.
于是我就抱着”吐着吐着就习惯了”的心理慢慢接受了C++的这个语法上的缺陷. 具体说来是什么样的缺陷呢? 那时的理解就是少了匿名函数这种漂亮的语法.
等到这个学期做软件课程设计(做一个简单的DBMS)的时候, 我心血来潮用了boost::spirit来做SQL的语法分析器, 这一做肯定折了我几年阳寿, 那个编译时几百行的错误把终端都给刷满了, 最后没办法只得把错误信息输出到文件里去慢慢挑错…
期间有个东西我很在意, 就是相关子查询的写法. spirit::qi的抽象语法树是不好提取出来的, 但是相关子查询却要求枚举外层的记录, 然后多次遍历内层的抽象语法树. 我的解决办法就是把一个boost::function作为子查询下属的多个非终结符的综合属性, 这一做可不得了, 那个bind嵌套的是一层又一层, 一发不可收拾.
上面大概算是说了一通废话, 没有用过boost的同学可能要在心里暗骂我了…
于是在做完那个简陋的DBMS之后不久, 也不知道具体是哪一天, 可能是某日又用到functional这个头文件的缘故, 我突然对boost文档里多次出现的”functional”这个字眼感兴趣起来. 之前接触模板元编程的时候也多次看到说模板元编程是”函数式”的, 大概是一切均是函数的意思. 由此导致的直接结果就是没有了”变量”这个概念.
函数式编程大概就是这样进入我的视野的.
第一次看到Haskell的快排代码时我被震撼了(), 它就像是算法最原始的一段英文描述, 简洁, 直白, 流畅.
在看过几篇Haskell教程之后, 再回头看boost, 看元编程…
Aha!
我无法用语言很好的描述出这种兴奋的情绪, 无法清楚地描述出它们之间的联系. 我知道我看到的仅仅是冰山一角, 但这已经足以让我惊喜万分.
既然无法用语言描述, 那么就用代码来说话吧. 今天花了一晚上时间, 几乎是照着上述那段Haskell代码一句一句翻译成C++的template. 其间借用了boost::mpl中的一些基础的元函数写法, 比如外覆器和元函数转发什么的.
首先把int和bool外覆器写好:
template<int n>
struct int_ {
typedef int_ type;
static const int value = n;
};
template<bool b>
struct bool_ {
typedef bool_ type;
static const bool value = b;
};
typedef bool_<true> true_;
typedef bool_<false> false_;
然后是对应于Haskell中的list的定义, 一个list可以递归地定义为首元素和尾部list的串联, 像这样:
template<class x, class xs>
struct list {
typedef list type;
};
边界条件是一个空list, 此时递归定义不再适用, 那么就定义一个空list:
struct null {
typedef null type;
};
对于++, 我们可以用一个concat函数来代替, 利用list的递归定义, 有如下Haskell代码:
concat' :: [a] -> [a] -> [a] concat' [] xs = xs concat' (x:xs) ys = x : concat' xs ys
相应的, 在C++中有如下声明:
template<class xs, class ys> struct concat;
其函数体可以这样写:
// x:xs ++ ys
template<class x, class xs, class ys>
struct concat<list<x, xs>, ys> : list<x, typename concat<xs, ys>::type> {};
concat的边界条件是左操作数为空, 此时cancat的递归定义不再适用:
// [] ++ xs
template<class xs>
struct concat<null, xs> : xs {};
filter在Haskell里可以这样写:
filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) = if p x then x : (filter p xs) else r
这里出现了条件语句, 用模板偏特化可以轻松实现:
template<class b, class T, class F>
struct select : T {};
template<class T, class F>
struct select<false_, T, F> : F {};
然后把filter的代码翻译过来, 注意边界条件仍然是空list:
template<class p, class T>
struct filter;
template<class p>
struct filter<p, null> : null {};
template<class p, class x, class xs>
struct filter<p, list<x, xs> > : select<
typename p::template apply<x>::type,
list<x, typename filter<p, xs>::type>,
filter<p, xs>
> {};
剩下的就是把它们组合到一起, 就有了最一开始的那段C++代码…
注意到那个less和notless其实是很难看的, 因为我不想用占位符把代码搞得复杂了, 就写成了一个元函数类, 像是这样:
template<class rhs>
struct less{
template<class lhs>
struct apply : bool_<(lhs::value < rhs::value)> {};
};
template<class rhs>
struct notless{
template<class lhs>
struct apply : bool_<(lhs::value >= rhs::value)> {};
};
最后定义一个用来打印list的仿函数, 其定义仍然是递归的:
template<class T>
struct output;
template<>
struct output<null> {
void operator ()() const {}
};
template<class x, class xs>
struct output<list<x, xs> > {
void operator ()() const {
std::cout << x::value << std::endl;
output<xs>()();
}
};
测试程序用了一些宏来简化代码. 有时候, 不得不承认…用宏总比附加的预处理程序好用…
int main() {
#define L(a, b) list<int_<a>, b>
#define L0 null
#define L1(a) L(a, L0)
#define L2(a, b) L(a, L1(b))
#define L3(a, b, c) L(a, L2(b, c))
#define L4(a, b, c, d) L(a, L3(b, c, d))
#define L5(a, b, c, d, e) L(a, L4(b, c, d, e))
#define L6(a, b, c, d, e, f) L(a, L5(b, c, d, e, f))
#define L7(a, b, c, d, e, f, g) L(a, L6(b, c, d, e, f, g))
typedef qsort<L7(5, 4, 2, 1, 1, 7, 6)>::type result;
output<result>()();
return 0;
}
完整代码在这里.
灵感来自: http://accu.org/index.php/journals/1422
Post a Comment