SCIP in C++11 ― 2.1.3節その2

Church数とモノイド：問題2.6

えらいぐちゃぐちゃしていて、最初はなんじゃこりゃと思ったが、

よく見ると巡回群、というか巡回モノイドの演算をやっているように見えるな。

zeroが返す恒等手続きが単位元f⁰で、

Church数が引数にとった手続きfの作用を何回繰り返すかで、

自然数と同型な集合を表現しているみたい。

つまり問題1.43のrepeatedの内部手続きを抽象化しているっぽい。

repeatedを実装しているときに「これって群？」て思ったが、

基本その方向でいいようだ。

置き換えモデルで計算しても(((add-1 zero) f) x)=(f x)だな。

それならばadd-1の定義が、fⁿからfⁿ⁺¹を返していることを、

帰納的に定義していると見るのはたやすい。

単位元としての恒等写像から帰納的定義をスタートしているので見づらいだけか。

fが巡回モノイドの生成元で、xがfが作用する空間の元。

fの逆写像は定義されてないからモノイドだけど、

fに逆写像があれば、巡回群<f>の作用を完全に抽象的に表現できる。

すっげー！これ使えそう。

fだけでなくいくつもの、逆写像を持つ写像を引数に取るようにして工夫すれば、

巡回群だけでなく、対称群とかの有限生成の群をいろいろ表現できるんじゃね？

もうちょっと頑張れば、置換とか座標変換とか自由にやりまくりじゃん。

Church数自体を2次元配列にするとかも考えられるか。

前の問題でショックを受けてちょっと凹んだ自分に、一服の清涼剤。

addは問題1.9の考え方かと最初思ったが、

写像が等しいということを表現する仕方がわからないので、断念。

というわけで単純に問題1.42のcomposeを使う・・・とやってみたら、

そっか、単純にChurch数をcomposeで合成したら積になるじゃん。

先に積が定義できてしまったｗ

composeは問題1.42のと同じなので略。

----

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