HaskellからC++への移植

相変わらず仰々しいタイトルだが例の如く内容はしょぼいのでその辺は気にしないように。
そもそも私がHaskellを勉強し始めたのはC++のTemplateをより有効に使えるようにする為だったりする。まあ現在のところまだまだ勉強不足なのであまり有効に出来てないがorz

お題目として、組み合わせを求めるプログラムを書く。英語でいうとcombinationですね。数式だと

です。定義は確か

だったと思うがこの式だとやりにくいので以下の公式を使います。

なんでこんな公式覚えているの？とツッコミを入れられそうだが、パスカルの三角形を知っていれば普通に出てくる公式だったりする。
まあとにかく、まずはHaskellでちゃっちゃと書いてみます。

combination n m | 0 == m    = 1 
                | n == m    = 1 
                | otherwise = ( combination (n-1) (m-1) ) + ( combination (n-1) m )

本当はパターンマッチングがよかったんだけどまあいいや(謎)
n

int Combination( unsigned int N, unsigned int M ){
	if( M == 0 ){ return 1; }
	if( M == N ){ return 1; }
	return Combination( N-1, M-1 ) + Combination( N-1, M );
}

特に何も言うことはないと思います。普通に再帰関数ですね。これもn

template< unsigned int N, unsigned int M >
struct Combination{
	enum{ V = Combination< N-1, M-1 >::V + Combination< N-1, M >::V };
};

template< unsigned int N >
struct Combination< N, N >{
	enum{ V = 1 };
};

template< unsigned int N >
struct Combination< N, 0 >{
	enum{ V = 1 };
};

テンプレートメタプログラミングの参考書に載ってそうな例ですがまあそのまんまです。関数型言語的にはこちらの方が移植として正しいんじゃないかな？かな？と根拠もなく思ったりします。

もっと本格的にメタメタしてみたい今日この頃でした。