関数プログラミング楽しい

最近アキラさん（id:faith_and_brave）からいろいろ本を借りて読んでるのですが、その中でも

関数プログラミング

この本がすごく面白い。

foldr とか map とか、関数合成でいろいろ作っていく様がふつくしすぎる。みんな言語で最初に覚えるべきは関数型系の言語なんじゃないかと思ってしまうぐらい。
ちょっと何かに書いてみたい！と思ったのですが、自分が使えそうな関数型言語というと C++ のテンプレートしか知らないので、C++0x の Variadic Template の練習がてらに foldr, concat, reverse, map, filter をでっちあげてみました。

#include <tuple>

using namespace std;

template<bool>
struct bool_ { };
typedef bool_<true> true_;
typedef bool_<false> false_;

// bool→α
template<class Cond, class Then, class Else>
struct if_;

template<class Then, class Else>
struct if_<true_, Then, Else> { typedef Then type; };
template<class Then, class Else>
struct if_<false_, Then, Else> { typedef Else type; };

// (α→β→β)→β→[α]→β
template<template<class, class> class F, class Init, class List>
struct foldr;

template<template<class, class> class F, class Init>
struct foldr<F, Init, tuple<> >
{
    typedef Init type;
};

template<template<class, class> class F, class Init, class Head, class... Tail>
struct foldr<F, Init, tuple<Head, Tail...> >
{
    typedef typename F<Head, typename foldr<F, Init, tuple<Tail...>>::type>::type type;
};

// [α]→[α]→[α]
template<class L1, class L2>
struct binary_concat;

template<class... S1, class... S2>
struct binary_concat<tuple<S1...>, tuple<S2...>>
{
    typedef tuple<S1..., S2...> type;
};

// [[α]] → [α]
template<class LL>
struct concat
{
    typedef typename foldr<binary_concat, tuple<>, LL>::type type;
};

// α→[α]→[α]
template<class A, class L>
struct reverse_functor
{
    typedef typename binary_concat<L, tuple<A>>::type type;
};

// [α]→[α]
template<class L>
struct reverse
{
    typedef typename foldr<reverse_functor, tuple<>, L>::type type;
};

// (α→β)→[α]→[β]
template<template<class> class F, class S>
struct map;

template<template<class> class F, class... S>
struct map<F, tuple<S...>>
{
    typedef tuple<typename F<S>::type...> type;
};

// (α→bool)→[α]→[α]
template<template<class> class P, class S>
struct filter
{
    // α→[α]
    template<class A>
    struct box
    {
        typedef typename if_<typename P<A>::type, tuple<A>, tuple<>>::type type;
    };
    typedef typename concat<typename map<box, S>::type>::type type;
};

template<int N>
struct int_ { };
typedef int_<0> _0i;
typedef int_<1> _1i;
typedef int_<2> _2i;
typedef int_<3> _3i;
typedef int_<4> _4i;

template<class A>
struct add1;

template<int N>
struct add1<int_<N>>
{
    typedef int_<N + 1> type;
};

template<class A>
struct less4;

template<int N>
struct less4<int_<N>>
{
    typedef bool_<(N < 4)> type;
};

#include <type_traits>

int main()
{
    typedef concat<tuple<tuple<_1i, _2i>, tuple<>, tuple<_3i, _2i>>>::type concat_result;
    static_assert(is_same<concat_result, tuple<_1i, _2i, _3i, _2i>>::value, "failed");
    typedef reverse<concat_result>::type reverse_result;
    static_assert(is_same<reverse_result, tuple<_2i, _3i, _2i, _1i>>::value, "failed");
    typedef map<add1, reverse_result>::type map_result;
    static_assert(is_same<map_result, tuple<_3i, _4i, _3i, _2i>>::value, "failed");
    typedef filter<less4, map_result>::type filter_result;
    static_assert(is_same<filter_result, tuple<_3i, _3i, _2i>>::value, "failed");
}

なんかあまり Variadic Template 使ってない気がする……。