template

Haskell はほとんど電卓代わりなのに、なぜか Haskeller にされている。好きな言語ですけれども、よく知らないのでストーカーのような。
それで、遅延評価のよいところを聞かれて、とりあえず、有名な fib を挙げる。

fib = 1: 1: (map (uncurry (+)) $ zip fib (tail fib))

それに対して、C++ の template だと自動的にmemo化されるから高速だよね、という話が、でてくる。

#include<iostream>
using namespace std;

template<int n>
class fib;

template<>
class fib<0>{
public:
  static const int x = 1;
};

template<>
class fib<1>{
public:
  static const int x = 1;
};

template<int n>
class fib{
public:
  static const int x = fib<n-1>::x + fib<n-2>::x;
};

template<int n, int m>
class pascal;

template<>
class pascal<0, 0>{
public:
  static const int x = 1;
};

template<int n>
class pascal<n, 0>{
public:
  static const int x = 1;
};

template<int m>
class pascal<0, m>{
public:
  static const int x = 1;
};

template<int n, int m>
class pascal{
public:
  static const int x = pascal<n-1,m>::x + pascal<n,m-1>::x;
};

int main()
{
  cout << fib<40>::x << endl;
  cout << pascal<10, 10>::x << endl;
  return 0;
}

じゃあ、竹内関数は、const の初期化は三項演算子で、

template<int x, int y, int z>
class tak{
public:
  static const int v = (x <= y) ? y : (tak<tak<x-1, y, z>::v, tak<y-1, z, x>::v, tak<z-1, x, y>::v>::v);

とやってみると、たとえば、tak<1, 1, 1> の定義で tak<1, 1, 1> が必要となるからエラーになる。

そういや、と思って http://d.hatena.ne.jp/shinichiro_h/20060619 を参考に書き直すと

template<int x, int y, int z, bool b>
class tak;

template<int x, int y, int z>
class tak<x, y, z, true>{
public:
  static const int v = y;
};

template<int x, int y, int z, bool b = x <= y >
class tak{
public:
  static const int v = tak<tak<x-1, y, z>::v, tak<y-1, z, x>::v, tak<z-1, x, y>::v>::v;
};

つまり、x <= y が真の時には、特殊化されたほうの template が呼ばれるから、無事済むという話でございます。
ここから特殊フォームのない lisp のようなものだと分かる。

これで、O(e^n) が memo化によって O(n^3) になるはずで、実際 time で計測してみるとそうなっている。

けど、賢いコンパイラならばやらないことやっているよね。遅延評価すれば、

let tak x y z = if x <= y then y else tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y)

で、O(n)ですよね。
おお、うまい具合に遅延評価万歳っていう話と繋がった。

まあ、それで副作用がなくて特殊フォームがない LISP では遅延評価なんて出来ないと思うのですけれども。