圏論とかモナドについて② - ただのブログです

群からMonoidまで適当に書きましたが、Scalazでたくさん出てくるモナドさんと戦うにはもう一つ別の方向から、いくつかの概念を知る必要があります。
マサカリが飛び交う戦場、圏論です。

圏について

対象と射の２種類の集合であること
射の合成演算・が存在
・の結合則が成り立つこと
単位元が存在すること（※恒等射）

対象と射の２種類の集合であること

これを説明するため、まず対象と射という物を簡単に紹介します。

対象とは

文字通りですが、対象とは対象です。
対象が型であったり、モノイドであったりします。色々な物が対象になります。
今はあまり難しく考えないでください。
対象という言葉に深く捕われず、読んでいくうちに感覚的にどういったことを対象といっているのか見てもらえればよいです。

射について

写像、函数、変換、作用素と同じような同義語みたいな物を思っておけばOKです。
厳密には射と写像が意味しているものは別ですが、とりあえず今は同義語みたいな物として思っておいてください。

射については本来の英語表記に戻します。
射＝arrowです。
arrowつまり「→」。->をアロー演算子といいますよね。
->は→ですよね。
arrowですね！

f：x →　yは xはyに対応するよーってことで、射とは対応付けのことです。
対応関係を表わすものです。単射とか全射とか「射」を含む言葉を一つくらいは知ってますよね？
なんとなくイメージつきましたか…？

以上を踏まえて例を適当に挙げます。

ex)対象が型で射がメソッド

対象の集合はInt型とString型とします。
射はtoStringとか、toIntとかいっぱいあるので省略します。

f:Int　→ String

このときのfはtoStringとかですね！(※”とか”というのは他にもあるから）

val i:Int = 0
val s:String = i.toString

ほら、Int型のiがString型のsになりました。

さらにもう一例

f:String → Int

この時のfは、toIntとかlengthとかhashCodeとかですね！

val s:String = "1"
val i0:Int = s.toInt
val i1:Int = s.length
val i2:Int = s.hashCode

ほら、String型のsがInt型のiになりました。
「toInt以外は返ってくる値ダメじゃね？」とか思ったそこの貴方。（※思ってない人ごめんなさい）
対象が「型」なので、String型がInt型になればいいんです！

つまり

def f:String => Int
def f:Int => String

こういった定義が成されていればそれでOKということです。

つまり対象が型であり、射がメソッドというのは

型の集合 String,Int ∈ 型
メソッドの集合 toString,toInt,length,hashCode ∈ メソッド

なので満たしますね。

ちなみに、元の対象と先の対象はそれぞれ、ドメイン・コドメインと呼ばれます。
この場合だと

射の合成演算・が存在

射の合成演算子・が射f:T→R, g:R→Sがある時 f・g:T→Sが一意に成り立ちます。

書き方をかえると

R = f(T) 
S = g(R)
S = g(f(T)) = (f・g)(T)

こちらも先ほどの例を引き続いて例を挙げてみると

f:Double → Int
g:Int → String

という二つの射について、

f・g：Double → String

になるやつが定義できればいいんです。

def f:Double =>　Int = _.toInt
def g:Int => String = _.toString
def f_g:Double => String = g compose f

ここは、特に難しいことはないと思います。

単位元が存在すること（※恒等射）

単位元については元の際に説明しています。
圏論ではこの単位元律については恒等射という言葉で出てきます。が、意味しているものはほぼ一緒なので一応説明しておきます。

恒等射とは 各対象Aに対してid:A→Aとなる恒等射が存在し、任意のf:A→Bに対してf・id=f, id・g=gとなる。

射を合成して変えないものですね。

圏を定義してみる

ここまでを踏まえて簡単に定義してみると。

object Category {
  def id[A]: A => A = a => a
  def compose[A, B, C](f: A => B, g: B => C): A => C = g compose f
  trait CategoryLaw {
    def associative[A, B, C, D](ab: (A =>: B), bc: (B =>: C), cd: (C =>: D))
                               (implicit E: Equal[A =>: D]): Boolean = {
      val ad1 = compose(cd, compose(bc, ab))
      val ad2 = compose(compose(cd, bc), ab)
      E.equal(ad1, ad2)
    }
    def leftIdentity[A, B](ab: (A =>: B))(implicit E: Equal[A =>: B]): Boolean = {
      val ab1 = compose(ab, id[A])
      E.equal(ab, ab1)
    }

    def rightIdentity[A, B](ab: (A =>: B))(implicit E: Equal[A =>: B]): Boolean = {
      val ab1 = compose(id[B], ab)
      E.equal(ab, ab1)
    }
  }

  def categoryLaw = new CategoryLaw {}
}

すごくシンプルに定義できると思います。　　

上記のコードを書く上で参考にしたscalaz 7.0では現在このような定義がされていました。

trait Category[=>:[_, _]] extends Compose[=>:] { self =>
  ////
  // TODO GeneralizedCategory, GeneralizedFunctor, et al, from Scalaz6 ?

  /** The left and right identity over `compose`. */
  def id[A]: A =>: A

  /** `monoid`, but universally quantified. */
  def empty: PlusEmpty[({type λ[α]=(α =>: α)})#λ] = new PlusEmpty[({type λ[α]=(α =>: α)})#λ] with ComposePlus {
    def empty[A] = id
  }

  /** The endomorphism monoid, where `zero`=`id` and
    * `append`=`compose`.
    */
  def monoid[A]: Monoid[A =>: A] = new Monoid[A =>: A] with ComposeSemigroup[A] {
    def zero = id
  }

  trait CategoryLaw extends ComposeLaw {
    /** `_ <<< id` is vacuous. */
    def leftIdentity[A, B](ab: (A =>: B))(implicit E: Equal[A =>: B]): Boolean = {
      val ab1 = compose(ab, id[A])
      E.equal(ab, ab1)
    }
    /** `id <<< _` is vacuous. */
    def rightIdentity[A, B](ab: (A =>: B))(implicit E: Equal[A =>: B]): Boolean = {
      val ab1 = compose(id[B], ab)
      E.equal(ab, ab1)
    }
  }

  def categoryLaw = new CategoryLaw {}

  //// val categorySyntax = new scalaz.syntax.CategorySyntax[=>:] { def F = Category.this }
}

今回は全部引用なのでscalazらしい（？）全角記号のλとかあってちょっと難しく見えますが、MonoidとSemigroupという単語を知っていれば読めないレベルの難しいコードではないと思います。