テンプレートでフィボナッチ数列

『Modern C++ Design』 (ISBN:4894714353)を読んでC++のテンプレートが面白かったのでちょっと遊んでみた。

#include <iostream>

template <class T, class U>
struct Typelist
{
    typedef T Car;
    typedef U Cdr;
};

class NullType;

#define TYPELIST_1(T1) \
    Typelist<T1, NullType>

#define TYPELIST_2(T1, T2) \
    Typelist<T1, TYPELIST_1(T2) >

#define TYPELIST_3(T1, T2, T3) \
    Typelist<T1, TYPELIST_2(T2, T3) >

#define TYPELIST_4(T1, T2, T3, T4) \
    Typelist<T1, TYPELIST_3(T2, T3, T4) >

#define TYPELIST_5(T1, T2, T3, T4, T5) \
    Typelist<T1, TYPELIST_4(T2, T3, T4, T5) >

#define TYPELIST_6(T1, T2, T3, T4, T5, T6) \
    Typelist<T1, TYPELIST_5(T2, T3, T4, T5, T6) >

#define TYPELIST_7(T1, T2, T3, T4, T5, T6, T7) \
    Typelist<T1, TYPELIST_6(T2, T3, T4, T5, T6, T7) >

#define TYPELIST_8(T1, T2, T3, T4, T5, T6, T7, T8) \
    Typelist<T1, TYPELIST_7(T2, T3, T4, T5, T6, T7, T8) >

#define TYPELIST_9(T1, T2, T3, T4, T5, T6, T7, T8, T9) \
    Typelist<T1, TYPELIST_8(T2, T3, T4, T5, T6, T7, T8, T9) >

/* Fib */
template <class TList>
struct Fib;

template <>
struct Fib< NullType >
{
    enum { value = 0 };
};

template <class X>
struct Fib< TYPELIST_1(X) >
{
    enum { value = 1 };
};

template < class X, class Y, class Z >
struct Fib< Typelist< X, Typelist<Y, Z> > >
{
    enum { value = Fib< Typelist<Y, Z> >::value + Fib<Z>::value };
};

int main(int argc, char *argv[])
{
    int n1 = Fib< TYPELIST_1(int) >::value;
    std::cout << "Fibonacci(1) = " << n1 << std::endl;

    int n2 = Fib< TYPELIST_2(int, int) >::value;
    std::cout << "Fibonacci(2) = " << n2 << std::endl;

    int n3 = Fib< TYPELIST_3(int, int, int) >::value;
    std::cout << "Fibonacci(3) = " << n3 << std::endl;

    int n4 = Fib< TYPELIST_4(int, int, int, int) >::value;
    std::cout << "Fibonacci(4) = " << n4 << std::endl;

    int n5 = Fib< TYPELIST_5(int, int, int, int, int) >::value;
    std::cout << "Fibonacci(5) = " << n5 << std::endl;

    int n6 = Fib< TYPELIST_6(int, int, int, int, int, int) >::value;
    std::cout << "Fibonacci(6) = " << n6 << std::endl;

    int n7 = Fib< TYPELIST_7(int, int, int, int, int, int, int) >::value;
    std::cout << "Fibonacci(7) = " << n7 << std::endl;

    int n8 = Fib< TYPELIST_8(int, int, int, int, int, int, int, int) >::value;
    std::cout << "Fibonacci(8) = " << n8 << std::endl;

    int n9 = Fib< TYPELIST_9(int, int, int, int, int, int, int, int, int) >::value;
    std::cout << "Fibonacci(9) = " << n9 << std::endl;

    return 0;
}
  • 実行結果
% ./a.out
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34

ポイントは、全ての計算がコンパイル時に行われるということ。この性質はLispのマクロと同じ。特に、型推論が一種のパターンマッチングになっている点はSchemeの「健全な」マクロとかなり近いものを感じる。
…で、本当はテンプレートでたらいまわしてみたかったんだけど、さすがにこれまでテンプレートを使ったことがなくていきなりは無理だった。