一応C++でもやってみましたが

http://twitter.com/zick_minoh/status/6223526156

2日近くも掛かってしまいました。ひーん。Haskell版をただ書き直しただけです。

templateとかtypenameとかすぐ忘れてしまいますね。なんでやねん的なのが多かったです。
あと結局あちこちにapplyを書く事になってしまったし、っていうか普通にBoostを使いましょう。Boostです！！

#include <typeinfo>
#include <cxxabi.h>
#include <iostream>

char* demangle(const char *demangle) {
    int status;
    return abi::__cxa_demangle(demangle, 0, 0, &status);
}

struct True{typedef True type;};
struct False{typedef False type;};

struct BoolEq{
    template<typename L,typename R>
    struct apply{};
};
template<>
struct BoolEq::apply<True,True>{
    typedef True type;
};
template<>
struct BoolEq::apply<False,False>{
    typedef True type;
};
template<>
struct BoolEq::apply<True,False>{
    typedef False type;
};
template<>
struct BoolEq::apply<False,True>{
    typedef False type;
};

template<typename Cond,typename Then,typename Else>
struct IfThenElse{};

template<typename Then,typename Else>
struct IfThenElse<True,Then,Else>
{
    typedef typename Then::type type;
};
template<typename Then,typename Else>
struct IfThenElse<False,Then,Else>
{
    typedef typename Else::type type;
};

struct And
{
    template<typename P,typename Q>
    struct apply{};
};
template<>
struct And::apply<True,True>{typedef True type;};
template<>
struct And::apply<True,False>{typedef False type;};
template<>
struct And::apply<False,True>{typedef False type;};
template<>
struct And::apply<False,False>{typedef False type;};

struct Or
{
    template<typename P,typename Q>
    struct apply{};
};
template<>
struct Or::apply<True,True>{typedef True type;};
template<>
struct Or::apply<True,False>{typedef True type;};
template<>
struct Or::apply<False,True>{typedef True type;};
template<>
struct Or::apply<False,False>{typedef False type;};

struct Zero{typedef Zero type;};
template<typename V>struct Succ{
    typedef Succ<typename V::type> type;
};

typedef Succ<Zero> One;
typedef Succ<One> Two;
typedef Succ<Two> Three;
typedef Succ<Three> Four;

struct Add{
    template<typename L,typename R>
    struct apply{};
};
template<>
struct Add::apply<Zero,Zero>{
    typedef Zero type;
};
template<typename R>
struct Add::apply<Zero,R>{
    typedef typename R::type type;
};
template<typename L,typename R>
struct Add::apply<Succ<L>,R>{
    typedef typename Succ<Add::template apply<L,R> >::type type;
};

struct NatEq{
    template<typename L,typename R>
    struct apply{};
};
template<>
struct NatEq::apply<Zero,Zero>{
    typedef True type;
};
template<typename A>
struct NatEq::apply<Succ<A>,Zero>{
    typedef False type;
};
template<typename B>
struct NatEq::apply<Zero,Succ<B> >{
    typedef False type;
};
template<typename A,typename B>
struct NatEq::apply<Succ<A>,Succ<B> >{
    typedef typename NatEq::template apply<A,B>::type type;
};

struct Less{
    template<typename L,typename R>
    struct apply{};
};
template<>
struct Less::apply<Zero,Zero>{
    typedef False type;
};
template<typename A>
struct Less::apply<Succ<A>,Zero>{
    typedef False type;
};
template<typename B>
struct Less::apply<Zero,Succ<B> >{
    typedef True type;
};
template<typename A,typename B>
struct Less::apply<Succ<A>,Succ<B> >{
    typedef typename Less::template apply<A,B>::type type;
};

struct Nil{typedef Nil type;};

template<typename H,typename T>
struct Cons{
    typedef Cons<typename H::type,typename T::type> type;
};

struct cons{
    template<typename H,typename T>
    struct apply{
	typedef typename Cons<H,T>::type type;
    };
};

struct Foldr{
    template<typename Unary,typename Init,typename List>
    struct apply{
    };
};
template<typename Binary,typename Init>
struct Foldr::apply<Binary,Init,Nil>{
    typedef Init type;
};
template<typename Binary,typename Init,typename H,typename T>
struct Foldr::apply<Binary,Init,Cons<H,T> >{
    typedef typename Binary::template apply<H,typename Foldr::template apply<Binary,Init,T>::type>::type type;
};

struct Append{
    template<typename L,typename R>
    struct apply{
	typedef typename Foldr::template apply<cons,R,L>::type type;
    };
};

struct Concat{
    template<typename ListOfList>
    struct apply{
	typedef typename Foldr::template apply<Append,Nil,ListOfList>::type type;
    };
};

struct Length{
    template<typename List>
    struct apply{
	//typedef typename Foldr::template apply<Lambda<_1,_2,Succ<_2> > >::type type;
    };
};
template<>
struct Length::apply<Nil>{
    typedef Zero type;
};
template<typename H,typename T>
struct Length::apply<Cons<H,T> >{
    typedef typename Succ<typename Length::template apply<T>::type>::type type;
};

