Boost.MPLでエラトステネスの篩を実装してみた

『C++テンプレートメタプログラミング』を読み始めたので、Boost.MPLでエラトステネスの篩を実装してみました。

コード

Pythonで書くところの

def sieve(ns):
    return [ns[0]] + sieve([n for n in ns if n % ns[0]]) if ns else []

を、そのまま(?)C++のコードに落とします。

#include <iostream>
#include <boost/mpl/copy_if.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/front_inserter.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/list.hpp>
#include <boost/mpl/modulus.hpp>
#include <boost/mpl/not_equal_to.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/range_c.hpp>

namespace mpl = boost::mpl;
using namespace boost::mpl::placeholders;

template<class Seq, bool Empty = mpl::empty<Seq>::value>
struct sieve
  : mpl::push_front<
        typename sieve<
            typename mpl::reverse_copy_if<
                Seq,
                mpl::not_equal_to<
                    mpl::modulus<_, typename mpl::front<Seq>::type>,
                    mpl::int_<0>
                >,
                mpl::front_inserter<mpl::list<> >
            >::type
        >::type,
        typename mpl::front<Seq>::type
    >
{};

template<class Seq>
struct sieve<Seq, true> : mpl::list<>
{};

typedef sieve<mpl::range_c<int, 2, 100> >::type primes;

struct value_printer {
    template<class T>
    void operator()(T x) const
    {
        std::cout << x << ' ';
    }
};

int main()
{
    mpl::for_each<primes>(value_printer());
}

出力

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

VC10+Boost1.45.0とideone(GCC4.3.4+Boost 1.39.0)で動作確認。

ちょっと解説

テンプレートクラスsieveが整数列を篩にかけるメタ関数です。
列が空であるかどうかによる分岐は、bool型のテンプレート引数Emptyと部分的特殊化によって行います。2つのテンプレートの相互再帰で実装することもできますが(http://ideone.com/yud4V)、その場合は再帰の深さが倍になります。
reverse_copy_ifをfilter_viewに変えれば、Haskell的な遅延評価版もできるのですが、コンパイルが耐えられないくらい遅いのでやめました。