Church数とモノイド:問題2.6
えらいぐちゃぐちゃしていて、最初はなんじゃこりゃと思ったが、
よく見ると巡回群、というか巡回モノイドの演算をやっているように見えるな。
zeroが返す恒等手続きが単位元f0で、
Church数が引数にとった手続きfの作用を何回繰り返すかで、
自然数と同型な集合を表現しているみたい。
repeatedを実装しているときに「これって群?」て思ったが、
基本その方向でいいようだ。
置き換えモデルで計算しても(((add-1 zero) f)
x)=(f x)だな。
それならばadd-1の定義が、fnからfn+1を返していることを、
帰納的に定義していると見るのはたやすい。
単位元としての恒等写像から帰納的定義をスタートしているので見づらいだけか。
fが巡回モノイドの生成元で、xがfが作用する空間の元。
fの逆写像は定義されてないからモノイドだけど、
fに逆写像があれば、巡回群<f>の作用を完全に抽象的に表現できる。
すっげー!これ使えそう。
fだけでなくいくつもの、逆写像を持つ写像を引数に取るようにして工夫すれば、
巡回群だけでなく、対称群とかの有限生成の群をいろいろ表現できるんじゃね?
もうちょっと頑張れば、置換とか座標変換とか自由にやりまくりじゃん。
Church数自体を2次元配列にするとかも考えられるか。
addは問題1.9の考え方かと最初思ったが、
写像が等しいということを表現する仕方がわからないので、断念。
そっか、単純にChurch数をcomposeで合成したら積になるじゃん。
先に積が定義できてしまったw
----
typedef
int G_SetElement;
typedef
function<G_SetElement(G_SetElement)> MonoidAction;
typedef
function<MonoidAction(MonoidAction)> ChurchNumeral;
const
G_SetElement identity(const G_SetElement& x)
{return(x);}
const
ChurchNumeral zero=[](const MonoidAction& f)
{return(identity);};
const
ChurchNumeral add1(const ChurchNumeral& n)
{
return([n](const MonoidAction& f){
return([n,f](const int x){
return(f(n(f)(x)));
});
});
}
const
ChurchNumeral add
(const
ChurchNumeral& m,const ChurchNumeral& n)
{
return([m,n](const MonoidAction f)
{return(compose(m(f),n(f)));});
}
const
ChurchNumeral mul
(const
ChurchNumeral& m,const ChurchNumeral& n)
{
return(compose(m,n));
}
//---------abstraction
barrier---------
int
main(int argc, char** argv)
{
const ChurchNumeral one(add1(zero));
const ChurchNumeral two(add1(one));
const MonoidAction increment=
[](const G_SetElement x){return(x+1);};
cout<<"++0="<<one(increment)(0)<<endl;
cout<<"++1="<<two(increment)(0)<<endl;
const ChurchNumeral oneAlt=
[](const MonoidAction&
f){return(f);};
const ChurchNumeral
three(add1(add1(oneAlt)));
cout<<"++(++another1)="<<three(increment)(0)<<endl;
cout<<"3+2="<<(add(three,two))(increment)(0)<<endl;
cout<<"3*2="<<(mul(three,two))(increment)(0)<<endl;
cout<<"0*1="<<(mul(zero,one))(increment)(0)<<endl;
cout<<"1*0="<<(mul(one,zero))(increment)(0)<<endl;
return(0);
}
----
出力
----
++0=1
++1=2
++(++another1)=3
3+2=5
3*2=6
0*1=0
1*0=0
0 件のコメント :
コメントを投稿