2012-08-04

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


Church数とモノイド:問題2.6

えらいぐちゃぐちゃしていて、最初はなんじゃこりゃと思ったが、
よく見ると巡回群、というか巡回モノイドの演算をやっているように見えるな。
zeroが返す恒等手続きが単位元f0で、
Church数が引数にとった手続きfの作用を何回繰り返すかで、
自然数と同型な集合を表現しているみたい。
つまり問題1.43repeatedの内部手続きを抽象化しているっぽい。
repeatedを実装しているときに「これって群?」て思ったが、
基本その方向でいいようだ。

置き換えモデルで計算しても(((add-1 zero) f) x)=(f x)だな。
それならばadd-1の定義が、fnからfn+1を返していることを、
帰納的に定義していると見るのはたやすい。
単位元としての恒等写像から帰納的定義をスタートしているので見づらいだけか。

fが巡回モノイドの生成元で、xfが作用する空間の元。
fの逆写像は定義されてないからモノイドだけど、
fに逆写像があれば、巡回群<f>の作用を完全に抽象的に表現できる。
すっげー!これ使えそう。

fだけでなくいくつもの、逆写像を持つ写像を引数に取るようにして工夫すれば、
巡回群だけでなく、対称群とかの有限生成の群をいろいろ表現できるんじゃね?
もうちょっと頑張れば、置換とか座標変換とか自由にやりまくりじゃん。
Church数自体を2次元配列にするとかも考えられるか。
前の問題でショックを受けてちょっと凹んだ自分に、一服の清涼剤。

addは問題1.9の考え方かと最初思ったが、
写像が等しいということを表現する仕方がわからないので、断念。
というわけで単純に問題1.42composeを使う・・・とやってみたら、
そっか、単純にChurch数をcomposeで合成したら積になるじゃん。
先に積が定義できてしまったw

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

0 件のコメント :

コメントを投稿