Ch11: 宣言的プログラミング を読んでいく

イントロ

この章では、圏論とプログラミングの関係を改めて整理していく。
まずはプログラミングの種類を分解した後、圏論がどこに関わっていくのかを考えていこう。


留意点
CTFPではこの章で物理学の例を記載しているが、本稿では省略する。
遠い未来、私が物理を勉強する機械があれば書き加えるかもしれない。


11.1 プログラミングの種類

注意: この項では、CTM(ガウディ本)の内容を元にしている。

プログラミング(の計算モデル)は、いくつかの分類方法があると思うが、まずは 宣言的であるかどうか で分けることができる。
宣言的とはどういうことか。CTMでは以下のように言っている。

宣言的であるということは...直感的に言えば、「どのように」を説明せずに、「何」を定義することによってプログラムすることである。
ここで、「何」とは達成したい結果であり、「どのように」とはその結果を達成するのに必要なアルゴリズム等である。
(出典: コンピュータプログラミングの概念・技法・モデル)

宣言的であるとは、正確には以下の要件を満たした操作のことをいう。

  • 独立性: それ以外の操作のどんな実行状況にも依存しない
  • 状態なし: ある操作とそれ以降の操作の間に記憶・共有されている内部実行状態がない
  • 決定的: 同じ引数を与えられれば常に同じ結果を返す

宣言的であるプログラムと宣言的でないプログラムの例を見てみよう。

TODO: 例

宣言的プログラムに注目すると、それは 表現力 によって更に2つに分けられる。

  • 記述的な宣言性: データ構造を定義しているにすぎないもの。事実、この言語はレコードを定義することしかできない。処理しやすいという利点がある。
    • 例) HTML, XML
  • プログラム可能な宣言性: チューリングマシンと同等の表現力を持つようなもの。
    • 例) 関数型プログラム(Haskell等), 論理型プログラム(Prolog等)

プログラム可能な宣言性は更に定義敵味方と観察的見方がに分けられるが、ここでは省略する。
ここで重要なのは、冒頭で「宣言的であるとは、「何(What)」を定義する」と話したが、記述的宣言性はプログラム可能宣言性と比べてより宣言的であるということだ。
宣言的であるとは01の関係ではなく、「程度」による。

また、1つのプログラムやプログラミング言語は宣言的な部分と宣言的でない部分を併せ持つ事が多い。
例えばScalaでは宣言的でないプログラミングも可能だが、宣言的であるプログラミングも可能だ。

11.2 プログラムが宣言的であることの嬉しさ

注意: この項では、CTM(ガウディ本)の内容を元にしている。

ここまで話していると、宣言的であるプログラムは宣言的でないプログラムの下位互換でしかないと思う人がいるかもしれない。
しかしそれは大きな間違いだ。
宣言的プログラミングは以下の観点で重要である。

  • 宣言的プログラムは推論が容易だ
    • 宣言的モデルで書かれたコードはそうでないものより読みやすい。なぜなら外部環境に影響を受けず、入力にのみ影響を受けるからだ。これにより推論は簡単になり、テストもしやすくなる
  • 宣言的プログラムは合成的だ
    • 宣言的プログラムやコンポーネント同士を組み合わせたり合成したものもまた、宣言的である

11.3 圏論はより宣言的である

皆さんは微積分をご存知だろうか。
微積分では微分(簡単に言えば、関数の各点における傾き(変化の割合))という概念があるが、これはwikipediaでは以下のように説明されている。

微分係数 f′(a) とは、関数 f のグラフの x = a 付近を(すなわち点 (a, f(a)) 付近を)限りなく拡大していったときに、グラフが直線に近づいて見える場合における、その直線の傾きのことである。 出典 wikipedia

この説明から、微積分、より正確に言えば微分という概念は「宣言的ではない(より命令的)」と言えるだろう。
なぜなら、定義が「何(What)」ではなく、「どのように(How)」「どんな操作」によってされているからだ。

次に、集合論における直積の定義を見てみよう。

集合のデカルト積(デカルト­せき、英: Cartesian product)または直積(ちょくせき、英: direct product)、直積集合、または単に積(せき、英: product)、積集合は、集合の集まり(集合族)に対して各集合から一つずつ元をとりだして組にしたもの(元の族)を元として持つ新たな集合である。
出典 wikipedia

この定義もまた、「宣言的ではない」と言えそうだ。
なぜなら、例えば2つの集合 A={a1, a2, a3}, B={b1, b2}が在る時に「Aから1つ要素をとって、次にBから1つ要素をとって、2つを組み合わせることを繰り返すことで構成する」という操作が定義だからだ。

ここで、圏論における直積の定義はどうなっていたか。
ここで出てくる言葉をまだ勉強していないとしても、定義が性質(「何」)によってされている ことに注目してほしい。

定義: 積 Product
2つの対象a, bの積とは、以下の定義を満たす対象cのことであり、a × bなどと書く。
f: d -> a, g: d -> b の2つの射をもつ任意の対象dに対して、p . m = f かつ q . m = gを満たすp: c -> a, q: c -> bが存在するようなm: d -> cが一意に存在する。
出典 ch5: Products and Coproducts を読んでいく

圏論の概念の多くはその構成方法ではなく普遍的性質によって定義されており、
このことから 圏論はより宣言的である といえるだろう。

1.3 圏論とプログラミング

そんな宣言的な圏論は、Haskellの含む関数型プログラムに関する推論を助けてくれる。
例えば、直接/間接的に、既存のプログラム構成や新しいものを正当化するのに役に立つ。

圏論はプログラムを宣言的なレベルでの推論をするためのメタ言語として活用できるのだ。

Ch10: Natural Transformation を読んでいく

イントロ

私達は最初に、圏Cの対象a, bの関係として射を考えた。
次に、1つレイヤーを上げて、圏Cと圏Dの関係として関手を導入した。(特に、関手は圏の構造を保存するものだ)
今回は更にもう一つレイヤーを上げよう。

この章では、関手Fと関手Gの関係を表現するものである自然変換 を導入する。

まずはイメージを膨らませよう

自然変換について考える前に、まずは「関手と関手の関係性」を表現するとはどういうことかを考えてみよう。

関手は「ある圏を構造を保ったまま他の圏に埋め込むもの」であったが、他の捉え方として「ある圏を他の圏の中でモデル化するもの」ともみなせる。

この様に関手をみなした時、ドメインの圏は「コドメインの圏の1部分の構造を表すモデル ー設計書ー 」と言える。

感覚を掴むために、例として「動物を、四肢・胴体・頭があるものとしてモデル化する」ことを考えてみよう。
そのために、まずは圏Modelと圏Animalを定義する。

圏Model
- 対象: {head, torso, limb1, limb2, limb3, limb4}
- 射: torsoを中心とした繋がり(下図を参照) 圏Modelのイメージとしては、headが頭、torsoが胴体、lim{n}が四肢に対応しており、射は夫々の繋がりを表現している。

f:id:sereronnrot:20210323050234p:plain

圏Animalはいろいろな動物の部位がそれぞれ対象に、夫々の繋がりと、各動物の同じ部位が同じものが射で繋がれている圏だ。
射の例としてあは 「犬の頭 <- 犬の胴体」や「犬の頭 <- サンタさんの頭」等。
(下図では各動物の同じ部位の繋がりは省略されている。)

f:id:sereronnrot:20210323050253p:plain

これらの圏の間の関手を考えることで、例えば「犬をモデル化」することを表現できる。

具体的には、下図の様に圏Modelの各対象・射を圏Animalにおける犬の各部位の一部に対応付けられる。
下図の関手F を見てほしい。 圏Modelの各対象と射が圏Animalの「犬の四肢・胴体・頭とその間の射」にマッピングされている。
ここでは厳密な定義はしないが、Fが関手である(になれる)ことはなんとなく分かると思う。
(ここで、犬のしっぽ(tail)はモデル化の対象外ではない事に注意しよう)

f:id:sereronnrot:20210323050405p:plain

また、圏Animalには犬の部位以外も存在するので、他にもサンタさんをモデル化する関手G, 猫をモデル化する関手H が考えられるだろう。

f:id:sereronnrot:20210323050924j:plain

各動物のモデル化を表す関手F, G, H が作れたところで、次はこの問いを考よう。

  • 「犬をモデル化する表現F と猫をモデル化する表現H 」は何らかの関係性があるのか?
    • 例えば、関手F から関手G を作成する事はできるのか?(或は、関手Fで関手Gを表現できるのか?)

具体的に言えば、α: F -> G の様なものの存在を考える。

f:id:sereronnrot:20210323051042p:plain

αに満たしてほしい制約としてはどんなものがあるだろうか?

まずはじめに、圏と圏の関係性を表現する関手が圏の構造を保つものであったように、このαも関手の構造を保つものであってほしい。
また、F, Gは同じドメイン(圏Model)の共通の対象・射を同じコドメイン(圏Animal)の夫々異なる対象と射にマッピングするため、
F, Gの間に違いがあるとすればコドメインの圏の中の要素間の違いであり、それらの違いはドメインの要素で説明されるのが自然だといえる

この様なαが存在すれば、αは関手によるモデル化を比較するのに使えるだろう。

では、関手Fと関手Gの関係α を表すのにどんな構成要素が必要か考える。
一度抽象的な圏に戻って考えていこう。
関手F: C -> D は、以下の2つの構成要素で成り立っていた。

よって、自然変換α: F -> Gは、F1, F2をそれぞれG1, G2へ対応させれば良いので、以下の2つの構成要素があればよい。
- α1: F1 -> G1
- α2: F2 -> G2

だが、自然変換は関手の構造を保存するようにしたいので、α1: F1 -> G1は、圏Cの各対象a についてF1(a)がG1(a)に対応付けるようにしたい。
(圏Animalの例に戻ると、「頭 => 犬の頭」という対応は「頭 => 猫の頭」という対応に紐付いてほしくて、「頭 => 犬の頭」と「胴体 => 猫の胴体」を関連付けても微妙でしょ?そんな事ないかな)

α2に関しても同様である。

よって、自然変換α: F -> Gは、F1,F2をそれぞれG1, G2へ対応させれば良いので、以下の2つの構成要素があればよい。

  • α1_a: F1(a) -> G1(a) a ∈ Obj(C)
  • α2_f: F2(f) -> G2(f) f ∈ Hom(a, b) a, b ∈ Obj(C)

注意: α1_aは対象a毎に定義される。α2_fも同様にf毎に定義される。

まずα1_aについて検討していこう。
ここで注意したいのが、F1(a)とG1(a)は同じ圏の中にあるので、α1_aは圏Dの対象同士の関係を表しているということだ。
...圏の対象同士の関係を表すものを私達はすでに知っている。そう、射だ。
なので、α1_aとして態々新しく対象同士の関係の概念を作るより、すでに存在する射を使用するほうが自然だといえる。
よって、α1は射の選択である
αを自然変換と呼ぶなら、このα1_aをα1のaでの要素と呼ぼう。
(aは圏Cの対象なのに対し、α1_aは圏Dの射であることを覚えておこう)

そういうわけで、もし圏DにおいてHom(F1(a), G1(a))が空集合である場合は、FからGへの自然変換は存在しない。

次に、α2_fについて検討していこう。
結論から言うと、α2_fは常に固定されており、わざわざ考える必要がない。 (TODO: 怪しい)
固定されているとはどういうことか?
2つの関手による射のマッピングは、驚くほど強く、それと整合性が取れる自然変換の選択肢を制限する。(TODO: もうちょいちゃんと書きたい)

よって、これからはα1を自然変換αと表記する。

関手F, Gによって圏Cの射f:a -> b はF(f), G(f)に移され、
さらにαa: F(a) -> G(a), αb: F(b) -> G(b) なので、図示すると以下のようになる。

f:id:sereronnrot:20210323051924j:plain

圏Animalの例をかんがえると、以下のような対応があるイメージだ。

f:id:sereronnrot:20210323053851j:plain

さて、先程話したように、α は「関手の構造を保つものであってほしい」という願いがある。
この願いを満たすために、α には満たすべき以下の条件を付け加える。

  • G(f) ∘ αa = αb ∘ F(f)

この条件を、自然条件と呼ぼう。
ここで使用されている合成則 ∘ は圏Dのものであることに注意。

f:id:sereronnrot:20210323052313j:plain

自然条件を圏Animalの例に当てはめると、「注目する対象を犬の頭から犬の胴体にしてから、自然変換で犬の胴体から猫の胴体へ移ること」と、「自然変換で犬の頭から猫の頭に移ってから、注目する対象を猫の頭から猫の胴体にすること」が同じになってほしいという要請だ。

お気持ち的には、
A. 変換α は関手から関手への対応なので、圏の対象が何であるかは(レイヤーが2つ下なので)忘れたい。よって、fで最初に対象aからbへ変換した後に変換を行ったとしても、変換を行ってからfを適用しても同じ結果になってほしい。
B. 関手の構造を保持するという成約を式にした
のどちらかなんだろうなぁと思っている。(TODO: 考える)

以上で変換αのイメージとしてはある程度形になったと思うので、次項では変換α を自然変換として定義する。


理解を深めるために、F(f)が逆射を持つ場合を考えてみよう。
すると、自然性によって、α_aを用いてα_bを書くことができる。

αb = G(f) ∘ αa ∘ (F(f))-1

もちろん、2つの対象の間に複数の可逆な射がある場合、それら全てについて上の式が成り立つ。


自然変換の定義

自然変換を以下のように定義する。

定義: 自然変換 Natural Transformation

C, Dを圏とし、F, GをCからDへの関手とする。自然変換 α は以下のように定義される。
任意のαa という意味でαC という表現も使用される。
- α: a -> αa a ∈ Obj(a)
- α
a: F(a) -> G(a)

ただし、αCは以下の自然条件を満たす。
- α
b ∘ F(f) = G(f) ∘ α_a a, b ∈ Obj(C)

自然条件は可換図式では以下のように書ける。

f:id:sereronnrot:20210323054406j:plain

定義終

自然変換によって関連付けられている関手の不足・または豊富さは、それらがつなげる圏の構造について沢山の事を教えてくれる。
(極限や米田の補題でこの話題にもう一度戻ってくるらしい)
(後の章で詳しく扱うそう)

自然変換は対象と射の対応とも捉えられる。
また、自然条件より、射fを可換な四角形に変換するとも言える。

f:id:sereronnrot:20210323054709j:plain

この自然変換の特性は、可換図式を含む圏論的構成の際に非常に便利であることが多い。
適切に関手を選んであげることで、多くの可換条件が自然変換へと変換できるからだ。
(これもまた後の章で詳しく扱う)

最後に、自然変換は関手の同型を定義することができる。

定義: 自然同型
F から G への自然変換 η が存在して η_X が C に含まれる全ての対象 X に対して同型射となるとき、この自然変換は自然同型であるといい、F ≈ η G などと書く。
(また、FとGは自然同型であるとも言う)
圏 C, D の間の関手 F: C → D, G: D → C について自然同型 GF ≈ Id_C, FG ≈ Id_D がともに成り立つならば C と D は同等なもの(圏同値)と見なされる。
(引用元 Wikipedia)

10.1 Polymorphic Functions 多相関数

さて、自然変換はプログラム上ではどの様に表現されるのだろうか。
一例として、Scalaでは以下のように書ける。

def alpha[A]: F[A] => G[A]

自然条件はどの様に書けるだろうか?

G.map(f) compose alpha == alpha compose F.map(f)

ここで、改めてこの関数がパラメータ多相であることを意識してほしい。
Haskell(や副作用のない関数のみを使う場合は?)では、F, G が関手なら、alphaは自動的に自然条件を満たす
何故自動的に自然条件が成り立つかは本記事の範囲を超えるので、興味ある人はTheorems for freeで調べてほしい。
また、パラメータ多相は全ての型に対して1つの式しか使えないため、表現力はかなり制限されることには注意しよう。

最後に、いくつかの例を書いてこの項は終わりにする。

①シンプルな例

def safeHead[A]: List[A] => Option[A] = {
    case Nil => None
    case x :: xs => Some(x)
}

この関数は、Aに関してポリモーフィックなので、自然変換だ。
一応、自然条件を確認してみる。

(map(f) compose safeHead) == (safeHead compose map(f))  
map(f)(safeHead(List.empty)) == map(f)(None) == None  
safeHead(map(f)(List.empty)) == safeHead(List.empty) == None  
map(f)(safeHead(x :: xs)) == map(f)(Some(x)) == Some(f(x))  
safeHead(map(f)(x :: xs)) == safeHead(f(1) :: map(f)(xs)) == Some(f(x))  

②片方の関手がConstである例
片方の関手がConstである場合、自然変換は引数か出力のみポリモーフィックである関数になる。

def length[A]: List[A] => Const[Int, A] = {
    case Nil => Const(0)
    case x :: xs => Const(1 + unConst(length(xs)))
}

def unConst[C, A]: Const[C, A] => C = {
    case Const(x) => x
}

lengthは自然変換だが、実質的に出力はIntになっていることが分かる。

次はドメイン(引数)がConstの例だ。

def scam[A]: Const[Int, A] => Option[A] = {
    case Const(x) => None
}

③Readerの例
最後の例として、Reader関手にふれる。
例えばUnitドメインのReader関手は以下のように定義できた。

// 今回はUnitがドメインのReader関手を作っているが、ドメインは好きなもので良い
type Reader[A] = Unit => A
implicit val readerFunctor = new Functor[Reader] {
  def map[A, B](f: A => B)(g: Reader[A]): Reader[B] =
    f compose g
}

