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 では遅延評価なんて出来ないと思うのですけれども。