template<typename Binary,typename Arg1>
struct Partial{
    struct Unary{
	template<typename ARG2>
	struct apply{
	    typedef typename Binary::template apply<typename Arg1::type,typename ARG2::type>::type type;
	};
    };
};

struct Filter{
    template<typename Unary,typename List>
    struct apply{};
};
template<typename Unary>
struct Filter::apply<Unary,Nil>{
    typedef Nil type;
};
template<typename Unary,typename H,typename T>
struct Filter::apply<Unary,Cons<H,T> >{
    typedef typename Unary::template apply<H>::type cond;
    typedef typename Filter::template apply<Unary,T>::type rest;
    typedef typename IfThenElse<cond,Cons<H,rest>,rest>::type type;
};

struct Map{
    template<typename Unary,typename List>
    struct apply{};
};
template<typename Unary>
struct Map::apply<Unary,Nil>{
    typedef Nil type;
};
template<typename Unary,typename H,typename T>
struct Map::apply<Unary,Cons<H,T> >{
    typedef typename Unary::template apply<H>::type H_;
    typedef typename Map::template apply<Unary,T>::type T_;
    typedef Cons<H_,T_> type;
};

struct Insert{
    template<typename Elem,typename List>
    struct apply{
    };
};
template<typename Elem>
struct Insert::apply<Elem,Nil>{
    typedef Cons<Cons<Elem,Nil>,Nil> type;
};
template<typename Elem,typename H,typename T>
struct Insert::apply<Elem,Cons<H,T> >{
    typedef typename Cons<Elem,Cons<H,T> >::type A;
    typedef typename Insert::template apply<Elem,T>::type B;

    typedef typename Partial<cons,H>::Unary C;
    typedef typename Map::template apply<C,B>::type D;
    
    typedef typename Cons<A,D>::type type;
};

struct Perm{
    template<typename List>
    struct apply{};
};
template<>
struct Perm::apply<Nil>{
    typedef Cons<Nil,Nil> type;
};
template<typename H,typename T>
struct Perm::apply<Cons<H,T> >{
    typedef typename Concat::template apply<typename Map::template apply<typename Partial<Insert,H>::Unary,typename Perm::template apply<T>::type>::type>::type type;
};

template<typename A>
struct Kotori{
    typedef typename NatEq::template apply<typename A::type,One>::type type;
};
template<typename A,typename B>
struct Naru{
    typedef typename Less::template apply<typename A::type,typename B::type>::type type;
};
template<typename A>
struct Suzu{
    typedef typename NatEq::template apply<typename A::type,One>::type left;
    typedef typename NatEq::template apply<typename A::type,Two>::type right;
    typedef typename Or::template apply<left,right>::type type;
};
template<typename A>
struct Ayu{
    typedef typename NatEq::template apply<typename A::type,One>::type left;
    typedef typename NatEq::template apply<typename A::type,Two>::type right;
    typedef typename Or::template apply<left,right>::type type;
};
    
struct Kawaii{
    template<typename List>
    struct apply{};
};

template<typename A,typename B,typename C,typename D>
struct Kawaii::apply<Cons<A,Cons<B,Cons<C,Cons<D,Nil> > > > >{
    typedef typename Kotori<A>::type kotori;
    typedef typename Naru<B,C>::type naru;
    typedef typename Suzu<C>::type suzu;
    typedef typename Ayu<D>::type ayu;
    typedef Cons<kotori,Cons<naru,Cons<suzu,Cons<ayu,Nil> > > > type;
};

struct Judge{
    template<typename List>
    struct apply{};
};

template<typename A,typename B,typename C,typename D>
struct Judge::apply<Cons<A,Cons<B,Cons<C,Cons<D,Nil> > > > >{
    typedef typename Kawaii::template apply<Cons<A,Cons<B,Cons<C,Cons<D,Nil> > > > >::type kawaii;
    typedef typename Filter::template apply<Partial<BoolEq,False>::Unary,kawaii>::type filterd;
    typedef typename Length::template apply<filterd>::type length;
    typedef typename NatEq::template apply<length,One>::type type;
};

typedef Cons<One,Cons<Two,Cons<Three,Cons<Four,Nil> > > > RankSet;
typedef Cons<One,Cons<Three,Cons<Four,Cons<Two,Nil> > > > Ans;
typedef Perm::apply<RankSet>::type All;
typedef Length::apply<All>::type Len;
typedef Filter::apply<Judge,All>::type Compute;

int main()
{
    Compute compute;
    std::cout << demangle(typeid(compute).name()) << std::endl;
}

==>
./a.out 
Cons<Cons<Succ<Zero>, Cons<Succ<Succ<Succ<Zero> > >, Cons<Succ<Succ<Succ<Succ<Zero> > > >, Cons<Succ<Succ<Zero> >, Nil> > > >, Nil>

「計算する」という目的に関してだけならば、GHCに比べて圧倒的に速い。
あと、型のレベルでの制約(Context)はHaskellだとType Classで付けられますが、C++だとConcept(は全然知らないのですが)がなんか使えないというかなんからしいので、なんかなんか・・・。

適当に作ったので、一貫性無く引数(的な所)で"::type"をしてますが適当なのでそれも適当です。

参考

デマングルに関しては
http://0xcc.net/blog/archives/000095.html
をそのまま使いました。