すると、任意の型A に対して、Reader[A]から他の任意の関手Fへの自然変換を作ることができる。
例えば、UnitドメインのReader関手からMaybe関手への自然変換は以下の2つだけである。

  // 自然変換の型は以下のようになっていてほしい
  //def alpha[A]: Reader[A] => Option[A]

  def dump[A]: Reader[A] => Option[A] = {
    case _ => None
  }

  def obvious[A]: Reader[A] => Option[A] = {
    case g => Some(g())
  }

この項では、関手の間のパラメータ多相関数は自然変換になる事を確認した。
特に、ADTを入力・出力とするポリモーフィックな関数はADTが関手であるため自然変換だ。

10.2 Beyond Naturality 自然性を超えて

この項では関数型が関わる自然変換に注目する。
ここで思い出してほしいのが、関数型は出力型に対して共変的であるということだ。
よって、関数型から関手を作り(ex Reader関手)、それらの間をつなぐ自然変換を作ることができる。 そして、その時作った自然変換は、高階関数とみなせる。

しかし、関数型は引数の型に対しては反変的である。
反変関手に対して自然変換は定義できるだろうか?

可能である。反変関手は反対圏の共変関手であるため、反変関手から反変関手への自然変換を考えられる。
ただ、その時に1つだけ問題になるのが、自然条件だ。
自然条件をScalaで書いた時に、mapを使用していたので、今回はそれをcontaramapに以下のように置き換える必要がある。

G.contramap(f) compose alpha == alpha compose F.contramap(f)  

可換図式は以下のようになる。(左右を見比べてみよう)
f:id:sereronnrot:20210323055409j:plain

これで反変関手の自然変換が定義できたので、最後に実例を考えてみよう。
Ch9で反変関手の例として登場したOp関手を覚えているだろうか?

  // 今回はIntがコドメインのOp関手を考える
  type Op[A] = A => Int  

  // 反変関手の定義  
  trait Contravariant[F[_]] {
    def contramap[A, B](f: B => A)(fa: F[A]): F[B]
  }

  implicit val opContravariant = new Contravariant[Op] {
    override def contramap[A, B](f: B => A)(fa: Op[A]): Op[B] = fa compose f
  }

Op関手を使って、自然変換の例を作ってみる。

  // これら2つの関手は異なるものであることに注意
  type BoolOp[A] = A => Boolean
  type StrOp[A] = A => String
  
  implicit val boolOpContravariant = new Contravariant[BoolOp] {
    override def contramap[A, B](f: B => A)(fa: BoolOp[A]): BoolOp[B] = fa compose f
  }
  implicit val strOpContravariant = new Contravariant[StrOp] {
    override def contramap[A, B](f: B => A)(fa: StrOp[A]): StrOp[B] = fa compose f
  }

  // 自然変換
  def boolToStr[A]: BoolOp[A] => StrOp[A] = {
    case f => (x: A) => if (f(x)) "T" else "F"
  }

補足: 自然変換の一般化について
Ch8の補足で、A => Aのように、関手ではない型コンストラクタの話をしたのを覚えているだろうか。
当然、A => Aは関手ではないので、(A => A) => F[A]はFが関手であっても自然変換ではない。
しかし、自然変換にはこういったものを扱う一般化が存在する。
それはエンド について議論した際に出会うことになる。

10.3 Functor Category 関手圏

今や我々は関手と関手の関係性を記述する道具を手にしている。
であれば、関手を対象とした圏を考えたくなるのは自然だろう。

関手圏は、雑に書くと以下のような圏になるはずだ。

  • 対象: 関手
  • 射: 自然変換
  • 合成則: ???
  • 単位射: ???

我々はまだ自然変換の合成則を作っていないので、それを考える必要があるが、実は我々はすでに答えを持っている。
F, G: C -> Dの時、自然変換α: F -> G は圏Dの射 であるので、圏Dの射の合成則を使えばよい。

単位射は対応する圏Dの単位射を使えば良い。

これで関手の圏を作る材料が揃ったので、以下に定義を記載する。(注意: わかり易さを優先して細かい条件などを省いている。詳しい定義はWiki参照)

定義: 関手圏 Functor Category

C, Dを圏とする。以下のような圏を関手圏とよび、Fun(C, D), [C, D]やDC等と書く。
- 対象: 圏Cから圏Dへの関手
- 射: FからGへの自然変換 F, G ∈ Obj([C, D])
- 合成則: f ∈ Hom(a, b), g ∈ Hom(b, c) a, b, c ∈ Obj([C, D])の時、g ∘ fは圏Dの合成則
参考とより正確な定義

関手圏の単位射は identity natural transfromation id_Fだ。これは実質、圏Dの単位射。
- id_Fa:: F(a) -> F(a)

また、特に関手圏の射αa: F(a) -> G(a), βa: G(a) -> H(a) の合成はβa ∘ αa: F(a) -> H(a) だが、これは対象ごとに考えるのではなく自然変換レベルの合成を考えることも出来る。
この合成を垂直合成という。

  • α: F -> G, β: G -> H なら α・β: F -> H

f:id:sereronnrot:20210323060703j:plain

関手圏がDCで表されているのを見ると、関数型: a -> bがbaで表現されていることを思い出す。関手圏も(いづれかの見方で)関数対象とみなせるのだろうか?
それについては、次の項で圏Catを学んだ際に回答していく。

TODO: 加筆
指数対象と同じ議論

10.4 2-Categories 2-圏

この項では、対象が(小さい)圏である圏Catを学ぶ。
カンの良い人ならここで「対象が圏なら射は関手かな?」と分かるかもしれない。
正しい。圏Catの対象と射は以下のように定義される。

  • 対象: 小さい圏 (小さい圏とは、Obj(C)やHom集合がともに集合になる圏)
  • 射: 関手
  • 合成則: 関手の合成

しかし、関手を導入した段階で圏Catを紹介しなかったのは、更に追加の構造を考えるからだ。
これまで登場した圏ではHom集合はただの集合であり、その中に構造は入れていなかった。

しかし、圏CatのHom集合は夫々ドメインとコドメインが同じである関手の集合であるが、ドメインとコドメインが同じ関手の間には自然変換によるリッチな構造が存在している。(我々は特にこれを関手圏とした)

すると、圏Catから見ると

  • ①射 関手: 射
  • ②射 自然変換: 射と射の間の射

の2種類の射が存在するといえるだろう。

f:id:sereronnrot:20210323061055j:plain

また、これらにはそれぞれ合成則があった。

  • ①合成則: F: C -> D, G: D -> E なら F ∘ G: C -> E であり、 F ∘ G ∈ Obj(EC)
  • ②合成則: α: F -> G, β: G -> H なら α・β: F -> H (垂直合成)

では、これら2つの合成則はどんな相互作用を起こすのだろうか?
その一例として、以下のようなケースを考えてみる。
1射
F : C -> D
F': C -> D
G : D -> E
G': D -> E
2射
α : F -> F'
β : G -> G'

これらを図で書くと以下のようになる。

f:id:sereronnrot:20210323063205j:plain

この時、G ∘ FとG' ∘ F'の関係をα, βを使って記述したいとする。
関手同士の関係は自然変換で表されるので、出来れば自然変換で記述したい。
そういうわけで、以下の図でG(F(a))とG'(F'(a))の間の射がほしくなる。

f:id:sereronnrot:20210323063412j:plain

ここで、自然変換α,βはそれぞれ圏Dの射であることから、関手GでαaはG(αa)に移されることに注意すると、G(F(a))からG'(F'(a))へは、以下の2つのパスがある事がわかる。
1. G(F(a)) -βF(a)-> G'(F(a)) -G'(αa)-> G'(F'(a))
2. G(F(a)) -G(αa)-> G(F'(a)) -βF'(a)-> G'(F'(a))

  • β_F(a) :: G(F(a)) -> G'(F(a))
  • β_F'(a) :: G(F'(a)) -> G'(F'(a))
  • G(α_a) :: G(F(a)) -> G(F'(a))
  • G'(α_a) :: G'(F(a)) -> G'(F'(a))
    (上2つはF ∘ Gにおける外側のGを変更しているのに対し、下2つは内側のFを変更していることに注意)

これらのパスを射の合成を使って書くと、 1. G'(αa) ∘ βF(a)
2. βF'(a) ∘ G(αa)

となるが、これらはβの自然性から同じものである。TODO:加筆
よって、以下の自然変換を定義することが出来た。
β ∘ α : G ∘ F -> G' ∘ F'

これを、水平合成 と呼ぼう。

f:id:sereronnrot:20210323063426j:plain

また、垂直合成と水平合成について、以下のような可換法則が成り立つ。
(証明は次の項で記載する)

  • (β1・β0) ∘ (α1・α0) = (β1 ∘ α1)・(β0 ∘ α0)

図で書くとこんな感じ

f:id:sereronnrot:20210323063500j:plain

ここまでの話をまとめよう。
圏Catは、対象として圏を、射として関手を持つが、加えて射から射への射も加えて持ち、それらの間に垂直合成と水平合成が存在する事がわかった。
圏Catは以上の性質より圏の一般化と考える事ができ、2-category(2圏) の一例となっている。

定義: 2-category 2圏

2-categoryは圏の一般化であり、以下のもので構成される。

  1. 対象
  2. 1-射: 対象と対象の間の射
  3. 2-射: 1-射と1-射の間の射

射は、以下の2つの方法で合成ができる。

  • 水平合成: 対象に沿った合成
  • 垂直合成: 射に沿った合成

なお、射の合成はcoherent associator 2-morphismsまでのみassociativeである。
定義終

圏Catの要素を2-categoryの要素と対応させると、
1. 対象: 小さな圏
2. 1-射: 関手
3. 2-射: 自然変換

となる。

圏Catを考えた時、その圏の射は関手であるので、対象C, Dの間の射の集合Hom(C, D)は、正しく関手の集合である。
TODO: C, Cat, Funの図

そして勿論[C, D]が圏であることから、圏Catの対象として存在するため、圏Catもカルテシアン閉圏であることがわかる。(実際にはもっと強く、full-blownである。)

TODO: 加筆
指数対象と同じ議論

10.A 髭結合と可換法則の証明

自然変換について、特に抑えるべき重要なパターンがある。
1つ目は髭結合だ。


圏C, D, Eについて、関手F: C -> D と 関手H, I: D -> E、自然変換β : H -> Iがあるとする。
図示すると以下のような状況だ。

f:id:sereronnrot:20210323063829p:plain

この状況で、自然変換: H ∘ F -> I ∘ F が以下の様に得られる。

βは圏Dの各対象d に対して 射βd: H(d) -> I(d)を対応させており、特に関手Fのイメージ(d=F(c)となるc ∈ C がある)に対しては、
β
F(c): H(F(c)) -> I(F(c)) と書ける。
このβ_F(c) は圏Eの射であるので、これを集めることで圏Cから圏Eへの自然変換が作成できる。
そして、この自然変換は: H ∘ F -> I ∘ Fと表現できる。
この自然変換をβF と書き、Fとβの左髭結合と呼ぶ。
(βFは β・F とも書く。これは、Fを恒等な自然変換: F -> Fとみなすとこの様に表記できるからだ。)

左髭結合があるんだから、もちろん右髭結合もある。
以下のような図式を考える。

f:id:sereronnrot:20210323063838p:plain

この時、自然変換: H ∘ F -> H ∘ G を考えると、左髭結合のときと同じ様に
α_H(d): H(F(c)) -> H(G(c)) が考えられ、これを集めた自然変換は: H ∘ F -> H ∘ Gと表現できる。
この自然変換をと書き、Hとαの右髭結合と呼ぶ。
(Hα はH・α とも書く。)


髭結合について、以下の分配法則が成り立つ。

圏C, D, Eと関手F, G, P: C -> D、H: D -> Eと自然変換α: F -> G, β: G -> Pがあるとする。
この時、 H(β ∘ α) = (Hβ) ∘ (Hα) が成り立つ。
(この法則は右髭結合に関しても類似のものが成り立つ)


補足: 証明
βとαは圏Dの射であることとH の関手性から、
H(β ∘ α) = H(β) ∘ H(α)が成り立つ。


髭結合を使って、前項の水平合成に関する議論をより数学的に行うことが出来る。
圏C, D, E と関手F, G: C -> D、H, I: D -> E、自然変換α: F -> G, β: H -> I があるとする。
この時、以下の式が成り立つ。
- (βG) ∘ (Hα) = (Iα) ∘ (βF)
この時、この式の両辺をβα と書き、αとβの水平合成と呼ぶ。

TODO: 図


証明
圏Cの対象c について、左辺は以下のような変換を行う。
H(F(c)) -[Hα]-> H(G(c)) -[βG]-> I(G(c))

右辺は以下のような変換を行う。
H(F(c)) -[βF]-> I(F(c)) -[Iα]-> I(G(c))

よって、右辺と左辺が同じということは以下の図式が可換であることと同値。
一方でこの図式が可換であることはβの自然性からいえる。

f:id:sereronnrot:20210323063920p:plain


これらの事実を使用し、前項の可換法則を証明することが出来る。
可換法則は以下のような式だった。

  • (β'・α') ∘ (β・α) = (β' ∘ β)・(α' ∘ α)

証明
β ∘ α : G ∘ F -> G' ∘ F'
β' ∘ α' : G' ∘ F' -> G'' ∘ F''

(β'・α') ∘ (β・α)
= (β'・α')F'' ∘ G(β・α)
= (β'F'') ∘ (α'F'') ∘ G(β・α)
= (β'F'') ∘ F'(β・α) ∘ β(F)
= (β'F'') ∘ (G'α') ∘ (G'α) ∘ (βF)
= (β'・α') ∘ (β・α)

10.5 Conclusion まとめ

この章では、自然変換や関手圏等を扱った。
自然変換は、プログラムでは特定のポリモーフィックな関数として表現される事を学んだ。
関手圏では関手は対象として、自然変換が射として扱われる事に加え、2つの合成則-水平・垂直合成-が導入された。

10.6 Challenges

TODO: やる。

自然変換に関する自分用のメモ

本文で、自然変換は以下の構成要素であるべきと最初に話した。

① α1_a: F1(a) -> G1(a) a ∈ Obj(C)
② α2_a_b: Hom(F(a), F(b)) -> Hom(G(a), G(b)) a, b ∈ Obj(C)

が、実際にはα2_fは必要ないのだが、それに関して(周りと話したり)して考えたことをひとまず書いておく。
仮にα2_fがあるとしたら、こういう関係が成り立ってほしい。

③ α2_a_b(F(f)) ∘ α1_a = α1_\b ∘ F(f)

これは、自然変換が「関手の構造を保存する」という要請から来ている。
注意: これは、④ G(f) ∘ αa = αb ∘ F(f) とは異なる。
では、{①, ②, ③}を自然変換の構成要素・条件とすれば良いのではと思うが、これは{①, ④}である本来の自然変換の定義より強い。(らしい)
そして、実用上は{①, ④}ぐらいの強さが丁度いいらしい。
また、{①, ④}だけでは②は言えない。
また、{①, ②}だけでも足りない。
例:
Obj = {*}
Hom(*, *) = {±1, ±2, ..., ±n, ...}
f ∘ g = f + g
の時、
α(F(n)) = G(n)
F(n) = n (Fは恒等関手)
G(n) = -n
α(F(n)) = G(n)
α(n) = -n
この時、

G(n) ∘ α(G(*)) = α(F(*)) ∘ F(n)
{m = α(*)} -n + m = m + n mはキャンセルされてしまって、定義ができない。

参考 https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%AA%E3%83%A2%E3%83%BC%E3%83%95%E3%82%A3%E3%82%BA%E3%83%A0

https://math.stackexchange.com/questions/3142222/natural-transformation-parametric-polymorphic-function-in-structure-categorie https://ncatlab.org/nlab/show/2-category#:~:text=The%20easiest%20definition%20of%202,hom(x%2Cy).&text=This%20produces%20the%20classical%20notion%20of%20strict%202%2Dcategory. http://pantodon.shinshu-u.ac.jp/topology/literature/2-category.html https://home.gwu.edu/~wschmitt/papers/cat.pdf

【読書メモ】 Murphy Probabilistic Machine Learning: An Introduction ドラフトを読んだメモ

Probabiistic Machine Learning: An Introduction (Murphy) のドラフト(2021 Mar 8)をちろちろ読んだ感想を書き溜めてく。

1章 Introduction - 確率的アプローチを取る理由 1. 不確実性の元での決定にたいする効率的なアプローチ - 意思決定するのは人間である前提? (機械がするなら確率じゃない、Energy based modelのほうが良さそう) 2. 確率的モデリングは色んな分野で使われた統一的なフレームワーク - 帰納バイアス

Foundation

2章 Probability: univariate models 随分色々詰め込んでいた...
ヤコビアンとかの話は後半にいきそう

  • 不確実性のタイプはその理由で2つに分けられる
    1. epistemic uncertainty (model uncertainty)... データの取得方法や背後に隠された原因や構造に起因するもの
    2. aleatoric uncertainty... 内在的な変動性に起因するもの。これはデータをより多く集めても改善することはできない
      • ex) 公平なコインを投げた時、表が出る確率はp=0.5
    3. この区分けはactive learning等の応用で特に重要
      • ex) H(p(y| x, data))が大きい時、model uncertaintyであるH(p(theta| data))が大きいのか、aleatoric uncertaintyである H(p(y|x, x, theta))が大きいのか。
  • softplus 関数というものがあるらしい。
  • 積分は「和」で、畳込みは「flip and drag operation」と捉えられる

3章 Probability multivariate models

  • マハラノビス距離は「線形変換を通した、より低次元でのユークリッド距離」として考えられる

線形変換L s.t. Σ-1 = L'L, L: RD -> Rd (d ≦ D)
(y - μ)Σ-1(y - μ) = (Lδ)'(Lδ) = ||L(y - μ)||^2

