Scalaz の Functor.scala を初心者が読んでみた

Scalaz Advent Calendar の 6 日目の記事として書いています.

準備

今回解説するソースコードは scalaz/Functor.scala です.

scalaz-seven ブランチのものであることに注意してください.

前置き

数学 (代数) は一応やってはいたものの, Scala や Scalaz のことを全然分からない状態からこの記事を書いています. そんな人間が Scalaz を読んだらどう見えるか? という実験記録のようなものがこの記事です.

圏論については「圏論の基礎」を参照しています. 用語などはそちらに倣いました.

数学の函手とは

最初にざっと圏論の概念の定義を並べておきます.

圏 (category) の定義

  • 圏とは対象 (object) と対象の間の射 (arrow) の集まり

    • f はある対象 a とある対象 b を結び付けるもの

      この射は方向を持っているので f: a → b のように表記することが多いです

      この af のドメイン (domain, source), bf のコドメイン (codomain, target) と言います

  • 各対象 c には id c という c から c への射 (恒等射, identity) が存在する

  • f: a → b, g: b → c があったとき, それらをつないだ合成射 (composite) g・f: a → c も存在する

    • 恒等射 id c: c → c と合成の関係は以下の通り

      • f: b → c, g: c → d としたとき (id c)・f = f, g・(id c) = g

        つまり恒等射は合成 (composition) 演算の両側単位元です

    • 複数の合成がつながっている場合合成の順序は問わない

      f: a → b, g: b → c, h: c → d があったとき, (h・g)・f = h・(g・f)

      いわゆる結合則 (associative law) です

つまり圏とは群と群の間の準同型の集まり, のようなものです. この喩えでは, 対象が群という1つの集合なのですが, 圏論では群の元1つ1つについて直接扱わない流儀を採ります.

圏を図で書くと, 圏は対象をノードとし, 射をエッジとする有向グラフになります. これを図式 (diagram) とかと呼んで, 圏の説明で使ったりします.

函手 (functor) の定義

この対象と射を含む圏どうしの間にも対応付け (函手, functor) を考えることができます. 射が対象どうしの対応付けだったのに対し, この函手は圏どうしの対応付けになっていて 1 段上のメタなものになっています.

  • 函手とは圏と圏の間の対応付けで, 対象を対象に, 射を射に対応付ける

    型を考えると対象を写すものと, 射を写すものは別の関数になるのですが, 同じ記号で書いても混ざることは無いので同じ記号を援用したりします

    • 函手 T が写した対象と射の関係は以下の通り

      • T(id c) = id Tc

        恒等射を恒等射に写します

      • T(f・g) = T(f)・T(g)

        合成を保ちます

この函手を大雑把に説明すると, 圏の中にある図式を別の圏に写すものです.

Scalaz の Functor とは

ここまでを踏まえて Scalaz の Functor が数学の函手になっているのか見ていきましょう.

実装

まず Functor の先頭部分は以下のようになっています.

trait Functor[F[_]]  { self =>
  ////

  /** Lift `f` into `F` and apply to `F[A]`. */
  def map[A, B](fa: F[A])(f: A => B): F[B]

  // derived functions
  ...

F という Functor を宣言し, map というメソッドの型が定義されています.

他のメソッドは Functor#map メソッドを使って実装されているので, 最低限 Functor#map だけ実装すれば良さそうです. (このあたりはまた後日追い掛けます)

数学の定義と対比して

Scalaz の Functor はいったいどんな函手なのかを見てみましょう.

Functor#map の型を見てみると以下のようになっています.

/** Lift `f` into `F` and apply to `F[A]`. */
def map[A, B](fa: F[A])(f: A => B): F[B]

これから map メソッドは fa: F[A]f: A => B を受け取って, F[B] 型のインスタンスを返すのが分かります. 意図としては, f という関数を持ち上げて fa に適用しています.

図式として書くと以下のようになります.

F[A] → F[B]
 ↑      ↑
 A   →  B

函手のドメインである圏には AB が対象として存在し, f が射として存在しています. 下の段の矢印が射 f です.

A → B
  f

対象 A, B をそれぞれ持ち上げているのが型パラメータを 1 つだけ受け取る型クラス F です.

  F[A]   F[B]
F ↑    F ↑
  A       B

函手のコドメインである圏には F[A]F[B] が対象として存在し, map(_)(f) が射として存在しています. これが F[f] に相当します. (型が違うので, Scala でこうは書けませんが) Functor#lift の実装は map(_)(f) となっているので, 射 f を持ち上げたものが lift(f) となり, 上の図式の F[A] から F[B] の射になっているわけですね.

   lift(f)
F[A] → F[B]

数学の圏論の言葉で説明すると,「Scalaz の Functor は『クラスを対象とし, 関数を射とする圏』の自己函手」となっています.

ここまでは函手の型の話で, 数学の定義に沿っていることが分かりました. しかし, 関手の定義はそれだけではなく公理的に記述された制約がありました. 「恒等射」と「合成の保存」です.

これは FunctorLaw という trait で実現されています. FunctorLaw には identity, associative というメソッドがあり, それぞれ恒等射, 合成の保存の制約をチェックする役割を担っています.

公理の名前の間違い (?)

気付いた人もいるかもしれませんが,「合成の保存」は英語では "preserve composition" と言います. "associative" は「結合的」という意味で, h・(g・f) = (h・g)・f という性質を表します.

よく考えると意味が違うのですが, 何故かこのような名前になっています. 不思議に思って Scalaz のメーリングリストで聞いてみましたが, 1 人同意してくれた以外には反応がありませんでした. みんな気にしてないのかな. そのうち pull request 投げてみます.

FunctorLaw のチェックには ScalaCheck が使われているそうなので, 間に合えばこの Advent Calendar の記事として書いてみたいと思います.

おわりに

実装も何もない記事でしたが, Scalaz のソースコードを読み始めるときの手掛りになれば嬉しいです.

それでは次は @pocketberserker さん, お願いします.

Comments

blog comments powered by Disqus

Licenses