scalaz.NaturalTransformation についての疑問

発端

という がくぞさん の疑問があって

平日夜にすごいH本をちょびちょび読む会 (通称: ちょびよみ) での話題にしよう, という流れになりました.

解説準備用のメモとして, この記事を書いておきます.

Scalaz の雰囲気

「Scalaz の世界観」という見出しにしようかと思ったけど, Scalaz についてほとんど知らないので曖昧な見出しにしておきました.

自分の印象では Scalaz は「Haskell の圏論に裏打ちされた様々な仕組みを Scala の上に移植することが目的」だと感じています. なので, Functor (函手) や NaturalTransformation (自然変換) などの圏論の用語が出てきます.

ここで Scalaz の話と圏論の話をきちんと分けないと, ややこしくなるのだと思います.

Scalaz と圏論

まず大前提の話として, 数学の圏論の概念をそのまま Scala の上に持ってくることはできません. というのは, 現在の代数学や圏論の概念は定義が公理的になっていて, 命題の形で定義が表現されています. そこで, ある概念の Scala 実装が定義を満たしていることを確認するには, その命題が真になることを証明しないといけないのですが, この「証明」というところが問題です. 今のところ Scala には「命題を証明する能力」は無い (はず) です. (もしあったらごめんなさい)

昔, 代数の概念を Python で表現する試み (Python で書く代数) をしたことがあるのですが, 公理を満たしていることのテストは, 結局はいくつかの適当な値でテストしただけでした.

そんなわけで Scala で実装する上では数学の圏論の概念をそのままの形でなく, Scalacheck や scalaprops で使われている) Property Based Testing [1] という手法を利用することになると思います. (関数やメソッドの実装と満たすべき性質から, 自動証明するツールもできなくはないと思いますが, それは Scala の範囲を越えてるので今のとこは対象外) 概念の実装とテストケースを組み合わせて, かろうじて Scala で圏論の概念を表現しているのが現状です.

それでも Java で表現するよりは Scala で表現する方が簡単 (型パラメータまわり) なので, 別に Scala が表現力が弱いとか言うつもりはありません. 本来の使い道からちょっとズレた使い方をしているので仕方無い, という話です. (あれ? Scalaz dis になってるか?)

圏論の自然変換とは

定義は Wikipedia なり何なり色んなサイトに載ってるので, そちらを見てください. 適当な説明をすると「対象どうしを結ぶ射があり, 対象と射をひっくるめたものどうしを結ぶ函手があり, 函手どうしを結ぶのが自然変換」となります. 自分のイメージは「高度な関係性を記述するもの」です. 圏論では自然変換が結ぶのは函手ということになります. (注: 厳密な議論はここではしない)

Scalaz の NaturalTransformation とは

Scalaz では, 真の型 (proper type, kind * を持つもの) のうち関数の型でないものを対象とし, 関数の型を射として圏を構成するようです. (Haskell の Hask 圏と同じ発想?) ここでは, 適当に「Scala 圏」と呼んでおきます.

そして kind * -> * を持つ型コンストラクタ (e.g. List とか Maybe とか) を, Scala 圏から Scala 圏への函手と見なすことができます. これが scalaz.Functor です.

さらにこの scalaz.Functor を別の scalaz.Functor に変換するものには, “NaturalTransformation” という名前を付けるのが自然でしょう. kind だけ見ると (* -> *) -> * -> * となると思います. たぶん.

scalaz.NaturalTransformation は自然変換なのか?

(NaturalTransformation を継承した個々のクラスではなく, NaturalTransformation を継承したクラス全てについて,) この疑問への答えは前述の通り「いいえ」なのですが, それでもある自然変換を scalaz.NaturalTransformation という型で表現したいという意図はあるわけです.

Scalaz の NaturalTransformation という trait は次のように定義されています:

/** A universally quantified function, usually written as `F ~> G`,
  * for symmetry with `A => B`.
  *
  * Can be used to encode first-class functor transformations in the
  * same way functions encode first-class concrete value morphisms;
  * for example, `sequence` from [[scalaz.Traverse]] and `cosequence`
  * from [[scalaz.Distributive]] give rise to `([a]T[A[a]]) ~>
  * ([a]A[T[a]])`, for varying `A` and `T` constraints.
  */
trait NaturalTransformation[-F[_], +G[_]] {
  self =>
  def apply[A](fa: F[A]): G[A]

  def compose[E[_]](f: E ~> F): E ~> G = new (E ~> G) {
    def apply[A](ea: E[A]) = self(f(ea))
  }
}

(https://github.com/scalaz/scalaz/blob/v7.1.3/core/src/main/scala/scalaz/NaturalTransformation.scala#L5-L21 より引用)

この宣言部だけを見てみると, 発端となったがくぞさんの「 (F や G は) kind が * -> * であればよくてFunctorじゃなくてもOKなんですが、圏論的にはFunctorである必要がある感じです?」という疑問が出てきます.

この疑問への答えは

自然変換を表現しようとして NaturalTransformation って名前にしたのだろうし, それなら函手を函手へ写すものであるべき. ただしこれは私の考え方であって,『便利であれば別の使い方をしてもいいだろう』という意見もあると思う. 私は嫌いだけど

となります. コメントには「 FG が函手である必要がある」とは書いてないんですが, Scalaz の世界観的には函手は kind * -> * を持つ型コンストラクタらしいので, やっぱし FG も scalaz.Functor である方が自然だと思います.

ここでは深くは立ち入りませんが, apply メソッドの引数の型 F[A]G[A] の型引数が一致してるのは何故なのか, を調べてみると面白いかもしれません.

ちょびよみで喋るためのメモなので, これくらいの内容でおしまい.

ではでは.

余談

あまり本題には関係無かったけど, カインドってどんなものだろう? と思って, Wikipedia の記事を翻訳しました. カインド (型理論)

脚注

[1]Property Based Testing scalapropsとscalacheckとその他色々