4章 Statistics
相変わらずめちゃくちゃいろんな話題を詰め込んでいる。

  • モーメント法は単純だけど、理論的にはすべてのデータをより効率よく使えるMLEのほうが好ましい。
    • MLEは漸近的に最小分散であることとかが関係してるのかな
    • モーメント法は計算が楽だから、MLEの初期値をモーメント法で算出するのは賢い
  • EWMAなつかしい
    • 式(4.86)がわからん
    • 初期値を補正する式(4.87)知らなかった
  • 正規分布の分散行列のMAP推定とMLEを比較したの、わかりやすかった
    • 高次元になると分散行列の推定は特異になりがち
      • 解決策としてのMAP推定
    • 縮小推定
      • Rigde推定は対角成分にλ'で影響を与える
      • 事前分布にウィシャート(母数S = N*diag(Σ_mle))を使用した場合のMAP推定は対角成分以外を0に近づける
        • 図がわかりやすい。MAP推定の行列のスペクトルはMLEのものより真の分散行列のスペクトルに近い。固有ベクトルは影響を受けない。
  • 経験ベイズ
    • 事後推論はモデルによっては計算が大変なので、何らかの近似を用いる手法が色々ある
    • 経験ベイズはハイパーパラメタを周辺尤度を最適化するように選んだ後、そのハイパラを用いて事後分布の推定を行う。
      • これは、データがありそうなところに事前分布を寄せることになる
      • MLEよりは過学習しにくい。
    • 複数の手法を表にすると以下のようになる。 下にいくほど、よりベイズっぽくなる。
Method Definition
最尤推定 argmax_{θ} p(D|θ)
MAP推定 argmax_{θ} P(D|θ)p(θ|φ)
ML-Ⅱ 経験ベイズ argmax_{φ} ∫ p(D|θ)p(θ|φ) dθ
MAP−Ⅱ argmax_{φ} ∫ p(D|θ)p(θ|φ)p(φ) dθ
Full-ベイズ p(θ, φ| D) ∝ ∫ p(D|θ)p(θ|φ)p(φ) dθ
  • フィッシャー情報量はピーク時での曲率がどの程度きわだっているかを示す
  • バイアスバリアンストレードオフは分類問題ではあまり役に立たないと書いている。。。
    • 理由: バイアスとバリアンスが積の関係で組み合わさっているから
    • うーむ、よくわからん

Ch9: Function Types を読んでいく

イントロ

私は今まで、「関数」というものを、ある時は対応として、ある時はデータ型として扱ってきた。
そんな微妙な扱いをしていた関数は結局のところ何なのかをこの章では明らかにしていく。
関数が射であることは周知の事実であると思うので、今回は特に関数の対象(データ型)としての側面に注目していこう。
また、非常に重要な概念であるHom関手も学ぶ。

9.0 関数は射?それとも対象?

Scalaでは(純粋)関数 ー ここではFunction1[A, B]を考えるー は2つの顔をもつ。

  1. あるデータ型Aとデータ型Bの対応
  2. Function1[A, B]というデータ型

関数を1.の視点で見た時、それはプログラムの圏で言うところの射であり、2.の視点で見た時は対象っぽいだろう。
では、結局、Scalaの関数はプログラムの圏(対象は型で射は純粋関数)において、射であるのか? それとも対象であるのか?
結論から言うと、「関数型Function1[A, B]は対象であり、かつプログラムの圏をPとしたときP(A, B) つまり対象Aから対象Bへの射の集合でもある」。
(データ型は(厳密性を失うことで)集合のように捉えられるのを思い出そう)

例えばFunction1[Boolean, Int]を考えてみる。
下図のBooleanからIntへ伸びる無数の射があり、それをまとめたものがFuction1[Boolean, Int]だ。
(下図では本来圏論では考えない対象のさらに中の要素を考えている事に注意。)
Function1[Boolean, Int]が「プログラムの圏Pの対象」としても、P(Boolean, Int)としても現れている。

TODO: 図

さて、関数が対象でもあるとわかったところで、これから2つの問を考えていく。
1. 関数型は対象として何らかの特別な性質をもつのか? 言い換えるなら、何らかの普遍性をもつのか?
2. ADTのように、何らかの代数的演算と関わりはあるのか?


少しだけ横道にそれよう。
本稿ではプログラムの圏ではhom-setsが対象であるといったが、同様にSet圏もhom-setsが圏の対象として存在する
(局所的に小さな圏を考えていることを思い出そう)

Set圏やプログラムの圏の様に、hom-sets を表す対象を作る方法がある圏もいくつか存在し、その対象をinternal hom-sets(内部hom-sets) と呼ぶ。
一方で、hom-setsが圏の対象として存在せず、外側にある圏もあり、そのような場合hom-setのことをexternal hom-sets(外部hom-sets)と呼ぶ。


9.1 Universal Construction of Function 関数型の普遍的構成

まず、一旦私達が知っている関数型というものは忘れて、関数型(より一般に言えば内部hom-set)を一からデータ型として作成する事を考える。
いつもどおり、Set圏からのアナロジーを考え、そこからアイデアを得ていこう。(当然だが、最終的には他の圏を考えるため集合の性質を使ってはいけない)

関数は入力と出力の対応を表すので、関数型は入力(引数)の型と出力の型の合成型だと考えられる。
そこで、今まで私達が合成型を作ってきた方法である普遍性を用いた構成を行おう。


Universal Construction(普遍性, 普遍的構成)について復習しておくと、ある対象が、それと周囲の(全ての)対象との関係(つまり射)のパターンによって定義づけられているものである時、この構築をUniversal Constructionと呼び、このような性質を普遍性と呼ぶ のだった。
より詳しい説明はCh5.Aにある。


まず、仮に関数f: X -> Y が対象であったなら、それが関わる対象を列挙してみると、{f, X, f(X)}が挙げられる。
次にパターンを見つけるためにそれぞれの対象の関係について考えると、特に 「f(X) はf にX を与えた時の出力」だが、
これは「f と X をある評価機に入れると、f(X)が出てくる関係」と言い換えることが出来る。
この言い換えを図示したものが以下にある。

そして、この視点で考えたときの3要素の関係を、function application(関数適用)とかevaluation(評価) と呼ぼう。
上図のevaluationで結ばれた関係は、直積を用いると evaluation: (f, x) = f(x) の様に表現できる。

これで関数による関係性を対象と射で表現できたので、これを関数型を作るためのパターンとして選択しよう。

関数型の候補となる何らかの型をzとする。
引数の型をa、出力される型をbとするならば、{z, a, b}の組み合わせが出来る。(abを固定したことに注意しよう。)
zの要素f に対しても {f, X, f(X)} のような関係を考えたいのだが、先程の話の通り、zaの積型 z × aを使うことで、
fにx (f∈z, x∈a) を適用する(application)という事を、g: (z × a) -> bで表現できる。

これでパターンが作成できた。


質問コーナー Q. このパターンをつかったuniversal constructionによって関数型をたった一つ選びだせるの?
A. 答えは一般的にはNoだけど、我々の関心の的であるプログラムの圏に限って言えばYes。
(TODO: 選び出せない圏は何?)

  1. 構成のために直積を使ったケド、直積を使わずには構成できないの?
  2. No. 直積がなければ構成はできない。(TODO: 理由)

さて、Set圏はほぼ全ての対象が射で繋がり合っているので、z×aからb(空集合以外)への関数があるようなzが沢山見つかる。
というわけで、これらの候補を何らかの基準でランキングしていこう。
基準としては今までと同じく射があるかどうかで考えていく。
今回私達が興味があるのはz (これが後々関数型になってほしい)なので、イイ感じのh: z' -> zがあるかどうかを基準にしたい。
しかし、今考えなければならないのは p: (z x a) -> b だ。
そのため、積型の関手性を利用して、h: z' -> z を (h, id): (z x a) -> (z' x a) に持ち上げよう。
直積の第2要素は変わらないようにしたいのでid を使用していることに注意してほしい。

TODO: fig

つまり、g' と組み合わせてg を作成できるようなh: z' -> z が一意に存在する時(その時にのみ)、{z', g'}は{z, g}より良いということにする。
式でいうと、以下のような関係が成り立つときだ。

g' = g ∘ (h x id)

この方法で普遍的にbestなものを選び、その対象をa => bと呼ぼう。
この対象もまた自身のapplication(適用): (a => b)×a -> bが存在し、それをevalと呼ぶ。
まとめると、ある{z', g'}が他の全ての関数型の候補z に対し、z のapplicationであるgがevalとh で分解できるならば、{z', g', b}がベストであり、{a => b, eval}と呼ぶ。
(b はすべてのパターンで同じであるため省略した)

定義としてまとめておこう。

定義: 関数対象(冪) function object (Exponential)

aからbへの関数対象は、以下の条件を満たすevalを伴う、対象a => b である。
- eval: ((a => b) × a) -> b
条件
- g: z × a -> bという射を持つ任意の対象zに対して、一意な射 h:: z -> (a => b) が存在し、
- g = eval ∘ (h × id) が成り立つ。

定義終

もちろん、任意の2つの対象の組み合わせに対してa=>bが存在する保証はない。
しかし、Set圏には存在し、Set圏のa=>b はHom(a, b)に同型である。
よって、プログラムの圏においてもFunction1[a, b]は関数対象a=>b とみなせる。

何故、関数対象は冪とも呼ばれるのか。それは後の項で説明する。

9.2 Currying カーリー化

この項では、前項で考えた関数対象のfactorizerについて話す。
factorizerは射影g を受け取り、射h x id を返す関数だ。
(factorizerはCh5.6で出てきている)
が、興味があるのは h x idではなくh なので、g とh の関係を探っていくことになる。

まずは射gの見方を今までと少し変えて、2つの変数z, aを取る関数とみる。(実際、Set圏ではその様に見れる)

  • g: z × a -> b

普遍性から、上のような定義のgに対してそれぞれ一意な射hが存在する。

  • h: z -> (a => b)

ここで、Set圏では a => bは a -> bなので、射h は1つの引数を取ってa からb への関数を返す関数と見ることができる。
このように「関数を返す関数」を一般に高階関数 higer order functionと呼ぶ。
(注意: 実際には高階関数の定義はもっと広い 詳しくはWikipadia参照)

よって、普遍性は「2つの引数を取って1つの値を返す関数」と「1つの変数を受け取り1つの関数を返す関数」との一意な対応を確立する。(g, hを見比べてほしい)
この対応付けをカーリー化 curryingといい、h をg のカーリー化、g をh のアンカーリー化と呼ぶ。
この対応付けは1対1である。なぜなら、任意のgに対して一意なhが存在し、その一方で任意のhに対してg=eval ∘ (h × id)が再構成できるからだ。

カーリー化をScalaで書いてみる。

def curry[A, B, C](f: (A, B) => C): A => B => C =
  a => b => f(a, b)

def uncurry[A, B, C](f: A => B => C): (A, B) => C =
  (a, b) => f(a)(b)

これで、curryは関数対象のfactorizerであることがわかった。

9.3 Exponentials 冪

ADT(代数的データ構造)を扱った時、積型をa*b, 直和型をa+bと表現した事を覚えているだろうか。
実は、関数型も同様に代数を使って表現することができる。

結論から言うと、aからbの関数対象、あるいは内部hom対象は指数(冪) exponential(power)と呼ばれ、abと書く。

其の理由を考えていこう。

考えるヒントとしては、関数をテーブルのようなデータとして捉えることだ。


復習:
普通の型について復習しよう。
例えば、Intはプリミティブ型であり、{2147483647, 2147483646, ...,-2147483648}の集合だと考えられる。その集合の大きさは、2147483648*2=4294967296だ。
(ここで、集合の大きさは「集合に含まれる要素数」だ。)
同様に、Booleanは、{true, false}の集合と考えられる。集合の大きさは2だ。
List[Boolean]は、{[true], [false], [true, false], [false false], ...}の集合と考えれられる。集合の大きさは無限だ。
(Ch6でのADTの議論を思い出してほしい)


例えば、BooleanからIntへの関数は、2種類の入力{true, false}に対して出力{2147483647, 2147483646, ...,-2147483648}を対応させれば良いので、表で書くと以下のようになる。

【Boolean -> Intの関数表】

関数名 引数がtrue 引数がfalse
f1 0 0
f2 0 1
f2 0 2
... ... ...
fn 1 0
... ... ...
f1.8446744e+19 .. ..

1.8446744e+19 = 42949672962である。
なぜ42949672962になるのだろうか?
fn: Boolean -> Intは、純粋関数であるため各入力に対して出力を一つ決めれば良い。
入力がBooleanに属する{true, false}の2通りであり、各入力に対してIntに属する4294967296通りの中から1つを出力として選択するため、(入力がtrueの時の出力, 入力がfalseの時の出力)の全ての組み合わせを計算すると
4294967296 * 4294967296 = 42949672962
となり、それがBoolean -> Intの数となる。
逆に、gn: Int -> Booleanの数は、同様の考えから24294967296になる。
(組み合わせとして、(入力が1の時の出力, 入力が2のときの出力,...)のパターン数を考えよう)
このことから分かるように、
一般に、fn: a -> b Function1[a, b]の対応する代数は、baになる。
これが実際に代数演算に対応しているのかは、後の項で確認する。

TODO: 遅延評価とデータ構造・関数の話

9.4 Cartesian ClosedCategories デカルト閉圏

これまでは基本的にSet圏をデータ型と関数の圏のモデルとして使ってきたが、もう少し広い範囲の圏の族を紹介しておく。

今回扱うのは、Cartesian closed (Categories) デカルト閉(圏)だ。
略してCCCとも言う。

圏C が以下の性質を満たす時、デカルトであるという。
1. Cは終対象を持つ
2. Cの任意の2対象 a, bに対し、Cはそれらの直積 a × b を対象に持つ
2. Cの任意の2対象 a, bに対し、Cはそれらの指数対象(冪対象) ab を対象に持つ
引用元: wikipedia デカルト閉圏

Set圏はこれらの条件を満たすので、デカルト閉だ。
指数は積の反復と考えられるので、任意の対象の数・組み合わせの直積が存在する圏だと解釈することもできる。
また、終対象は零対象との積あるいは任意の対象の0乗と考えられる

さて、なぜここでデカルト閉圏を取り上げたかというと、これが単純型付きラムダ計算のモデルのモデルを提供してくれるからだ。
(単純型付きラムダ計算は、全ての型ありプログラミングの基礎となっている。)

また、圏C がデカルト閉の性質に加え、終対象と積の双対としての始対象と直和を持つとき、デカルト閉 bicartesian closed という。
デカルト閉圏では、以下の演算が可能だ。
1. a × (b + c) = a × b + a × c
2. (b + c) × a = b × a + c × a
(1,2が等しいとは限らないことに注意)
Set圏は、双デカルト閉だ。

補足: デカルト閉だが双デカルト閉ではない圏
TODO: 書く  

CCCや単純型付きラムダ計算は「計算機科学のための圏論の基礎の基礎」が詳しそう。
私はまだ読めていない。難しい...。

9.5 Exponentials and Algebraic Data Types

さてさて、私達は関数型を指数で表現する事を覚えたわけだが、今までのADTの議論から、高校で習った指数に関する数学の法則も成り立っていてほしい。 この項ではそれを確認していく。

9.5.1 Zeros Power

  • a0 = 1
  • Function1[Nothing, a] = Unit
  • Hom(始対象, a) = 終対象

(注: 一番上の代数方程式以外は、=を同型であるという意味で使用している)

a0は、Hom(0, a), Function1[Nothing, a]に対応する。
ch5.3の議論から、そういった関数は1つしか無いため、上の式は成り立っていることが分かる。
因みに、このHom(a, 始対象) = 終対象という式は、始対象・終対象・積の性質しか使っていないので、双デカルト閉圏全てで成り立つ。

9.5.2 Powers of One

  • 1a = 1
  • Function1[a, Unit] = Unit
  • Hom(a, 終対象) = 終対象

ch5.2の議論から、任意の対象から終対象への射はそれぞれ1つしか存在しないので、上の式は成り立つ。
この式はデカルト閉圏全てで成り立つ。

9.5.3 First Power

  • a1 = a
  • Function1[Unit, a] = a
  • Hom(終対象, a) = a

ch5.2の議論から、終対象からの射は何かを1つ選択するというものであると捉えられる。
よって、終対象からの射はコドメインの型に含まれる要素数分だけ存在するので、上の式が成り立つ。
この式は、Set圏(プログラムの圏)の性質を使っているため、デカルト閉圏全てでは成り立たない。

9.5.4 Exponentials of Sums

  • ab+c = ab * ac
  • Function1[Either[b, c], a] = Tuple[Function1[b, a], Function1[c, a]]
  • Hom(b+c, a) = Hom(b, a) × Hom(c, a)

この式を日本語でいうと、「2つの型からなる直和型からある型への関数は、2つの関数の積型と同等である」みたいな感じだろうか。

通常、左辺のようにEither[B, C]を入力とする関数を書く時、以下のように最初にパターンマッチを使うだろう。(出典 プログラミングの基礎)

  def template[B, C](x: Either[B, C]) =  x match {
    case Left(b: B) => ???
    case Right(c: C) => ???
  }

一方、右辺の型は、最初のパターンマッチの後の処理を関数として分離したものだと考えられる。

  def leftf[A, B](b: B): A = ???
  def rightf[A, C](c: C): A = ???

  // val template = (leftf, rightf)

厳密な証明は行わないが、上の式は成り立つことが分かった。

