最小不動点と再帰関数定義関数

http://www.hyuki.com/t/200508.html#i20050827064837
http://www.kmonos.net/wlog/52.php#_0308050827
を見て。
ruby で書くのはあまりにも簡単なので、書きにくそうな C++ に挑戦。

#include <iostream>
#include <boost/bind.hpp>
#include <boost/function.hpp>

using namespace std;
using namespace boost;

typedef function< int( int )> func_t;

int _fib_maker( func_t f, int x )
{
	return x<=1 ? 1 : f(x-1)+f(x-2);
}

typedef function<func_t ( func_t )> maker_t;
func_t fib_maker( func_t f )
{
	return bind( _fib_maker, f, _1 );
}

int call( func_t * f, int x )
{
	return (*f)(x);
}

void fix( maker_t g, func_t & f )
{
	func_t x = bind( call, &f, _1 );
	f = g(x);
}

void test()
{
	func_t fib;
	fix( fib_maker, fib );
	for( int i=0 ; i<10 ; ++i ){
		cout << fib(i) << ", ";
	}
}

いろいろ不満はあるが、とりあえずこんな感じで。

lambda を使う気にはならなかったので、_fib_maker が fib_maker とは別な関数になっている。かっこわるいけど、lambda を使うよりはましかと思って。
ゴミ集めがないので、上記の call 関数のようなものが必要になってくるのもかっこわるい。これは回避方法を思いついていない。
int→int に限定しているのもかっこわるいが、 template で書くと読みにくくなるので今回は int 限定で。
何よりも。

func_t fib = fix( fib_maker );

と、書けなかったのがかっこわるい。クラスを書けば書けないことはなさそうだけど、ソースの量がだいぶ増えそうなので考えるのをやめた。

まあでも。実装できたから満足ではある。

ここまでできれば メモ化も簡単だがメモ領域をメモ化関数の外に置くか、メモ化クラスにするか、どっちかにする必要がありそう。それとも。bind の中に隠せるのかな??

書いていて思ったのは。
bind と function、すごい便利。

＃以下、9/2 追記:
書いてすぐ寝たんだが、起きる前に気がついた。
fib が fib 自身のアドレスを利用しているので、fib をコピーしてからコピー元を削除すると、削除済みポインタの参照が発生してしまう。
コピー禁止にする必要がある。あるいは、クラスを書けばなんとかなるかも。

＃以下、9/3 追記:
boost::bind も boost::function も使わないバージョンを http://d.hatena.ne.jp/Nabetani/20050902/p1
に書いた。
C言語版とruby版を http://d.hatena.ne.jp/Nabetani/20050903/p1 に書いた。