Rustで圏論(3) 圏はトレイトでは？

前回の話

前回、同型かどうかを判断するコードの中に間違いがあるという話を書きました。 中心となる処理は以下です。

    fn is_isomorphism(&self, object1: &str, object2: &str) -> bool {
        self.has_arrow(object1, object2) && self.has_arrow(object2, object1)
    }

与えられた2つの対象でf: A->Bとg: B->Aの射が存在していれば、同型である。 と書いてあるように見えるんですけど、これだと全然定義通りじゃなかったですね。すいません。 f;g = 1A かつ g;f = 1Bじゃないとダメです。そもそも、射の合成も恒等射もないですし。

そもそも、圏はstructじゃなくてtraitなのでは

話題が変わってしまいますが、当初はstructでCategoryを定義したものの、これだとあんまりしっくりきません。 「圏というもの」が存在する、というよりはいろんなものが「圏と見なせる」というケースが多い気がするためです。 というわけで、structではなくtraitで実装し直してみました。今度は圏の定義に忠実に。

use std::cmp::PartialEq;

trait Category {
    type Object: PartialEq;
    type Arrow: PartialEq;

    fn domain(&self, f: &Self::Arrow) -> Self::Object;
    fn codomain(&self, f: &Self::Arrow) -> Self::Object;
    fn identity(&self, a: Self::Object) -> Self::Arrow;
    fn composition(&self, f: Self::Arrow, g: Self::Arrow) -> Option<Self::Arrow> {
        if self.codomain(&f) != self.domain(&g) {
            None
        } else {
            Some(self.composition_internal(&f, &g))
        }
    }
    fn composition_internal(&self, f: &Self::Arrow, g: &Self::Arrow) -> Self::Arrow;
    fn ci(&self, f: &Self::Arrow, g: &Self::Arrow) -> Self::Arrow {
        self.composition_internal(f, g)
    }

    fn objects() -> HashSet<Self::Object>;
    fn arrows() -> HashSet<Self::Arrow>;

    fn associativity(&self, f: Self::Arrow, g: Self::Arrow, k: Self::Arrow) -> bool {
        self.ci(&self.ci(&f, &g), &k) == self.ci(&f, &self.ci(&g, &k))
    }
    fn unit_law_domain(&self, o: Self::Object, f: Self::Arrow) -> bool {
        self.ci(&self.identity(o), &f) == f
    }
    fn unit_law_codmain(&self, o: Self::Object, f: Self::Arrow) -> bool {
        self.ci(&f, &self.identity(o)) == f
    }
}

下の3つは公理なんですが、証明系の言語ではないので、定義したものの使いどころがわからない。 traitをimplementする側が保証しないといけないわけです。Haskellの型クラスもそうですね。 具体例も徐々に書いていきましょう。