9.5.5 Exponentials of Exponentials

  • (ab)c = ab*c
  • Function1[c, Function1[b, a]] = Function1[Tuple[b, c], a]
  • Hom(c, Hom(b, a)) = Hom(b×c, a)

この式は、カーリー化を冪(関数対象)で表している と解釈できる。
カーリー化・アンカーリー化を行う関数を再掲しておく。
これらは互いの逆像になっているので、上の式が成り立つ。

  def curry[A, B, C](f: (A, B) => C): A => B => C =
    a => b => f(a, b)

  def uncurry[A, B, C](f: A => B => C): (A, B) => C =
    (a, b) => f(a)(b)

  // curry compose uncurry f == f

9.5.6 Exponentials of Products

  • (a*b)c = ac * bc
  • Function1[c, Tuple[a, b]] = Tuple[Function1[c, a], Function[c, b]]
  • Hom(c, a×b) = Hom(c, a) × Hom(c, b)

この式は、値のペアを返す関数は、1つづつ値を返す関数のペアと同等であると言っている。
Scalaで核と以下のようになる。
左辺は、

  //Tuple2[B, C] = (B, C)
  def template[A, B, C](a: A): (B, C) = {
    // some calculation
    val b = ???
    val c = ???
    return (b: B, c: C)
  }

右辺は、

  def f[A, B](a: A):B = ???
  def g[A, C](a: A):C = ???

  def template[A, B, C](f: A => B, g: A => C): A => (B, C) = {
    (a: A) => (f(a), g(a))
  }

9.6 Curry-Howard Isomorphism

別途まとめて記事にする。

Challengeはなし

お疲れ様!
この章はChallengeはない。

参考文献・リンク
- https://ie.u-ryukyu.ac.jp/~kono/lecture/software/Agda/ccc.html
- https://ja.wikipedia.org/wiki/%E3%83%87%E3%82%AB%E3%83%AB%E3%83%88%E9%96%89%E5%9C%8F
- https://www.yumpu.com/en/document/read/13887230/-
- https://m-hiyama-memo.hatenablog.jp/entry/20090827/1251336227
- http://pllab.is.ocha.ac.jp/~asai/book/Top.html  

Ch8: Functoriality を読んでいく

イントロ

前回は、関手(ファンクタ、Functor)の概念や様々な例を学んだ。
今回は、その拡張や仲間を見ていこう。
何故拡張する必要があるのか?
例えば、Either[_, _]のように2つの型でパラメタ化された型はこれまで学んできた関手では表現できない。(関手はF[_]という形だった)
他には、Function1[A, Int]は(共変)関手で表現できるが、Function1[Int, A]は表現できない。(射の対応に注意)

Functoriality, Functrialとは何か?
一言でいうと、何かが関手である(なれる)という事を意味する。

8.0 Functorial(ity) とは

この項では本章のタイトルでもあるFunctoriality について話していく。
ただ、私はまだFunctorialityの正確な定義も日本語訳も見つけられていないため、ざっくりとしたイメージを話すことになる。
これらの正確な定義や日本語訳をご存じの方はぜひ教えてほしい。

おそらく、Functoiral(またはFunctoriality)は日本語で言えば「関手性・関手的」みたいな言葉になると思う。
そして、ここではFuncorialを以下のように理解する。

  • 「ある構成(法)C が Functorial(関手的)である」とは、「元々の関係性に対して構成Cがファンクタ則を満たしている」ことを意味する。

前章でListは関手とみなせる と言ったが、これはまさにListがfunctorialであるということだ。

8.1 Bifunctors

さて、冒頭で述べたように現在我々が持っている関手ではEither[A, B]のようなものは表現できない。
それは、関手が1つの(プログラムの)圏から1つの(プログラムの)圏への対応を考えているからだ。
なので、少しドメインを大きくして、2つの圏から1つの圏への射を考えてみよう。これを、Bifunctor(双関手)と呼ぶ。
f:id:sereronnrot:20210224163645j:plain

これは言い換えると、圏Cと圏Dの直積、C×Dから圏Eへのマッピングを考えている。

f:id:sereronnrot:20210224163704j:plain

  1. 圏Cと圏Dの直積は圏か?
  2. 圏です。
    射は(f, g)で、合成は (f, g) ∘ (f1, g1) = (f ∘ f1, g ∘ g1), idは、 (id, id) TODO: 書く。

f:id:sereronnrot:20210224163733j:plain


双関手のファンクタ則を考えていくときは、圏C×Dから圏Eへのファンクタとみたときのファンクタ則を考えれば良い。
双関手をscalaで定義してみる。

trait Bifunctor[F[_, _]] {
  def bimap[A, B, C, D](f: A => C)(g: B => D): F[A, B] => F[C, D] = 
    first(f) compose second(h)
  def first[A, B, C](f: A => C): F[A, B] => F[C, B] = bimap(f)(identity[B])
  def second[A, B, D](g: B => D): F[A, B] => F[A, D] = bimap(identity[A])(g)
}

ここで、firstsecondが定義されているのはなぜだろうか?
bimapfirstsecondで定義されており、first,secondbimapを使用して定義されているので、「bimap1つ」「firstsecond」のどちらを先に定義しても、もう一方がそれにより自動的に定義されるので、どちらかを実装すれば良いことになる。
これは、圏C×Dの図を見てもらうと分かるように、(f, g) = (f, id) ∘ (id, g)が成り立つことから、bimapもF((f, g) ) = F((f, id) ) ∘ F((id, g) )となり、左辺(bimap)は右辺(first ∘ second)と等しいからだ。

TODO: premonoidal category と Associativity

8.2 Product and Coproduct Bifunctors 直積と直和は双関手

双関手の例を見ていこう。 直積を覚えているだろうか?
忘れた人は、ここを確認してほしい。

もし対象の任意のペアに直積が存在していたら、それら対象から積へのマッピングはbifunctorial(双関手的)であるといえる。
なぜなら、bimapが定義できるからだ。(具体的な実装は後に見ていく)

では、「対象の任意のペアに積が存在している」ということはありうるのだろうか?
少なくともプログラムの圏(Hask, データ型が対象で純粋関数が射の圏)では成り立つ。
(他の圏だとこれが成り立たないものもあるんだろうか?)

では、試しに一番シンプルな積型であるTuple2を双関手にしてみよう。
プログラムの圏をP、特にTuple2のみの圏をTとすると、Tuple2: P x P -> Tと書ける。

implicit val tuple2Bifunctor = new Bifunctor[Tuple2] {
  def bimap[A, B, C, D](f: A => C)(g: B => D): ((A, B)) = {
    case (x, y) => (f(x), g(y))
  }
}

ここでの双関手の働きのイメージは、(,)a b = (a, b)のように型のペアを作る感じだ。

積と直和が双対であるので、直和も双関手だ。

implicit val eitherBifunctor = new Bifunctor[Either] {
  def bimap[A, B, C, D](f: A => C)(g: B => D):
    Either[A, B] => Either[C, D] = {
    case Left(x) => Left(f(x))
    case Right(y) => Right(g(y))
  }
}

(本ではmonoidal category(モノイド圏)に触れているが、言葉が足りないので一旦省略)

8.3 Functorial Algebraic Data Type 関手的代数データ型

私達は前章でパラメータ化されたデータ型(parameterized data types)が関手とみなせる例をいくつか見てきた。
では、ADT(代数的データ構造)はfunctrialだろうか?

この問に答えるために、まずは「どうやったらADTがfunctrialであるといえるか」を整理しよう。
前提として、ADTは簡素な型を直積や直和で組み合わせることによって複雑な型が構成される。
また、関手も合成が可能であり、特に直積と直和は前項で見たように双関手だ。
よって、ADTの基本的な構成物・要素がfunctorialであると示すことができれば、ADTもまたfunctorialであるといえそうだ。

では、ADTの基本的な構成物はどのようなものがあるだろうか?
小さいものから考えると、まず以下の2つが考えられる。

  1. Unit型のように、型パラメタに依存しないもの
  2. Option型Some等の、1つの型パラメータをラップ(カプセル化)したもの

実は、基本的な構成物としてはこれで十分なのである。
なぜなら、2つ以上の型パラメータをラップしたものは、直和や積型を使用して表現が可能であるからだ。
よって、これらがfunctorialであることを確認していこう。


1. Unitがfunctorialである

Unit型は前章の定数関手の項で見たように、関手Unit[_]とみなすことが出来る。  
これはUnit型はfunctorialである、ともいえる。
この時、コドメインの要素は()(あるいは何らかの単一の値)だけであり、ドメインの型パラメタによらない。

また、Unitが関手であることから、それと同型のList型のNilOption型のNoneも関手とみなせる。
NoneNilも、以下のように型パラメータによらない。

// None::Option[_]
val none0:Option[Int] = None
val none1:Option[String] = None
val none2:Option[List[Int]] = None
// Nil::List[_]
val nil0:List[Int] = Nil
val nil1:List[String] = Nil
val nil2:List[List[Int]] = Nil

2. 1つの型パラメータをラップしたものはfunctorialである

さて、Option型のSomeなどはどうだろうか。単一の値をラップしているということは、アンラップ、つまり戻すことも可能であるという事を考慮すると、identity functor(恒等関手)と同型であることが分かる。
注意) ここではラップする際に中の値について何らかの変更を加えるものは想定されていない。何故なら何らかの変更を加えるにはその値の型情報が必要であり、型はパラメタ化されているため決められないからだ。

type Id[A] = A  
implicit val identityFunctor = new Functor[Id] {
    def map[A, B](f: A => B)(x: Id[A]): Id[B] = f(x)
  }

さて、これでADTの基本的な構成物がfunctorialである事がわかった。

この結果を使って、試しにOptionがfunctorialであることを確認してみよう。
Option型の値はNoneSome(a)であるため、これらの直和で構成できるのだった。

// None | Some(a)
sealed trait Option[+A]
case object None extend
case class Some[A](a: A) extends Option[A]

NoneConst ()あるいはUnitと同型であり、SomeIdentityと同型であることを思い出すと、以下のように書ける。

type Option[A] = Either[Unit[A], Id[A]]

よって、OptionはUnit[_] とIdentity[A] の合成であると言えた。

次に、2. 関手2つと双関手は合成が可能である ことを確認する。
具体的には、以下の様な合成方法を採用する。

関手F: A -> C と 関手G: B -> D と 双関手H: C x D -> E を合成したものをH(G, F)とかく。
注意) この表記方法は私が設定した。ちゃんとした記法をご存じの方は教えて下さい。

  • H(F, G)(a, c) = H(F(a), G(c)) a ∈ A, c ∈ B // 対象の対応
  • H(F, G)(f, g) = H(F(f), G(g)) fは圏Aの射 gは圏Bの射 // 射の対応

合成をこの定義にした場合、F, Gの関手であることを仮定した場合ファンクタ則を満たす。


簡易的な証明
圏Aの恒等射id_aと圏Bのid_bは、F, Gによってそれぞれ id_F(a)、id_G(b)に写され、
Hが双関手であることからHによってH(id_F(a), id_G(b)) に写される。
これはまさにid_H(F, G) である。

次に合成則の確認を行う。
j = f ∘ h (jfhは圏Aの射), k = g ∘ i (kgiは圏Bの射)の時、 H(F, G)(j, k) = H(F(j), G(k))
= H(F(f ∘ h), G(g ∘ i))
= H(F(f) ∘ F(h), G(g) ∘ G(i)) // F, Gの関手性
= H(F(f), G(g)) ∘ H(F(h), G(i)) // Hの関手性

よって、H(F, G) は双関手の定義を満たしている。


図で書くと以下のような対応になる。
fig

上図のH(F(f), G(g))をScalaで書くと以下のようになる。

// H(F(f), G(g)) = BiComp
// TODO: 補足説明
// 関手の合成を行った結果がまた双関手である
case class BiComp[BF[_, _], FU[_], GU[_], A, B](v: BF[FU[A], GU[B]])
  implicit def bicompBiFunctor[
    BF[_, _], FU[_], GU[_]](
                           implicit BF: Bifunctor[BF],
                           FU: Functor[FU], GU: Functor[GU]) =
    {
      // partially-applied type BiComp
      type BiCompAB[A, B] = BiComp[BF, FU, GU, A, B]
      new Bifunctor[BiCompAB] {
        override def bimap[A, B, C, D](f: A => C)(g: B => D): BiCompAB[A, B] => BiCompAB[C, D] = {
          case BiComp(x) =>
            BiComp(
              BF.bimap(FU.map(f))(GU.map(g))(x)
            )
        }
      }
    }

とても複雑なコードに見えるが、注目するべきはBF.bimap(FU.map(f))(GU.map(g))(x)が理解できればよい。
新しいデータ型BiCompが双関手であうるのは、fuguが共に関手である場合のみである。

さて、そんなわけで今度こそOptionが双関手であることが分かった。
余談:
前章でOptionが関手である事を等式論証を用いて証明したが、それは不要だったことが分かる。
Optionは2つのfunctorial primitivesの和であるからだ。

TODO: コンパイラで自動で関手かどうか判定する話

8.4 Functors in C++

略。

8.5 The Writer Functor ライター関手

注意) この項は、Ch4を読んでいることを前提としている。飛ばしても良い。

Writer圏を覚えているだろうか?
Writer圏はKleisli圏の一種で、圏の射は通常の関数に何らかの装飾(情報の追加)が合わさったものであった。
まず、定義を復習しよう。

  class Writer[A](val a: A, val log: String) {
    def pure(a: A) = new Writer(a, log="")
    def >=>[B](f: A => Writer[B]):Writer[B] = {
      val w_b = f(a)
      new Writer(w_b.a, log + w_b.log)
    }

    override def toString: String =
      a.toString + "\n" + "="*10 + "\n with log \n" + log + "\n" + "="*10
  }

f:id:sereronnrot:20210224163900j:plain

Writer[_]型コンストラクタはTuple2[_, String]と同型なので関手的である。
では、Writer圏や、より一般にKleisli圏は関手と何らかの関係をもつのだろうか?
まず、Kleisli圏が持つ >=>pure を用いると、以下のようにfmapが作れる事がわかる。

// 実装はWriterで行う  
// シグネチャが正しいか確認してみよう  
// f -> (f, "")   
def fmap[A, B](f: A => B): Writer[A] => Writer[B] = 
identity[Writer[A]] _ >=> (x => pure(f(x)))

簡単そうに見えて、結構複雑な定義である。
流れとしては、identity[Writer[A]]の型コンストラクタは Writer[A] => Writer[A] であり、
(x => pure(f(x)))A => Writer[B]なので、>=> が使用でき、結果的にWriter[A] => Writer[B]が出来る。

よって、Writerは関手とみなせる事がわかった。 更に一般に、Kleisli圏はpureとfmapを持ちファンクタ則も満たすことから関手であることがわかる。
(fmapもpureも実質情報の付与を行っていないため、元の圏の結合律などからファンクタ則が成り立つのは何となく分かると思う)

TODO: parametric polymorphism, Theorem of freeの話

8.6 Covariant and Contravariant Functors 共変関手と反変関手

今まで見てきたWriterを含む殆どの関手は、以下の条件を満たしていた。

  • 条件1: Cの任意の射f, gについて、F(f ∘ g) = F(f) ∘ F(g)

Reader関手も、上の条件を満たしている。

// 今回はIntがドメインのReader関手を作っているが、ドメインは好きなもので良い
type Reader[A] = Int => A
implicit val readerFunctor = new Functor[Reader[A]] {
  def map[A, B](f: A => B)(g: Reader[A]): Reader[B] =
    f compose g
}

ドメインをIntに固定するReader関手(R)のmapは、f: A => Bから、R(f):(Int => A) => (Int => B)であり、 R(A): Int => Aと f ∘ R(A): Int => A => Bという自然な形でR(B)が作成できる。
では、ドメインではなくコドメインを固定したOpという対応を作ってみよう。

  type Op[A] = A => Int
  implicit val opFunctor = new Functor[Op[A]] {
    def map[A, B](f: A => B)(fa: Op[A]): Op[B] = ???
  }

ここで問題が発生する。どう頑張ってもmapが作れない。。。
では、発想を変えて、何だったら作れるだろうかと考えてみると、こんなものが作れる。

def contramap[A, B](f: A => B)(fb: Op[B]): Op[A] = 
  fb compose f

ドメインをIntに固定するOpのcontramapは、f: A => Bから、O(f): (B => Int) => (A => Int)であり、O(B): B => Intと O(B) ∘ f: A => B => Intという自然な形でO(A)が作成できる。

ここで、Reader関手のmapとOp関手?のfmapのシグネチャを比較してみよう。
- Reader.map: (A => B) => Reader[A] => Reader[B]
- Op.contramap: (A => B) => Op[B] => Op[A]

Reader関手は元の圏の射の方向がそのまま受け継がれているが、Op関手?は射の方向を逆にしている事がわかるだろうか。

では、Op関手?の様なものを圏論の言葉で定義していこう。
まず、反対圏の復習をする。(詳しくはCh5.1)

定義: 反対圏 Opposite Category

反対圏 C_opは、圏Cの対象をそのままに、圏Cの射f: A -> Bの定義域(domain)と終域(codomain)を入れ替えたf_op: B -> Aを射とする圏である。
よって、Obj(C) = Obj(C_op) であり、C(A, B) = C_op(B, A)。
合成 ∘op は、 f_op ∘op g_op = (g ∘ f)で与えられる。
また、(C_op)_op = C となる。((C_op)_op)
定義終

Op.contramapは (B => A) => Op[A] => Op[B]と書けるので、圏Cをプログラムの圏とすると、OpはC_opからDへの関手であると言える。(ファンクタ則も満たしている)
Op関手のような関手を反変関手といい、以下のように定義される。

