0, 1, 2, 3, 小圏

0（対象も射もない圏）、 1（対象が1つと恒等射のみの圏）、 2（対象が2つと、それぞれの恒等射・その間の1つの射からなる圏）、 3（対象が3つとそれぞれの恒等射、射も3つで1つの射が残り2つの射の合成である圏）

をそれぞれRustで表現していこうとしていたのですが、3をやろうとして、ちょっと面倒だな、と感じました。 0/1/2はそれぞれ別の構造体で、それぞれ別のトレイト実装を作っていたわけなのですが、3だと内容の割にコード量が増えたからです。というわけで、3以外も表現できる一般的な圏を表す構造体を作ることにしました。

#[derive(Default)]
struct SmallCat<Object, Arrow> {
    objects: Vec<Object>,
    arrows: Vec<Arrow>,
}

この機会に、ジェネリックにして、対象も射も好きな型を与えられるようにしました。こうしたのは、3を作っていて、対象や射に名前を与えたくなったからです。今まで使っていたCategoryObject/CategoryArrowというUnitな構造体では情報が足りないので、 NamedCategoryObject/NamedCategoryArrowを作り、それをSmallCatに与えましょう。ついでに型エイリアスも宣言します。

#[derive(PartialEq, Default)]
struct NamedCategoryObject(&'static str);

#[derive(PartialEq, Default)]
struct NamedCategoryArrow {
    name: &'static str,
    codomain: usize,
    domain: usize,
    equals: Vec<Vec<usize>>,
}

type SmallCat_ = SmallCat::<NamedCategoryObject, NamedCategoryArrow>;

NamedCategoryArrowは、射の名前以外にも、codomain/domain/equalsがいます。 codomain/domainがあるのは、初回に作った構造体（Category）と似ています。 equalsは、3で出てくる射の結合を表現するためのものです。

Categoryトレイトを実装します。

impl<O: PartialEq> Category for SmallCat<O, NamedCategoryArrow> {
    type Object = O;
    type Arrow = NamedCategoryArrow;

    fn domain(&self, f: &Self::Arrow) -> &Self::Object { &self.objects[f.domain] }
    fn codomain(&self, f: &Self::Arrow) -> &Self::Object { &self.objects[f.codomain] }
    fn identity(&self, o: &Self::Object) -> &Self::Arrow {
        let idx = self.objects.iter().position(|x| x == o).unwrap();
        for a in self.arrows.iter() {
            if a.codomain == idx && a.domain == idx {
                return a
            }
        }
        panic!("");
    }
    fn composition_internal<'a>(&'a self, f: &'a Self::Arrow, g: &'a Self::Arrow) -> &'a Self::Arrow {
        let f_idx = self.arrows.iter().position(|x| x == f).unwrap();
        let g_idx = self.arrows.iter().position(|x| x == g).unwrap();
        for arrow in self.arrows.iter() {
            for eq in arrow.equals.iter() {
                if eq[0] == f_idx && eq[1] == g_idx {
                    return arrow;
                }
            }
        }
        panic!("")
    }
    fn objects<'a>(&'a self) -> Box<Iterator<Item=&'a Self::Object> + 'a> {
        Box::new(self.objects.iter())
    }
    fn arrows<'a>(&'a self) -> Box<Iterator<Item=&'a Self::Arrow> + 'a> {
        Box::new(self.arrows.iter())
    }
}

対象や射を区別するのは、Vecのインデックスという仕様にしました。参照にうまくLifetimeを与えられませんでした。射はNamedCategoryArrow固定ですが、対象はジェネリックに与えられます。

これを使って3を表現したいわけですが、表記が冗長になるので、以前作ったcatマクロを改良して使いましょう。

macro_rules! cat {
    ([ $( $object:ident )* ]
     [ $( $arrow_name:ident : $codomain:ident -> $domain:ident )* ]
     [ $( $f1:ident;$f2:ident = $f3:ident )* ]) => ({
        let mut objects = vec![];
        let mut arrows = vec![];

        $(
            objects.push(NamedCategoryObject(stringify!($object)));
            let idx = objects.iter().count() - 1;
            arrows.push(NamedCategoryArrow {
                name: stringify!($object), 
                codomain: idx, 
                domain: idx, 
                equals: vec![]
            });
        )*

        let mut equals_list = vec![];
        $( equals_list.push( (stringify!($f3),
                              vec![stringify!($f1), stringify!($f2)]) ); )*

        $(
            let cod_idx = objects.iter()
                                 .position(|x| x.0 == stringify!($codomain))
                                 .unwrap();
            let dom_idx = objects.iter()
                                 .position(|x| x.0 == stringify!($domain))
                                 .unwrap();
            let mut equals = vec![];

            for eqs in equals_list.iter() {
                if eqs.0 == stringify!($arrow_name) {
                    let before_idx = arrows.iter()
                                           .position(|x| x.name == eqs.1[0])
                                           .unwrap();
                    let after_idx = arrows.iter()
                                          .position(|x| x.name == eqs.1[1])
                                          .unwrap();
                    equals.push(vec![before_idx, after_idx]);
                }
            }
            arrows.push(NamedCategoryArrow {
                name: stringify!($arrow_name),
                codomain: cod_idx,
                domain: dom_idx,
                equals: equals,
            });
        )*
        SmallCat_ { objects, arrows }
    })
}

これを使えば、3は以下のように表現できます。 3以外の小圏も同様に定義できます。

    let _small_cat = cat!(
        [X Y Z]
        [f: X -> Y
         g: Y -> Z
         h: X -> Z]
        [f;g = h]
    );

関手・自然変換

続いて、関手と自然変換もトレイトを作ってみました。

trait Functor {
    type DOM: Category;
    type COD: Category;

    fn send_objects(object: <Self::DOM as Category>::Object) -> <Self::COD as Category>::Object;
    fn send_arrows(arrow: <Self::DOM as Category>::Arrow) -> <Self::COD as Category>::Arrow;
}

trait NaturalTransformation {
    type C: Category;
    type D: Category;
    type F: Functor<DOM=Self::C, COD=Self::D>;
    type G: Functor<DOM=Self::C, COD=Self::D>;

    fn components() -> Box<Iterator<Item=<Self::D as Category>::Arrow>>;
}

比較的、定義通りに書ける感じがします。ただ、やはりそれぞれの満たすべき条件を書き表すことはできません。トレイトの実装者が満たすことになりますね。まだ何か物足りない気もしますが、具体的に作っていくことで見えてくるでしょう。

色の輪

Rustで圏論(6) 小圏・関手・自然変換

0, 1, 2, 3, 小圏

関手・自然変換