定義: 反変関手 Contravariant Functor

圏Cから圏Dへの反変関手F は、以下の条件を満たす満たす対象、射の対応の組(F1, F2)である。通常、F1,F2を纏めてFと表記する。
F1: Cの対象x -> Dの対象F1(x) への対応
F2: Cにおける射f -> Dにおける射F2(f) への対応
- 条件1: Cの任意の射f, gについて、F(f ∘ g) = F(g) ∘ F(f)
- 条件2: Cの任意の対象xに対して、F(id_x) = id_F(x)
(参考: wikipedia)

条件1が(共変)関手と異なっていることに注意しよう。

f:id:sereronnrot:20210224163949j:plain

また、反変関手FをF: C_op => D、つまりCの反対圏からDへのマッピングとしてみると、普通の関手(共変関手)として扱える。
TODO: 図を書く。

反変関手を定義する型クラスは以下のように書ける。

  trait Contravariant[F[_]] {
    def contramap[A, B](f: B => A)(fa: F[A]): F[B]
  }

これを用いて、Op関手は以下のように反変関手にできる。

  implicit val opContravariant = new Contravariant[Op] {
    override def contramap[A, B](f: B => A)(fa: Op[A]): Op[B] = fa compose f
  }

flip関数を以下のように定義すると、更に簡潔に書けるらしい。(簡潔なんだろうか。。)

  def compose[A, B, C]: (A => B) => (C => A) => C => B = 
    f => g => c => f(g(c))
  def flip[A, B, C]: (A => B => C) => (B => A => C) =
    f => y => x => f(x)(y)
  implicit val opContravariant = new Contravariant[Op] {
    override def contramap[A, B](f: B => A)(fa: Op[A]): Op[B] = flip(compose[A, Int, B])(f)(fa)
  }

ここまでの話を纏めよう。

  • Function1[A, B]Bを固定するとReader関手とみなせ、Aについて共変である。
  • Function1[A, B]Aを固定するとOp関手とみなせ、Bについて反変である。

これは言いかえると、Function1[A, B]は1つ目の型パラメタAに対しては共変であり、2つ目のパラメタBに対しては反変であるといえる。
双関手の記法を用いると以下のように書ける。
Function1: P_op x P => P (Pはプログラミングの圏)

ドメインの直積圏の左側の圏がP_opのように反対圏になっていることに注目してほしい。

8.7 Profunctors プロファンクター

前項で、引数を一つ取って一つの値を返す関数であるFunction1[A, B]型は、1つ目の型パラメタに対しては共変であり、2つ目の型パラメタに対しては反変であることを学んだ。
少し一般化して、2つの圏(C, D)を1つの圏(E) にマッピングする関手Fを考える。
双関手の記法を思い出すと、こういった関手は以下のように書ける。

  • F:: C × D -> E

1つ目の圏C に対して反変にする。

  • F:: C_op × D -> E

この時、圏EがSetならば、以下のように書ける。

  • F:: C_op × D -> Set

この関手Fを、Profunctorと呼ぶ。(Profunctorの訳は?)

プログラムの圏(Hask)の対象は型であり、集合みたいなものだと考えられるので、Profunctorは2つの型パラメタを取る型コンストラクタであると考えられる。
Scalaでは以下のように実装できる。

  trait Profunctor[F[_, _]] {
    // 1つ目のパラメタについて反変であることに注意
    def dimap[A, B, C, D](f: A => B)(g: C => D)(fa: F[B, C]): F[A, D] =
      lmap(f)(rmap(g)(fa))
    // 1つ目のパラメタについて反変であることに注意
    def lmap[A, B, C](f: A => B)(fa: F[B, C]): F[A, C] =
      dimap(f)(identity[C])(fa)
    def rmap[A, C, D](g: C => D)(fa: F[A, C]): F[A, D] =
      dimap(identity[A])(g)(fa)
  }

Bifunctorの時と同じ様に、dimapか、lmaprmapを実装すれば良い。

f:id:sereronnrot:20210224164133j:plain

Function1は以下の様にProfunctorにできる。

  implicit val function1Profunctor = new Profunctor[Function1] {
    override def dimap[A, B, C, D](f: A => B)(g: C => D)(fa: B => C): A => D =
      g compose fa compose f

    override def lmap[A, B, C](f: A => B)(fa: B => C): A => C =
      fa compose f

    override def rmap[A, C, D](g: C => D)(fa: A => C): A => D =
      g compose fa
  }
  import function1Profunctor._
  val f1 = (x: Int) => (x*2).toFloat
  val f2 = (x: Float) => (x*2.5).toString
  val f3 = (x: String) => (x + "!!!").toList

  println(lmap(f1)(f2)(3))
  println(rmap(f2)(f1)(3))
  println(dimap(f1)(f3)(f2)(3))

補足: flipを使った実装
本ではこちらが記載されている。

  trait Profunctor2[F[_, _]] {
    def dimap[A, B, C, D]: (A => B) => (C => D) => F[B, C] =>
       F[A, D] = f => g =>
      lmap(f) compose rmap[B, C, D](g)
    def lmap[A, B, C]: (A => B) => F[B, C] => F[A, C] = f =>
      dimap(f)(identity[C])
    def rmap[A, B, C]: (B => C) => F[A, B] => F[A, C] =
      dimap[A, A, B, C](identity[A])
  }
  implicit val function1Profunctor2 = new Profunctor2[Function1]
   {
    override def dimap[A, B, C, D]: (A => B) => (C => D) => (B
      => C) => (A => D) = ab => cd => bc =>
      cd compose bc compose ab
      override def lmap[A, B, C]: (A => B) => (B => C) => (A =>
         C) =
    flip(compose)
    override def rmap[A, B, C]: (B => C) => (A => B) => (A =>
       C) =
    compose
     }
  import function1Profunctor2._
  println(lmap(f1)(f2)(3))
  println(rmap(f2)(f1)(3))
  println(dimap(f1)(f3)(f2)(3))

ProfunctorはendcoendLensArrowなどの応用先があるが、それはまた本書の後半に扱う。

8.8 The Hom-Functor Hom関手

前項のFunction1の例は、「対象a, bとそれらの間にある射Hom(a, b)のマッピングは、関手(或はProfunctor)である」というより一般的な性質を反映している。
記号的に書くと、Hom-set C(, ) はC_op x C => Set の (Pro)functorということだ。
そんな、「対象a,bとそれらの間にある射Hom(a, b)のマッピング」を、Hom関手 と呼ぶ。

f:id:sereronnrot:20210224164240j:plain

最後に射の関係性を書いてみよう。
C_op × Cの射は以下のような圏Cの射のペアなので、

  • f: a1 -> a
  • g: b -> b1

によるペア(f, g)はHom(a, b)からHom(a1, b1)への射になる。
実際、Hom(a, b)から1つ射hを抜き出した時に、 g ∘ h ∘ fとなり、これはC(a1, b1)の要素である。

Hom関手は非常に重要な関手なので、次の章で重点的に扱う。

TODO: 局所的に小さい県の話

(補足) 関手にならない型コンストラクタはあるのか?

本ではCh10に記載されているが、纏まりを考えてこちらで紹介する。

今まで、関手である型コンストラクタを紹介してきたが、「そもそも関手じゃない型コンストラクタってあるの?」という問に答えていく。
関手じゃないということは、共変でも反変関手でもないということだ。
そんな型コンストラクタは、例えば以下のように作ることができる。

type NotFunctor[A] = A => A

NotFunctor型は、ReaderOp関手を思い出すと、Aに対して共変でもあり反変でもあるようにみえるが、mapcontramapも実装できないので関手にならない。
TODO: 図

8.9 Challenges

Ques 1.
以下に定義されるPairが双関手であることを証明してください。
case class Pair[A, B](a: A, b: B)

Ans 1.
Tuple2と同型なので双関手。
等式論証は省略。

Ques 2.
Option[_]Either[Const[Unit, _], Id[_]]が同型であることを示してください。

type Option[A] = Either[Const[Unit, A], Id[A]]

Hint: Define two mappings between the two implementations. For additional credit, show that they are the inverse of each other using equational reasoning.

Ans 2.
実装の都合上、Const[Unit, A]Const[A]に変更している。

  case class Const[A](v: Unit)
  implicit val constFunctor = new Functor[Const] {
    def map[A, B](f: A => B)(ca: Const[A]): Const[B] =
      Const(ca.v)
  }
  type OptionLike[A] = Either[Const[A], Id[A]]

  def OptionLike2Option[A](a: OptionLike[A]): Option[A] = a match {
    case Left(Const(())) => None
    case Right(a) => Some(a)
  }

  def Option2OptionLike[A](a: Option[A]): OptionLike[A] = a match {
    case None => Left(Const(()))
    case Some(a) => Right(a)
  }
  val opl1:OptionLike[Int] = Left(Const(()))
  val opl2:OptionLike[Int] = Right(2)
  val op1 = Some(5)
  val op2 = None
  println(OptionLike2Option(opl1)) // None
  println(OptionLike2Option(opl2)) // Some(2)
  println(Option2OptionLike(op1)) // Right(5)
  println(Option2OptionLike(op2)) // Left(Const(()))
  assert(op1 == OptionLike2Option(Option2OptionLike(op1)))
  assert(op2 == OptionLike2Option(Option2OptionLike(op2)))

TODO: 等式論証

Ques 3.
以下のようにPreListを定義します。
これは、List型の再帰部分を型パラメタBで置き換えたものになります。
PreListBifunctorインスタンスであることを示してください。
(補足: by recursively applying PreList to itself, you can recover List. くわしくは不動点を学ぶときに解説する)

sealed trait PreList[+A, +B]
case object Nil extends PreList[Nothing, Nothing]
case class Cons[A, B](a: A, b: B) extends PreList[A, B]

Ans 3.
以下のようにしてPreListBifunctorインスタンスに出来る。

implicit val preList2Bifunctor = new Bifunctor[PreList] {
  override def bimap[A, B, C, D](f: A => C)(g: B => D): PreList[A, B] =>
    PreList[C, D] = {
    case Nil => Nil
    case Cons(a, b) => Cons(f(a), g(b))
  }
}

また、Nil, A,BはADTの基本的な構成物であり、PreListはそれらの積和で表現されるため、双関手である。

Ques 4.
これらのデータ型がA, Bの双関手であることを示してください。
TODO: ペンディング そもそもdata K2 c a b = K2 cscalaで書く方法がわからない...

おしまい

参考URL

Ch7: Functors を読んでいく

イントロ

この章では、Functor(関手)を扱う。
我々はこれまで一つの圏の中で「対象同士をつなぐ射」を考えていたが、この章では一つ抽象度が上がり「圏同士をつなぐ何か」を考える。
なので、内容の難しさは上がるが関手は圏論において非常に大事な概念なので、じっくり学んでいきたい。
いわば、この章はPart1の中ボス的なものだ。

7.0 関手を定義する

まずはイメージを膨らませよう

関手は、一言で言うなら「構造を保つ圏と圏のマッピング」を表す。
関手の定義を見ていく前に、まずは2つの事を考えてみよう。

  1. 「圏と圏のマッピング」は、何が必要だろう?
  2. 「(圏の)構造を保つ」とは、どういうことだろう?

1.「圏と圏のマッピング」は、何が必要だろう?

集合と集合のマッピングを表す「関数」は一般に、ドメインとコドメインの間で集合の各要素の対応を考える。
これは、集合がその中の要素で構成されているからだ。


例) 関数f: A -> B, A = {1, 2, 3}, B = {2, 3, 4} は例えば以下のように定義することができる。
- f(1) = 2
- f(2) = 3
- f(3) = 4


このアナロジーを効かせよう。
圏は「対象」と「射」で構成されているので、圏と圏のマッピングは以下の2つがあればよい。

  1. 対象と対象の対応
  2. 射と射の対応

つまり、「圏と圏のマッピング」は2つの対応が必要だということだ。 具体例として、以下のような対応が考えられる。

  1. 圏Cの対象a を圏Dの対象b へ移す写像 F1: a -> b
  2. F1(a) = d
  3. F1(b) = e
  4. F1(c) = k

  5. 圏Cの射f を圏Dの射g へ移す写像 F2: f -> g

  6. F2(f) = l
  7. F2(g) = m
  8. F2(h) = n

図にするとこんなかんじ。

f:id:sereronnrot:20210205034854j:plain

2. 「(圏の)構造を保つ」とは、どういうことだろう?

数学の概念の1つに、「単調増加関数」というものがある。
これは、「入力が増加すると出力も増加するような関数」のことを指す。
言い換えると、「ドメインの大小関係とコドメインの大小関係を保つ」ということだ。


例) f: A -> B, A = {1, 2, 3}, B = {1, 4, 6} が f(x) = 2 * x であるとき、単調関数だ。
何故なら 1 < 2 < 3 であり、f(1) < f(2) < f(3) を満たすからだ。


ドメインとコドメインの「大小関係」を「構造」として着目した時、単調増加関数は「構造を保つ」と言えるだろう。
では、圏にはどのような構造があるかと考える。

圏の定義を復習すると以下の通り。

定義: 圏 Category
圏Cは以下の構成物を持つ
1. 対象: 対象の集まりをobj(C)と書く。
2. 射: 対象の関係を表す。 対象aと対象bの間の射の集合をHom(a, b)やC(a , b)と書く。
3. 合成: 射の合成規則。射f, gが合成可能な場合、g ∘ fも射に含まれる。
射は以下の性質を持つ
1. 結合律: f: a → b, g: b → c, h: c → d が存在するなら、それらに関して h ∘ (g ∘ f) = (h ∘ g) ∘ f が成り立つ。
2. 単位律: 1つ1つの対象xに対して、以下の性質を持つ射が存在する。(これは、xの 恒等射**と呼ばれる)
- 任意の射 f: a -> x及び g: x -> bに対して、
- idx ∘ f = f かつ g ∘ idx = g
定義終

圏の定義をよく見ると、定義の中にある構造は「結合律」と「単位律」である事がわかる。
よって、「建の構造を保つ」ことは「結合律と単位律を保つ」と言い換えられる。
これら2つを保つとは言い換えると以下のようになる。

  1. 結合律を保つ: 入力の圏で成り立つ結合の組み合わせが出力の圏でも成り立つ
  2. 単位律を保つ: 入力の圏で単位射であるものは出力の圏でも単位射になる

これを考慮すると、先程「圏と圏のマッピング」の例として考えたものは構造を保たないことが分かる。
何故なら、圏Cでは h = f ∘ g が成り立つが F2(f)と F2(g)は合成できないからだ。

ここまで考えたところで、関手の定義に移ろう。
圏C, Dがあったときに、関手Fは以下の2つの要素で構成される。

  1. 圏Cの対象a を圏Dの対象b へ移す写像 F1: a -> b
  2. 圏Cの射f を圏Dの射g へ移す写像 F2: f -> g

こうして、関手Fは圏Cの要素を圏Dの要素へマッピングするのだ。
(以降は、F1, F2を両方ともFと記載する。慣習らしい。かんしゅなだけに。 )
とはいっても、圏Cから圏Dへのマッピングなら何でも良いわけではなく、関手であるためには以下の2つの条件を満たす必要がある。

  • 条件① h = g . f の時、 F(h) = F(g) . F(f)

これは言わば、h, g, fの間の関係が保たれていると考えることができる。(プログラムでこの要請がどの様に解釈できるのかは、後で触れる)

  • 条件② F(id_a) = id_Fa 日本語でいうと、対象aの恒等射もまた、aが関手で移された先である対象Faの恒等射に移されることだ。

これらの条件が、関手をただの圏同士のマッピングではなく、構造を保つ特別なマッピングにしている。

【関手の例(単位射は省略)】
f:id:sereronnrot:20210205035304j:plain

関手の定義

ついに、関手(ファンクタ) の正確な定義を記載できる。

定義: (共変)関手 (Covariant) Functor

圏Cから圏Dへの関手F:: C => D は、以下の条件を満たす満たす対象、射の対応の組(F1, F2)である。通常、F1,F2を纏めてFと表記する。また、以下の条件をファクタ則と呼ぶ。
F1: Cの対象x -> Dの対象F1(x) への対応
F2: Cにおける射f -> Dにおける射F2(f) への対応
- 条件1: Cの任意の射f, gについて、F(f ∘ g) = F(f) ∘ F(g)
- 条件2: Cの任意の対象xに対して、F(id_x) = id_F(x)

(参考: wikipedia)

補足: 関手を共変関手と呼ぶことがあるのは、後に反変関手というものが出てくるのでソレと区別するため。
ファンクタ則は全て射に関するものであることに気がつくだろうか。圏論では射が主役だ。

注意点

  • 関手はあくまで「構造を保つ」ものであり、「構造を反映するもの」ではない
    • あくまでドメインの圏の構造を壊さなければ良いので、関手は圏の圧縮・埋め込みに使うことも可能。
  • 関手でドメインの圏を移した先がコドメインの圏の全ての対象・射の全てを覆わなくても良い
    • 例えば 前順序の圏 (Z(整数), ≦) から (R(実数), ≦) への関手を考えても良い。  
  • 関係は保つものの、「関係の意味合い」は保たれないこともある。(その他の話題: 忘却関手 の例を参照)

7.1 Functors in Programming プログラミングにおける関手

プログラムの中で登場する関手はどのようなものだろうか?
プログラムに関係するのはプログラムの圏しか(今のところは)ないので、プログラムに関係する関手も F: プログラムの圏 -> プログラムの圏 であることが分かる。
こういった、ある圏から同じ圏への関手を、自己関手と呼ぶ。
まずは例を見てみよう。

7.1.1 Option Functor オプション型

Optionの定義を覚えているだろうか?

// 再掲
sealed trait Option[+A]
case object None extends Option[Nothing]
case class Some[A](a: A) extends Option[A]

前回は、Option圏論のどの概念にあたるのかは説明していなかったが、今ならそれは可能となる。
前回は特に触れなかったが、Option[+A]という記述に注目してほしい。
詳細には触れないが、ここではOption[_]は、A型を受け取り、Option[A]を作ることができることを覚えておこう。
つまり、Option[_]はそれ単品では使用されず、Int型やString型などと組み合わせてOption[Int], Option[String]等として使用する。
このOptionのような型を他の型でパラメータ化された型なんて言ったりする。
この辺の更に詳しい説明は 7.1.4の説明を見てほしい。

Option[_]は何らかの具体的な型であるAを受け取ってOption[A]を返すものとみなすと、関手になるかもしれない。

まずはF1にあたるものを実装していく。

object Option {
  // F1に相当する
  def apply[A](x: A): Option[A] = if (x == null) {
    None
  } else {
    Some(x)
  }
}

// 様々なデータ型で使える
// Option(4) == Some(4) // Int => Option[Int]
// Option("nep") == Some("nep") // String => Option[String]

例えばx: Intを受け取ったらSome(x): Option[Int]を返すということだ。
これはまさに「プログラムの圏」の対象であるAから「プログラムの圏」の対象であるOption[A]への対応と考えられる。
さて、Option.applyは型を受け取って型を返す写像としてみなすことができたので、次は圏の構造を保ちつつ射f を移せるような写像が定義したい。
なぜならそれが出来ればOptionはプログラムの圏の自己関手であると言える様になる。

// F2に相当する
def map[A, B](f: A => B): (Option[A] => Option[B]) = {
  case None => None
  case Some(x) => Some(f(x))
}

// Option

f:id:sereronnrot:20210205035518j:plain

さて、これで関手としてのパーツは揃ったが、最後にこのパーツで作成されたOptionがきちんと関手の満たすべき法則(ファンクタ則)を満たしているかを確認する必要がある。
次の項では、そのための道具を用意しよう。

7.1.2 Equational Reasoning 等式論証

ファンクタ則を満たしているかを確認するときに、等式論証(Equational Reasoning)を用いる。
これは、Haskellのような関数プログラミング言語ではよく用いられる証明テクニックだ。
等式論証では、数式の変形するときと同じ流れで関数の定義を変形して別の表現を得る。
この方法はHaskellの関数が副作用のない純粋関数であることを利用した方法なので (副作用を考えたら等号を成り立たせるのが大変)、
Scalaの関数の場合でも純粋関数であることを仮定すれば利用が可能である。と思う。

Optionがファンクタ則を満たしているかを等式論証を通して確認してみよう。
ファンクタ則は以下の2つだった。

  • 条件① h = g . f の時、 F(h) = F(g) . F(f)
  • 条件② F(id_a) = id_F(a)

1つづつ確認していこう。
まず、わかりやすい条件②から。scalaでは、id_aは以下のように定義する。

// id_aの定義
def id[A](x: A) = x
// F(id\_a) = id\_F(a)    
// a = Noneの場合  
//注意: F(id\_a) は map(id)に対応する。このFは、射を受け取っているため、実装ではmapが対応することに注意。    
map(id)(None)   
= {mapの定義}  
None  
= {idの定義}  
id(None)  
  
// a = Some(x)の場合  
map(id)(Some(x))  
= {mapの定義}  
Some(id(x))  
= {idの定義}  
Some(x)  
= {idの定義}   
id(Some(x))  

これで、条件②の等式論証が完成した。
次に条件②の証明をしていく。

// h = g . f の時、 F(h) = F(g) . F(f)  
// a = Noneの場合   
map(g compose f)(None)    
= {mapの定義}  
None  
= {mapの定義}  
map(g)(None)  
= {mapの定義}  
map(g)(map(f)(None))  
= {composeの定義}  
(map(g) compose map(f))(None)
  
// a = Just(x)の場合    
map(g compose f)(Just(x))    
= {mapの定義}    
Just((g compose f)(x))  
= {composeの定義}  
Just(g(f(x)))  
= {mapの定義}  
map(g)(Just(f(x)))  
= {mapの定義}  
map(g)(map(f)(Just(x)))  
= {composeの定義}    
(map(g) compose map(f))(Just(x))    

長かった...。とはいえ、これでようやくOptionがファンクタであることが証明できた。

7.1.3 Optional

C++でOptionを作っている。
あまり興味がないので省略。

7.1.4 Typeclasses 型クラスとその周辺

さて、ScalaでFunctorの一種であるOptionを作れたので、今度は他のものを...と考えたくなるが、その前にFunctorそのものをScala等のプログラム言語で実装していこう。
まずは、そのために理解するべき仕組みがいくつかあるのでさらっていく。
ただまぁここをちゃんと見なくても全体のざっくりとした理解は出来るかもしれない。

  1. Type Class 型クラス
  2. Type Constructor 型コンストラク
  3. Higher Kinded Type 高カインド型

1. Type Class 型クラス

型クラスは、Scalaの公式ドキュメントCatの公式ドキュメントこのサイトの説明が詳しい。

型クラスとは一言でいうと、それに属する型が備えるべき振る舞いを定義した共通のインターフェース のことだ。
型クラスは型のグルーピングに使える。

例えば、「2つのオブジェクトが同じかどうか判定するメソッドを備える」というインターフェースを規定する型クラスEqは以下のように書ける。

// 型クラス(trait) Eqに属する型は、===: (A, A) => Booleanを実装する    
trait Eq[A]{
  def ===(x: A, y: A): Boolean
}

ここで、あくまでインターフェースを定義しているだけで、具体的な実装は実際に実装する型ごとで異なることに注意してほしい。
特定の型が型クラスに属するということは以下のように書ける。
型Aが型クラスBに属しているということを、「AはBのインスタンスである」という。

case class Point(a: Float, b: Float)

implicit val pointEq = new Eq[Point] {
  // 具体的な実装  
  def equal(x: Point, y: Point): Boolean = {
    x.a == y.a && x.b == y.b
  }
}

型クラスを使用することで、アドホック多相性を実現することが出来る。
アドホック多相性の定義をWikipadiaから引用する。

定義: アドホック多相性

関数や演算子の多重定義のように、同じ名前で型の異なる引数に適用できて、その振る舞いは引数の型によって違うような関数の多相性のことをアドホック多相という。
引用元

アドホック多相性を感じるために、更に下にコードを記載する。
ここでは、Pointクラスに加えて、Point3Dクラスを作成している。

// 2つの名前の異なるくらすをていぎ
case class Point(a: Float, b: Float)
case class Point3D(a: Float, b: Float, c: Float)

// 作成したクラスを、`Eq`型クラス(trait)のインスタンスにする  
object implicits {
  implicit val pointEq = new Eq[Point] {
    // 具体的な実装  
    def equal(x: Point, y: Point): Boolean = {
      x.a == y.a && x.b == y.b
    }
  }

  implicit val point3dEq = new Eq[Point3D] {
    // 具体的な実装  
    def equal(x: Point3D, y: Point3D): Boolean = {
      x.a == y.a && x.b == y.b && x.c == y.c
    }
  }

}

// おまじない 説明書くかも
import implicits._

この様な準備の元、以下のような関数を実装できる。
1つのequal関数を異なる型の引数で実行できる事に注目しよう。
この実装のequalEqインスタンスである全ての型で実行ができる。

// 多相性関数
def equal[A](a: A, b: A)(implicit eq: Eq[A]):Boolean = eq.equal(a, b)

// 同じ名前の関数を異なる型を引数にとり実行できる
println(equal(Point(2, 3), Point(2, 3))) // true
println(equal(Point(3, 3), Point(2, 3))) // false
println(equal(Point3D(2, 3, 3), Point3D(2, 3, 3))) //true
println(equal(Point3D(3, 3, 4), Point3D(0, 2, 3))) //false

(implicit関連の文法は(説明する技量がないので)省略するかなあl。。。
公式ドキュメントやコップ本などを参照してほしい・・・。 )

その他の多相性については以下の記事がわかりやすい。
- https://qiita.com/matarillo/items/4870bb974f7a1900ef7c

2. Type Constructor 型コンストラク

注: ここ見ればおしまいだったかも...わかりやすい https://qiita.com/KtheS/items/649fbffcef18c74430f8

関数が「値を受け取り値をかえすもの」であるならば、型コンストラクタは「型を受け取り型をかえすもの」といえる。

**定義: 型コンストラク

型コンストラクタは1つ以上の型引数を取り、十分な引数が与えられたときデータ型を生成する。すなわち、型コンストラクタはカリー化により部分適用をサポートしする。
引用元 Wikipedia)

例として、Either型を紹介する。
Either[A, B]型は「AB型どちらかの値」を意味する型だ。

Either型は以下のように定義される。

// Either[_, _]はA,B 2つの型を受け取る
sealed trait Either[+A, +B] 
case class Left[A](v: A) extends Either[A, Nothing]
case class Right[B](v: B) extends Either[Nothing, B]

// Either[_, _] 型コンストラクタにInt型とString型を与え Either[Int, String]型を受け取る
val tmp: Either[Int, String] = Left(2)
val tmp: Either[Int, String] = Right("nep")

さて、いくつか似たような言葉が出てきているので整理しよう。(ここらへんめっちゃわけわからんくなってた)

  • Either型 ... 型だ。(特にfirst-order type(一階型)と呼ぶ) val e: Either = 〇〇の様には使えないだ。
  • Either[_, _] ... 型ではない。型コンストラクタだ。 A, Bの2つの型を受け取りEither[A, B]を返す。
  • Either[A, B]型 ...型だ。 val e: Either[A, B] = 〇〇の様に使える

通常、Eitherと言ったらEither型を指すんじゃないかなぁ。
Eitherが一階型と呼ばれるのはなぜか。

Either[A, B]val e: Either[A, B] = 〇〇の様に使えると話したが、この様に「インスタンス化することで値を得られる型」をproper type(固有型?)と呼ぶ。
Int(1, 2, 3等をインスタンスに持つ)やString("A", "bbb"等をインスタンスに持つ)も固有型だ。

では、Eitherはどうかというと、インスタンスとして直接は値を持たない。
Either[_, _]型コンストラクタを通してEither[A, B]のような固有型を下にもつ。
よって、EitherInt等の固有型より抽象度が上がっているといえる。
この意味でEither型は一階型と呼ばれる。

TODO: 型クラスと型コンストラク

3. Higher Kinded Type 効果インド型

ようやく3つ目にこれた...

高カインド型は一階型の拡張と言える。
固有型が「下に値を持つ型」で、
一階型が「下に固有型を持つ型」であるなら、
高カインド型は「下に一階型や高カインド型を持つ型」だ。


補足:高階関数と高カインド型

同じ様な話で、高階関数という概念がある。
これも、普通の「値を受け取り値を返す関数」を一階関数と呼び、
「関数を受け取り関数を返すような関数」を高階関数と呼ぶ。
(正確には引数か出力が関数を含めばよい)

一階型を「(型コンストラクタによって)型を受け取り型をかえすもの」とするならば、
ある意味で型の関数とみなすことが出来るだろう。
それなら、一階型を引数にとって一階型を返す高カインド型は高階関数に対応するものと考えられる。


高カインド型は例えば以下のように定義できる。
例えば、Option[_]List[_]等をまとめた「コンテナ型」を作りたいとする。
(この例はhttps://twitter.github.io/scala_school/advanced-types.html#higherを参照した)

// 高カインド型であるContainerを定義する。  
trait Container[M[_]] {
    def put[A](x: A): M[A]
    def pop[A](m: M[A]): A
}

// 一階型であるListを受け取ってContainer[List[_]]型を返す
val cl = new Container[List] {
  def put[A](x: A): List[A] = List(x)
  def pop[A](l: List[A]):A = l.head
}
println(cl.put(2)) // List(2)
println(cl.pop(List(12))) // 12

// 一階型であるSeqを受け取ってContainer[Seq[_]]型を返す
val cs = new Container[Seq] {
  def put[A](x: A):Seq[A] = Seq(x)
  def pop[A](s: Seq[A]):A = s(0)
}
println(cs.put("nep")) // Seq("nep")
println(cs.pop(Seq("noire"))) // "noire"

new Container[List]に注目しよう。
これはListの要素の型は指定していない。Container[List[_]]を返すということだ。
これはまさに高カインド型としての性質だ。

これでようやく関手を定義するための知識が整った。
休憩を取ろう。

Functorの定義

ここまで学んできた機能を使って、ScalaFunctor型を以下のように書ける。
他の型でパラメータ化された全ての型が、Funcotorの候補になるということだ。

// higher kinded type 
// ざっくり説明: Functorに属する型F[A]は、Aに関わらず同じmapを実装している。  
// 前述のEq traitが型に対して実装するものであったのに対して、
// Functor traitは、 Option[X]やList[X]などの型クラスを取る型クラスのため、
// 関数でいうところの高階関数のようなものになっている。  
trait Functor[F[_]] {
  def map[A, B](f: A => B)(fa: F[A]): F[B]
}

補足: ここで、「あれ、Functor Fは本来(F1, F2)の組だったよね?F1は?」と思った方。確かに...。
Optionの例では明示的にF1にあたるapplyを書いた様に、Option等の他の型を受け取る型は定義するときにapplyを実装出来る。
よって、それに合わせてFunctorを作る(mapを実装する)ことになるため、Functor traitにはmapのみが含まれている。と何処かで聞いた。

なお、このFunctor traitはあくまでmapを実装することを養成しているだけで、ファンクタ則を満たすよう強制するものではない。
ファンクタ則の確認は等式論証等を用いる必要がある。

7.1.5 Functor in C++

FunctorをC++で実装する話が書いてある。
省略。

7.1.6 List Functor リスト関手

Listは以下の様にFunctorのインスタンスに出来る。
言い換えるなら、「Listは関手とみなせる」。

sealed trait List[+E]
case object Nil extends List[Nothing]
case class Cons[E](h: E, t: List[E]) extends List[E]

object List {
  // F1の例
  // 実際にScalaで実装されているものとは大きく異なることに注意
  def apply[A](x: A): List[A] = if (x == null) {
    Nil
  } else {
    List(x)
  }
}

implicit val listFunctor = new Functor[List] {
// F2
def map[A, B](f: A => B)(fa: List[A]): List[B] = fa match {
case Nil => Nil
case Cons(x, t) => Cons(f(x), map(f)(t))
}
}

// Int -> List[Int]
// [1, 2, 3] => [f(1), f(2), f(3)]

7.1.7 Reader Functor リーダー関手

ここまで見てきたFunctorとはちょっと毛色が違うものが出てくる。
Scalaやその他の言語では、関数もデータ型の一つとみなされる。
例えばIntからStringの関数はInt => StringあるいはFunction1[Int, String]と表記される。
更に一般的にすると、A型からB型への関数はA => B型となる。
他の型でパラメータ化された全ての型がFunctorの候補になるということは、関数(function)も候補になるだろうか?

A => BA,Bの2つの型でパラメタ化されているが、ひとまずBInt固定したものを考えよう。
(Aを固定したパターンやA``Bの2つを固定したパターンは(暫く)後に触れる)
型で言えばA => Intを考えるということだ。

実装例をいかに乗せる

type FromInt[A] = Int => A

implicit val fromIntFunctor = new Functor[FromInt] {
  // F2
  override def map[A, B](f: A => B)(fa: FromInt[A]): FromInt[B] = {
    f compose fa
  }
}
object FromInt {
  // F1
  // あくまで形式的に実装しただけ
  def apply[A](a: A): FromInt[A] = (x:Int) => a
}


val twice = (x: Int) => (2*x).toString
val times10 = (x: Int) => (10*x).toString
val string2chars = (x: String) => x.toList

println(string2chars("nep")) // List(n, e, p)

val string2charsfunctor = fromIntFunctor.map(string2chars)_ 

println(string2charsfunctor(twice)(100)) // List(2, 0, 0)
println(string2charsfunctor(times10)(100)) // List(1, 0, 0, 0)

正直あまりコレの使い所がわからないと思う。
使用例はモナドを学ぶときに紹介するので、ここでは一旦、関手の例の一つとして考えてほしい。

実際、役割的には普通の関数と同じっぽい(https://stackoverrun.com/ja/q/7932549)

7.1.8 Either Functor イーザー関手

Either[A, E]のように、2つの型パラメータを持つ型でも、どちらかを固定したものは関手となれる。

  sealed trait Either[+A] // E = Stringに固定
  case class Left[A](v: A) extends Either[A]
  case class Right(v: String) extends Either[Nothing]

  implicit val eitherFunctor = new Functor[Either] {
    def map[A, B](f: A => B)(fa: Either[A]): Either[B] = fa match {
      case Left(a:A) => Left(f(a))
      case Right(v) => Right(v)
    }
  }

7.1.8 Const Functor 定数関手 と Unit型  

まず、定数関手の定義を以下に記載する。

定義: 定(数)関手

圏 Dの対象 X について、任意の圏 C から D への X が定める定関手(constant functor)を以下のようにして構成できる:
C の全ての対象を X に写し、C の全ての射を X の恒等射に写す。定関手は selection functor ともよばれる。
引用元 wikipedia

例えば圏Cから圏Dへの定数関手Constとして以下のようなものが考えられる。
注意) id_zのみ明示的に書いてある。
fig

関手の注意点で「あくまでドメインの圏の構造を壊さなければ良いので、関手は圏の圧縮・埋め込みに使うことも可能。」と話したが、定数関手が圧縮の極端な例だ。
ドメインの圏にある対象・関係を全てある一つの対象とその単位射へ移しているからだ。

Scalaでは例えばStringへの定数関手を以下のように定義できる。

case class Const[A](v: String)

object Const {
    // F1 具体的な文字は自由 どんな文字にしても同型
    def apply[A](a: A): Const[A] = Const("nep")
  }

implicit val constFunctor = new Functor[Const] {
  def map[A, B](f: A => B)(ca: Const[A]): Const[B] =
    Const(ca.v)
}

println(Const(3)) // Const("nep")
println(Const(List("nepgear", "uni"))) // Const("nep")

val twice_const = constFunctor.map((x: Int) => x*2)_ 
println(twice_const(Const(3))) // Const("nep")

Const関手はコドメインの対象(値)がvによらず1つだけだ。
この様に、属する値が1つだけの型でもっと有名なものを私達はすでに知っている。そう、Unit型だ。
以下のように定数関手としてのUnit関手を定義することができる。

  sealed trait Unit[+A] // +をつけないといけない理由
  object a extends Unit[Nothing] // ()はすでにつかわれているので、a で代用  

  object Unit {
    def apply[A](v: A): Unit[A] = a
  }

  implicit val unitFunctor = new Functor[Unit] {
    def map[A, B](f: A => B)(ca: Unit[A]): Unit[B] = a
  }

println(Unit(3)) // ch7$a$@7cf10a6f == a
println(Unit(List("nepgear", "uni"))) // ch7$a$@7cf10a6f == a 
println(unitFunctor.map((x: Int) => 4*x)(Unit(2))) // ch7$a$@7cf10a6f == a

Constと比較してほしい。両方とも同じことをしていることが分かる。

定数関手は今後の章で非常に重要な役割を担う。

7.1.9 Identity Functor 恒等関手

恒等関手は名前の通り、ドメインの圏の対象と射をそっくりそのままコドメインに移す。
恒等関手はあらゆる圏においても定めることが出来る関手だ。

定義: 恒等関手 Identity Functor

圏C の恒等関手は圏C から圏C への関手であり、以下のF1, F2から構成される。
F1: 圏C (ドメイン)の対象a を 圏C (コドメイン)の対象aへ移す
F2: 圏C (ドメイン)の射f を 圏C (コドメイン)の射fへ移す
定義終

単位射が圏論で重要なように、恒等関手もまた圏論では非常に重要な概念だ。

Scalaでは以下のように定義できる。

type Id[A] = A

implicit val idFunctor = new Functor[Id] {
  def map[A, B](f: A => B)(aid: Id[A]) = f(aid)
}
object Id {
  def apply[A](a: A): Id[A] = a
}

val id3: Id[Int] = 3
val twice = (x: Int) => x*2
println(twice(3)) // 6
println(idFunctor.map(twice)(id3)) // 6

7.2 Functorsって結局なんなn(?)

7.A Functorを見る視点 で詳しく扱う。

7.3 Functor Composition 関手の合成

今まで色々な関手を見てきたが、今度はそれらを合成すること、つまり関手の合成について考えていく。
圏C と圏D をつなぐ関手Fと圏Dと圏Eをつなぐ関手GがあったときにG ∘ Fは関手になるだろうか。

結論から言うと、G ∘ Fを以下のように定義すると、圏C と圏Eをつなぐ関手になる。
- G ∘ F(a) -> G*1 // 対象の対応
- G ∘ F(f) -> G(F(f)) // 射の対応

イメージ図 f:id:sereronnrot:20210205035824j:plain


簡易的な証明
圏Cの恒等射id_a は 関手Fによって圏D の恒等射id_F(a)に移され、
それが更に関手G によって圏E の恒等射id_G(F(a)) = id_(G ∘ F)(a)に移される。
これによりファンクタ則の1つ目が満たされる。

圏Cの射f とg がg ∘ f のように合成可能な時、関手Fによって移されたF(f) とF(g) は F(g) ∘ F(f) = F(g ∘ f) を満たす。(Fのファクタ則)
それらが更に関手G によってG(F(f)) と G(F(g))に移されるが、 F(f) とF(g) が F(g) ∘ F(f) の様に合成可能であるため、
G(F(g)) ∘ G(F(f)) = G(F(g) ∘ F(f)) を満たす。(Gのファンクタ則)
また、F(g) ∘ F(f) = F(g ∘ f) から(G ∘ F)(g) ∘ (G ∘ F)(f) = G(F(g)) ∘ G(F(f)) = G(F(g ∘ f)) = (G ∘ F)(f ∘ g)であるため、ファンクタ則の2つ目が満たされる。

よって、G ∘ Fは関手。


では、これがプログラミングでどう現れるのか。
例えばList[_]Option[_]を合成したList[Option[_]]]の様なネストされたデータ構造を使いたくなる場面とかはよくあると思う。
Scalaコードで書くと以下のような感じになる。

// 便宜上、標準ライブラリのOption, Listを使用している
object implicits {
  implicit val listFunctor = new Functor[List] {
    // F2
    def map[A, B](f: A => B)(fa: List[A]): List[B] = fa match {
      case Nil => Nil
      case x::t => f(x):: map(f)(t)
    }
  }
  implicit val optionFunctor: Functor[Option] = new Functor[Option] {
    def map[A, B](f: A => B)(fa: Option[A]): Option[B] = fa match {
      case None    => None
      case Some(a) => Some(f(a))
    }
  }

  // こんなイメージのものがホシイ
  // implicit val listofoptionFunctor: Functor[Option[List]] = ??? 
}

import implicits._
val listoption: List[Option[Int]] = List(Some(1), Some(2), Some(3), None, Some(10))

// こういうのがやりたい
val twice = (x: Int) => x*2
// listofoptionFunctor.map(twice)(listoption)

listofoptionFunctor.mapは正しくList関手とOption関手を合成した関手のmapだ。
なお、listoptiontwiceを適用するには、以下のようにすればいい。

listFunctor.map(optionFunctor.map(twice))(listoption) // List(Some(2), Some(4), Some(6), None, Some(20))

scalaのcatsではlistofoptionFunctorにあたるものを作る機能が実装されており、以下のように使用する。
(具体的な実装方法は難しいので省略 いつかわかりたい)

import cats.Functor
import cats.implicits._
listofoptionFunctor = Functor[List].compose[Option]

7.A Functorを見る視点

さて、これまで関手の定義やら具体例を見てきたわけだが、結局関手って何なんだろう。
Scala with Catsこのノートでは以下の様な視点が紹介されている。 1~3はnotesから、4はCatsから引用した。

  1. 関係を保つ対応付けとしての関手: 関手は対象間の関係を重視し保つマッピング
  2. 操作を保つ対応付けとしての関手: 関手は構造の操作とそれらの合成を重視し保つマッピング
  3. 誘導されたマップ(関数, 射)を定義する関手: すでに存在するマップ(関数, 射)から新たに誘導されたマップ(関数, 射)を定義する一貫した方法
  4. 文脈を付与する方法としての関手: ある文脈の元での連続した操作を表現出来るようにするための抽象化を提供する方法

1が一番抽象的でどの状況にも当てはまりそうな気がする。
プログラムで関手を使う場合は3, 4の理解がしっくりくるだろうか?

それぞれ、どんな場合にその視点がうまくハマるか、例をみていこう。

関係を保つ対応付けとしての関手

この章の最初の方に、以下のような単調関数の例を出した。


例) f: A -> B, A = {1, 2, 3}, B = {1, 4, 6} が f(x) = 2 * x であるとき、単調関数だ。
何故なら 1 < 2 < 3 であり、f(1) < f(2) < f(3) を満たすからだ。


圏でも同じ様なものがある。

例) (X, ≦)と(Y, ≦)が前順序の圏(対象aと対象bがa ≦ bの場合に aからbへの射がある圏) とする。
この時、関手F: (X, ≦) -> (Y, ≦) が存在した時、以下のようなことが言える。
- 圏Xにおいて対象a, bの間で a ≦ b であった場合、 圏Yにおいて F(a) ≦ F(b) 。...①
この例では、まさに圏Xでの関係ー今回は前順序関係ーがFの行き先においても保たれていることが分かる。

また、逆に、①を満たすような圏から圏へのマッピングF': (X, ≦) -> (Y, ≦) が存在した時、以下のようなことが言える。
- ①を満たしている場合、X(x, x) = {id_x} かつ Y(y, y) = {id_y} であるため、F(id_x) = id_y を満たす。
- 合成則も同様。
このことから、前順序圏の間の関手はまさに単調写像とどう問うものであることもわかる。

ドメインの圏(Y, ≦)が(X, ≦)より多くの関係をもっていても良いことに注意しよう。あくまで、ドメインの関係が保たれていれば良い。
- x ≦ y が成り立たない(射なし)場合に F(x) ≦ F(y) であってもよい。
- どのxでもF(x) = y にならない y がからむ(順序)関係はあってもなくてもよい。

操作を保つ対応付けとしての関手

圏を見る視点として、「操作としての圏」を紹介したのを覚えているだろうか。(ここ)

例2) G = (R, +)、H = (R, *)をそれぞれ群とする。
この時、群の圏BG, BHの間に以下のように定義した圏のマッピングを考える。
- F1: ☆ -> ☆ (BGのただ一つの対象をBHのただ一つの対象に対応させる)
- F2: x -> exp(x) (指数変換)

これが関手の定義を満たしていることを確認する。
1. BGにおける単位射は0 (和における単位元)であり、 BHにおける単位射は0だが、F(0) = exp(0) = 1 だ。
2. BGにおいて x ∘ y = hの時 x + y = hだが、 exp(x + y) = exp(x) * exp(y)であり、これは exp(x ∘ y) = exp(x) ∘ expを満たし F(x ∘ y) = F(x) ∘ F(y)を満たす。

これで指数変換を表現するFが関手であることが確認できた。
この様に、ドメインの操作がコドメインの操作にきちんと対応付けられるような変換(正式には準同型写像)は関手とみなすことが出来る。

例3) 線形変換の例
重要なので今度書く

誘導されたマップ(関数, 射)を定義する関手

誘導されたとはどういうことか。
ここでは、「ある g が f から誘導された」とは、「g が f によって定義されている」とする。
ここで、g のドメインやコドメインは f と異なっていても良い。

例4) List関手
List関手は、 f: X -> Y を List.map(f): List[X] -> List[Y] に移すが、
定義としては lx: List[X] = [x1, x2, x3, ..., xn] を ly: List[Y] = [f(x1), f(x2), f(x3), ..., f(xn)]に移す。
よって、 List.map(f)は明らかに f から誘導されていると言える。
(関数f を「複数の可能な入力を受け取り全てにf を適用したものを出力する関数」に移す)

例5) 確率関手 (分布関手)
以下のような関手P: Set -> Set を定義する。
- F1: 集合x を 有限の台の確率測度 (確率分布と言い換えても良さそう) へ対応させる。
- F2: f: x -> yを P(f): P(x) -> P(y)へ以下のように対応させる。(測度の押し出し)
p ∈ PX、(P(f))(p) ∈ PYのとき、
(P(f))(p)(y) := sum(p(x) | x ∈ f^-1(y))

雑にいうと変数変換がf にあたり、確率変換後の分布と変換前の変数の分布の関係を表すのがP(f)だ。

文脈を付与する方法としての関手

文脈とはなにかというのは言葉で説明するのは難しい。 なので、今まで見てきた例を、まだ紹介していないものも含めて改めて列挙してみる。

【関手の例】
- List
- Option
- Either (どちらかの型パラメータを固定)
- コドメインを固定した関数
- Future 並列処理に用いるデータ型
- Tree 木構造
- Const 定

こうしてみると、ある程度一般的なコンテナのような型が多いが、全てではないことが分かる。
ただ、Listであれば元の型に「複数の〜」という文脈が加わり、Optionは「失敗するかもしれない」だったり、
Futureは「将来得られるかもしれない」などの文脈が加わっている事がわかる。
このことから、Functorは、受け取った型に何らかの文脈を付け足すものと解釈できることが分かる。

また、更に関手は合成則を保つことから、元の型において 「fを適用した後にgを適用する」という行為が
そのまま関手を適用した後も成り立つ事がわかる。
このことから、関手は「連続した操作を表現している」とみなせる。

7.B 関手としての可換図式

以前、可換図式の定義を以下のようにしたことを覚えているだろうか。

定義 図式 Diagram
圏Cの可換図式は圏Cの(全部・或いは一部の)対象をノード(点)、射をエッジ(矢印)としてもつ有向グラフである。 可換図式は以下の特徴を持つ。
a. 各対象・射は図式に複数回現れる事ができる。
b. 2つの対象の間で複数の射が存在することができる。
c. 図式内の任意の対象Xに対して、それぞれに対応する恒等射idxは図式内では明示的に書かれない
d. 図式内の射(矢印) f: X -> Y, g: Y -> Z の合成射 g ∘ f は図式内には明示的に書かれない
定義終

これを、もう少し圏論ぽい言葉で定義してみよう。

定義: 図式 Diagram
圏Cと圏I を考える。 関手F: I -> C を圏C上のI型の図式と呼ぶ。
定義終

つまり、圏について考えるときに図式を通して考えるときに、私達は関手をつかって圏Cから移されたものを見ているといえる。

TODO: 可換図式、薄い圏

いつかかく 7.C 関手でないもの

いつかかく

いつかかく 7.D 関手を使って見る圏

いつかかく

7.F その他の話題

忘却関手

何らかの構造を忘れ去らせるような関手を忘却関手と呼ぶ。
まずは例を見たほうが早いと思う。

例) 以下の2つの圏を考える。

  • 圏C:
    • 対象: List[_]の型
    • 射: ある関数f: A -> Bを用いてmapf: List[A] -> List[B] = [f(a1), f(a2), ...]の様に書ける関数
  • 圏D:
    • 対象: List[_]の型
    • 射: List[A] -> List[B]の形をした全ての関数

この時、以下の様な関手F: C -> D が考えられる。
- F1: 同じものを対応させる
- F2: 同じものを対応させる
では、この関手は情報を何も落としていないと言えるだろうか?
圏C, Dを比較すると、圏Cの射(構造)として、「fmapfで表現できる(要素ごとの関数を用いて表現できる)」というものがあった。
しかし、圏Dの射(構造)にそれはない。
言い換えると、ある関数gが圏Cの射だとわかった時には「要素ごとの関数を用いて表現できる」と分かる一方で、
圏Dの射だとわかってもそれは言えないという点で、関手Fによって圏Cの情報が落とされている(圏Dができる)といえる。
この時、Fを忘却関手だ。

(お気持ち的な)定義: 忘却関手 Forgetful functors
圏D と、「圏Dの対象に何らかの追加の構造を加えた圏」である圏C を考える。
この時、この付加的な構造を無視・消し去るような関手F: C -> D を忘却関手と呼ぶ。
定義終

例2) 関手F: Top -> Set を考える。
(Top: 位相空間の圏)
- Fが、対象の対応として、位相空間(X, O) をその台集合Xへ対応させる関手であるとき、位相を忘れさせる忘却関手。
- Fが、射の対応として、連続関数f を (ただの)関数f' (注: 内容は変わらない。ただ普通の関数と見るだけ)へ対応させる関手である時、連続性を忘れさせる忘却関手。

2つのことがいえる。
- 忘却関手の行き先のほうが構造がゆるいため、ドメインの圏より多くの射を持つことが多い(連続関数ではない関数がたくさんある)
- 同じ様なカテゴリの忘却関手は複数あることがある。(同じ集合に様々な位相空間が入れられる。位相空間と集合は多対1で、それだけ様々な忘却関手が考えられる)

圏論の概念の中には「構造」や「構造を保つ」「構造を忘れる」といった言葉に関係しているものも多い。
忘却関手はそういった概念を説明する場合によく用いられる。

圏が対象で、関手が射の圏について

圏と圏の関係性を記述する関手という道具を手に入れた今、
圏を対象とし関手を射とした圏を考えたくなるかもしれない。
が、説明の都合上Ch10まで待ってほしい。
気になる人はCh10まで...

7.G いつか書く Catsで関手を扱う

いつかかく

7.4 Challenges

  1. Can we turn the Option type constructor into a functor by defining (i) which ignores both of its arguments? (Hint: Check the functor laws)
// (i)
def map[A, B](f: A => B)(oa: Option[A]): Option[B] = None

(i)を見ると、どんな入力に対してもNoneを返す関数のようだ。
ヒントの通り、ファンクタ則を確認してみる。

// 条件① F(id\_a) = id\_F(a)を確認    
// a = Some(x)の時    
map(id)(Some(x))  
= {(i)より}  
None  
  
一方で、  
id(Some(x))  
= {idの定義}  
Some(x)  
より、条件①を見たさない。  

以上の結果より、この定義ではOptionは関手にならないことが分かる。

  1. Prove functor laws for the reader functor. Hint: it's really simple.
    関数の合成則から明らか。

  2. Implement the reader functor in your second favorite language (the first being Haskell, of course).
    TODO: やる

  3. Prove the functor laws for the list functor. Assume that the laws are true for the tail part of the list you’re applying it to (in other words, use induction).

問題文の通り、帰納法を使用する。
まずは、条件①から確認していこう。

// 条件① F(id\_a) = id\_F(a)    
// a = Nilの時  
map(id)(Nil)  
= {mapの定義}  
Nil  
= {idの定義}  
id(Nil)  
  
// a = Cons(v, ta)の時    
// taが条件①を満たすと仮定する。    
map(id)(a)  
= {mapの定義}    
Cons(id(v), map(id)(ta))    
= {仮定: taは条件①を満たす}  
Cons(id(v), ta)  
= {idの定義}  
Cons(v, ta)  
= {idの定義}  
id(Cons(v, ta))  
id(a)   
  
taがNilの場合は場合は条件①が成り立つことを確認しているので、  
全てのListで条件①が成り立つことが分かる。(補足: 言い換えると、Listの要素数が0のときは条件①が成り立つことを確認し、要素数がn-1つの時に条件①が成り立つと仮定した上で要素数がnの時にも条件①が成り立つと確認した。よって、要素数1のときも条件は成り立ち、それにより要素数2のときも成り立ち...とずっと続いていく。)  

条件②も同様に確認する。

// h = g . f の時、 F(h) = F(g) . F(f) 
// a = Nilの場合  
map(g compose f)(Nil)  
= {mapの定義}  
Nil   
= {mapの定義}  
map(f)(Nil)  
= {mapの定義, map(f)(Nil) = Nilであるため}  
map(g)(map(f)(Nil))  
= {composeの定義}  
(map(g) compose map(f))(Nil)  

// a = Cons(v, ta)の場合  
// taが条件②を満たすと仮定する。   
map(g compose f)(Cons(v, ta))  
= {mapの定義}  
Cons((g compose f)(v), map(g compose f)(ta))   
= {仮定より}    
Cons((g compose f)(v), (map(g) compose map(f))(ta))  
= {composeの定義}  
Cons(g((f)v), map(g)(map(f)(ta)))  
= {mapの定義}    
map(g)(Cons(f(v), map(f)(ta)))    
= {mapの定義}  
map(g)(map(f)(Cons(v, ta)))  
= {composeの定義}  
(map(g) compose map(f))(Cons(v, ta))
taがNilの場合は場合は条件②が成り立つことを確認しているので、  
全てのListで条件②が成り立つことが分かる。  

お疲れ様!

*1:a

Ch6: Simple Algebraic Data Types を読んでいく

イントロ

前章では、普遍性による定義の一例として、始対象や終対象、そして直積と直和を学んだ。
この中でも特に直積と直和は「2つの要素を組み合わせてつくる要素」の様に考えられる。
実際、scalaでは以下のように実装できるのだった。

// 積
// A, Bは具体的な型 (Int, Float)等
(A, B)

// 余積(直和)
Either[A, B]

そして、日常的なプログラミングで使用される基本的なデータ構造の中には、この2つのメカニズムだけで構築できるものも多い。
こういったデータ構造の大きなメリットの一つは、データ構造の多くの性質が、合成可能であることだ。
例えば、IntやString等の基本型の比較方法(equality等)がわかっている時、
それらを積や直和型へ一般化する方法がわかれば、多くの合成型の比較方法が自動的に導出できる。
特に、直積型の直和型やそれを再帰的に定義したものを、代数的データ型と呼ぶ。

まずはプログラミングにおける直積型と直和型を詳しく見ていこう。

6.1 Product Types (直)積型

イントロ部で書いた様に、scalaでは積型はタプル、つまり(A, B)またはTuple[A, B]で表現される。
ここで、(A, B)(B, A)は異なる型であるが、違いはどちらを前に持つかだけなので、実質同じものを表現していることに注意しよう。
(こういった関係を圏論では同型という言葉を使って表現するのだった)
実際、以下のような関数が定義できる。

// A, Bには具体的な型が入る
def swap[A, B]: ((A, B)) => (B, A) = {
  case (x, y) => (y, x)
}

2つの型の積が出来たので、今度は2個以上の積の型も作ろう。
3つの型の積は(A, B, C)Tuple[A, B, C]と書き、2つの型の積を使って作成した以下の型と同型だ。

((A, B), C)
(A, (B, C))
def alpha[A, B, C]((A, B), C) => ((A, (B, C))) = {
  case ((x, y), z) => (x, (y, z))
}

def alpha_inv[A, B, C]: ((A, (B, C))) => ((A, B), C) = {
  case (x, (y, z)) => ((x, y), z)
}

def beta[A, B, C]: ((A, B, C)) => ((A, B), C) = {
  case (x, y, z) => ((x, y), z)
}

def beta_inv[A, B, C]: (((A, B), C)) => (A, B, C) = {
  case ((x, y,) z) => (x, y, z)
}

ここで、AとBの積型は、2つの型を受け取って1つの型を返す、二項演算子として見ることができるので、A * Bと表すことにしよう。
すると、「( )の中の計算を優先すること」と「=の意味は同型を除いて同じである」と約束をすると、先の性質は以下の式で表せる。

  • (A * B) * C = A * (B * C)

この式の形は、形式上は我々が日常で使う代数の掛け算と同じである。
そんなわけで、もう一つの掛け算の法則であるa * 1 = aに登場するような1に対応するような型が欲しくなってくる。

ここで、a*1について考えてみると、a * 1=aであることから、1との積は何も変化を与えない(a*1とaは同じとみなせる)と解釈できる。
では、scalaでは、Bがどんな型だったら、(A, B)とAが(同型を除いて)同じものとみなせるだろうか?
答えは、Unit型である。

def rho[A]: ((A, Unit)) => A = {
  case (x, ()) => x
}

// Unit型は ()しか存在しないため、xがあれば(x, ())以外のパターンはない
def rho_inv[A]: A => (A, Unit) = x => (x, ())

このことから、Unit型が代数の1 (単位)に対応していることが分かる。

6.2 Records あるいは構造体

タプルが各要素に対して要素の入っている順番(番号)を指定してアクセスしていたが、case classを用いることで各要素に対して名前でアクセスすることが出来る。
case classは以下のように宣言し使用する。

case class Pair[A, B](a: A, b: B)

val pair_instance = Pair(1, 2)

// .a や .b等、予め決められた名前でアクセスする
// pair_instance.a == 1
// pair_instance.b == 2

Pair(A, B)と同型。
(名前と添字が一対一で対応するため)
case classは他の言語では構造体等と呼ばれることが多い。

6.3 Sum Types 直和型

Ch 6.1では、積型について考えてきたので、次は直和型について考えていく。
以前調べたように、直和型はscalaではEither型で表現される。
Either型の定義は以下の通り。

// A, Bには具体的な型が入る
// Either[Int, Int], Either[Int, Float]等が実際の型になる
sealed trait Either[+A, +B]
case class Left[A](v: A) extends Either[A, Nothing]
case class Right[B](v: B) extends Either[Nothing, B]

積型(Tuple)と同じ様に、左右の型を入れ替えたものや、ネストする順番を変えたもの同士は同型。
また、以下のように3つの直和型を作れる。

sealed trait OneOfThree[+A,+B,+C]
case class Sinistral[A](v:A) extends OneOfThree[A,Nothing,Nothing]
case class Medial[B](v:B) extends OneOfThree[Nothing,B,Nothing]
case class Dextral[C](v:C) extends OneOfThree[Nothing,Nothing,C]

さて、直和型も二項演算子として見ることができるので、AとBの直和をA + Bと表すことにしよう。(なぜ積型は*, 直和型は+で表すのかは、後にわかる。)
すると、代数のa + 0 = aという式から、直和型の0にあたるものを見つけたくなってくる。
いきなり答えを言うと、scalaでは0に当たる型はNohingである。
なぜかと言うと、Either[A, Nothing]の値について考えた時、Nothing型の値は存在しないため、必ずA型の値になるのでA + 0 = Aが成立することになるからだ。

さて、ここからは色んな直和型を見ていこう。

Option型

値が無い可能性を含む型を、Option型を使用して以下のように表現することができる。
Option型は、A型とUnit型の直和型と同型だ。

sealed trait Option[+A]
case object None extends Option[Nothing] //Unit型の代わり。 ()にあたる
case class Some[A](a: A) extends Option[A]

// あるいは、 以下の方法でも良い。Unitは、値を得られなかったことを示す
/
type Option[A] = Either[Unit, A]

Enum(列挙)型

ところで、シンプルな(直和)型は結局の所、そこに属する値の集合とみなせる。
そう考えると、Enum(列挙型)もある種直和型の一種であると考えることができる。

sealed trait Color
case object Red extends Color
case object Green extends Color
case object Blue extends Color

List型

Listは、直和型と直積型の組み合わせで作成することができる。
標語的には、「直積の直和型」だ。

// Listは Either[Cons, Nil]のようなもの  
sealed trait List[+A]
case object Nil extends List[Nothing]
// Consは直積型
case class Cons[A](h: A, t: List[A]) extends List[A]

TODO: Immutableの話

ListとOptionを使った関数として、例えば以下のようなものが考えられる。

def maybeTail[A]: List[A] => Option[List[A]] = {
case Nil => None
case Cons(_, t) => Some(t)
}

TODO: その他本に書いてること

6.4 Algebra of Types 型の代数

これまで、直和型と積型を見てきたが、以下のような点がまだ不明瞭だと思う。

  • 代数的データ構造って、結局何が代数的なの?
  • なんで、代数で置き換えた時に積型は*, 直和型は+で置き換えたの?

この疑問に答えていこう。
まず、今まで私達はデータ型の性質を代数に置き換える時、積型を * に、 直和型を + にしていた。
すると、代数の以下の性質もデータ型で成り立ってほしいと考えるだろう。

  1. a * 0 = 0
  2. a * (b + c) = a * b + a * c

1. a * 0 = 0の(ざっくりとした)確認

aがA型とし、0はNothing型とする。(直和型のときの議論を思い出そう)
直積型としてTupleを使用すると、以下のような対応を得られる。

  • a * 0 -> Tuple[A, Nothing]
  • 0 -> Nothing
  • よって、 a * 0 = 0 -> Tuple[A, Nothing] = Nothing ... ①

さて、①式は成り立つ(同型を除いて同じという意味で)であるだろうか?
答えはYesである。

Nothing型は実際の値を持たない空集合のようなものと考えられ、
Tuple[A, Nothing]の値は(a, n) ,a ∈ A, n ∈ Nothingと考えられるが、
Nothingに属するnは存在しないため、(a, n)も存在しないことになる。( (a, n)はa,nが共に無いと作れない)
よって、両方とも空集合的なものと考えられるため、①式は成り立つと言える。

2. a * (b + c) = a * b + a * c の(ざっくりとした)確認

a, b, cをそれぞれA, B, C型とし、 直積型としてTuple, 直和型としてEitherを用いると、以下の対応を得られる。
- a * (b + c) -> Tuple[A, Either[B, C]]
- a * b + a * c -> Either[Tuple[A, B], Tuple[B, C]]
- a * (b + c) = a * b + a * c -> Tuple[A, Either[B, C]] = Either[Tuple[A, B], Tuple[B, C]] ... ②

②式は成り立つだろうか?
答えはYesである。
②式の左辺は (a, b or c)であり、 a, b, cはそれぞれA, B, Cの要素である。
そして、つまるところそれは(a, b)か(a, c)のどちらかだ。
これはまさに②式の右辺と等しい。
実際に、以下のように対応を取る関数を作れる。

// TODO 作る

これで、代数の一部の性質が積や直和といったデータ型の置き換えでも成り立つことが分かった。
ところで、今までは主にa, b等の抽象的な変数をデータ型で置き換えてきた。
では代数の 1 + 1 = 2や、2 * 3 = 6、1 + aのような式があったときに、これらをデータ型で置き換えることはできるのだろうか?

データ型
0 Nothing
1 Unit
2 = 1 + 1 ???
3 = 1 + 2 ???
2 * 3 = 6 ???
a + b Either[A, B]
a * b Tuple[A, B]
1 + a ???

まず、2 = 1 + 1から考えていこう。
1はデータ型でUnitであるので、1 + 1はEither[Unit, Unit]であることが分かる。

次に、3 = 1 + 2を見ていく。
1はデータ型でUnitであり、
2は上で見たようにEither[Unit, Unit]と考えられるので、
3はEither[Unit, Either[Unit, Unit]]と考えられる。

2 * 3 = 6はどうだろうか?
2はEither[Unit, Unit]であり、
3はEither[Unit, Eihter[Unit, Unit]]なので、
6はTuple[Either[Unit, Unit], Either[Unit, Either[Unit, Unit]]]と分かる。(長くてごめんね)
表を埋めると以下のようになる。

データ型
0 Nothing
1 Unit
2 = 1 + 1 Either[Unit, Unit]
3 = 1 + 2 Either[Unit, Either[Unit, Unit]]
2 * 3 = 6 Tuple[Either[Unit, Unit], Either[Unit, Either[Unit, Unit]]]
a + b Either[A, B]
a * b Tuple[A, B]
1 + a ???

ここで、最後に1 + aを考えていく前に、表の左右を見比べてみよう。
数とデータ型で、どのような関係があるだろうか?
0とNothing、1とUnitという組み合わせに共通点を考えてみると、0はNothing型である値の数1はUnit型である値の数(より一般には濃度)であることが分かる。(Nothing型の値は存在せず、Unit型の値は()だけだ)
Either[Unit, Unit]型である値の数は、左側のUnit型の値である場合と右側のUnit型である場合の2通りを合計した1 + 1 = 2であり、引き続き関係は成り立つ。

また、2 * 3もまた、 対応するデータ型である値の数で有ることが分かる。
よって、a + bをA, B型で置き換えた時、aをA型の値の数、bをB型の取りうる数と考えているといえる。

最後に、1 + aについて考えてみると、データ型ではEither[Unit, A]、あるいはOption[A]と考えられる。
Option[A]は、A型の値か何も得られないということを表す値を返すので、この型である値の種類は1 + (A型の値の数)であり、1 + aを解釈することが出来る。
最後に、完成させた表を記載する。

データ型
0 Nothing
1 Unit
2 = 1 + 1 Either[Unit, Unit]
3 = 1 + 2 Either[Unit, Either[Unit, Unit]]
2 * 3 = 6 Tuple[Either[Unit, Unit], Either[Unit, Either[Unit, Unit]]]
a + b Either[A, B]
a * b Tuple[A, B]
1 + a Either[Unit, A] = Option[A]

ここまで話して、ようやく最初のギモンに答えられる。(TODO: もうちょうちゃんと書く コンストラクタの話とか?)

    1. 代数的データ構造って、結局何が代数的なの?
    2. Ans. データ構造を考えるときにアナロジーとして代数的演算を考えられるため、代数的データ構造と呼ばれる。
    1. なんで、代数で置き換えた時に積型は*, 直和型は+で置き換えたの?
    2. Ans. 積と直和を混ぜた計算をするときに、代数的アナロジーを成立させるためにはそうする必要があった。

さて、代数的データ構造のよくある例として、Listを考えてみよう。
Listは以下のように定義されるのだった。

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[A](h: A, t: List[A]) extends List[A]
// または、 Either[Unit, Tuple[A, List[A]]]

これを代数の方程式で表すと以下のようになる。
- x: List[A]
- x = 1 + a * x

ここで、1はNil (またはUnit型、実質())で、 a * xはCons(A, List[A])(またはTuple[A, List[A]])に対応する。
この代数の方程式を解いてみる。

x = 1 + a * x
{右辺のxは左辺のxと等しいため、右辺のxに 1 + a * xを代入 }
x = 1 + a * (1 + a * x) = 1 + a + a*a*x
{再度同じことをする}
x = 1 + a * (1 + a (1 + a * x)) = 1 + a + a*a + a*a*a + a*a*a*a
{同じことをし続ける}
x = 1 + a + a*a*a + a*a*a + a*a*a*a + ...

方程式を解いていくと、最終的に積の無限和になった。    これは、Listが空の積型(1)、要素が1つ積型(a)、は要素が2つの積型(a*a),要素が3つの積型(a*a*a),,,の無限和であると解釈できる。    (仮に無限大のメモリがあれば、要素数が無限のリストを作ることもできるだろう)
この様に、方程式を解いていくことで代数的データ型は異なった見方での解釈が可能になる。

6.A 代数的データ型の補足

TODO
書く

参考
http://toriike.ic-blog.jp/toroii/2020/02/post-7fa3.title

何で走っているのだろう: Scalaでの代数的データ型のしくみと使い方

6.5 Challenges

1 . Option[A]Either[Unit, A]が同型であることを示してください。

Ans.
以下のように、Option[A]Either[Unit, A]を相互に変換する関数が実装できる。

def either2option[A](e: Either[Unit, A]): Option[A] = e match {
    case Left(()) => None
    case Right(a) => Some(a)
}

def option2either[A](o: Option[A]):  Either[Unit, A]= o match {
    case None => Left(())
    case Some(a) => Right(a)
}

また、Option[A]NoneSome(A)をとり、Some(A)の取りうる値はAの取りうる値と同じであるため、Option[A]の取りうる値の数は1+Aと表現できる。
同様に、Either[Unit, A]UnitAをとるが、Unitが取りうる値は()のみであるため、これも1+Aと表現できる。

2 . ~ 4. C++Javaで実装しろ系の問題なので今回は割愛(pythonやRustでやるのはいいかもしれない)

5 . a + a = 2 * aが(同型を除いて)、型で成り立つことを示してください。(2はBooleanと同等であることを思い出そう)

Ans . a + a は aaの直和型だ。
scalaではEither[A, A]と表記できる。
対して 2 * a は 2 と a の直積型だ。
問にあるように、2 はBooleanと同等であるため、scalaでは(Boolean, A)と表現できる。
よって、Either[A, A](Boolean, A)が同型であることを示せれば良い。

def either2tuple[A](e: Either[A, A]): (Boolean, A) = e match {
    case Left(a) => (true, a)
    case Right(a) => (false, a)
}

def tuple2either[A](t: (Boolean, A)): Either[A, A] = t match {
    case (true, a) => Left(a)
    case (false, a) => Right(a)
}

either2tupleEihter[A, A]Left(Boolean, A)の内、(true, A)を対応させ、Right(false, A)を対応させている。

おしまい!