ともちんの Tech ブログ

Scala プログラマのための圏論入門 (2) 型と関数の圏

Scala 圏論 関数プログラミング

はじめに

本記事では、Scala を構成する型と関数の圏である Scala 圏 (Hask 圏とも呼ばれます) について紹介します。まず、なぜ型が必要なのかについて述べ、型と関数を圏として考えていきます。

f:id:tomoki0606:20201110140816p:plain
型と関数の圏 Hask

前回の記事

taretmch.hatenablog.com

なぜ型が必要なのか

型付けには、静的な型付けと動的な型付けがあります。静的型付けは、変数や関数の引数、返り値などの型がコンパイル時のような実行前に定められるシステムです。一方で、動的型付けは、実行時の実際の値によって型が定められるシステムです。

動的型付け言語では、型のミスマッチは実行時に発見されます。一方で、静的型付け言語では型のミスマッチはコンパイル時に発見され、実行前にプログラムが文法的に正しいかどうかチェックすることができます。

Scala や Haskell、C++ のような言語は静的型付け言語です。静的型付け言語を採用することによって、文法エラーや型ミスマッチに対応しやすくなります。

型を集合として解釈する

最も直感的な型の解釈は、型が値の集合であることです。例えば、型 Boolean は値 true と false の集合です。型 Char はすべての Unicode の文字の集合です。

型を集合として解釈すると、x が Int 型であることを宣言するとき

val x: Int

と書きますが、これは x は整数集合の要素であると解釈できます。

しかし、型を集合として解釈するには微妙な点が少々あります。一般に、集合全体の集合を定義することはできません (ラッセルのパラドックスが一例)。そのため、循環定義を含む多相関数 (polymorphic function) を集合で表すことは難しくなります。

そこで、代わりに集合の圏 Set を用いて型を表現します。 Set は、集合を対象とし、関数を射とする圏です。 Set を用いて型を表現すると、関数プログラミングにおける関数は（数学的な）集合間の関数とみなせます。

とすると、またまた問題が生じます。集合間の関数は入力に対して値を出力するだけで、なんらかの処理を実行するわけではありません。一方で、プログラミングの関数は入力に対して出力値を計算するので、その内部で処理を実行します。出力を有限ステップで計算できるのであれば良いのですが、再帰を含む関数では実行が終了しない場合があります。したがって、関数の実行が終了しない場合の出力の型が未定義となってしまいます。

ある関数の実行が終了するかどうかは判定することができない (停止問題) ので、実行が終了しない場合の型をボトム型 (bottom type) ⊥ として定義します。scala では ??? で代替して表現できます。ボトム型の値は終了しない計算です。すなわち、以下のように定義されている関数

val f: Boolean => Boolean

は true、 false を返すか、実行が終わらない場合は ⊥ を返します。

val f: Boolean => Boolean = x => ???
// f: Boolean => Boolean = <function1>
val fTrue: Boolean => Boolean = x => true
// fTrue: Boolean => Boolean = <function1>
val fFalse: Boolean => Boolean = x => false
// fFalse: Boolean => Boolean = <function1>

ボトム型を返す関数は部分関数 (partial function) と呼ばれます。scala だと PartialFunction として定義されています。

純粋関数

一般的に、プログラミング言語における関数と数学的な関数は異なる意味を持ちます。プログラミング言語における関数は、入力に対して計算を実行し結果を出力しますが、データベースへの保存やグローバル変数の変更など、副作用を持つ場合があります。一方で、数学的な関数は、ただ値から値をマッピングするもので副作用は考慮されません。

プログラミング言語において、副作用を持たず、同じ入力に対して同じ出力を返す関数を純粋関数 (pure function) と言います。このように同じ入力に対して必ず同じ出力を返す性質は、参照透過性 (referential transparency) と呼ばれます。

f:id:tomoki0606:20201110141246p:plain
純粋関数と参照透過性

例えば、与えられた整数に +1 した値を返す関数

val inc = (n: Int) => n + 1
// inc: Int => Int = <function1>

は、どんな整数 n に対しても n+1 を返すので、純粋関数です。

Haskell のように、関数全てが純粋関数である純粋関数型言語では、言語の意味論が与えやすいという利点があります。関数の出力には表れない計算効果についても、モナドという概念を導入すれば純粋関数で表現できるようになります。

モナドについて議論するにはまだ道具が足りないので、入念に準備をしたあとに議論することにします。

型の例

型は、集合として解釈できると言いました。

ここでは、型と集合の具体的な対応関係について見ていきます。

空集合と Nothing 型

まずは空集合についてです。空集合は要素を1つも持たない集合のことですが、これは何の型に対応するのでしょうか？要素、つまり値を1つも持たない型は、Scala においては Nothing 型にあたります。これらの型は値を持たないので、Nothing 型を引数とする関数を呼び出すことはできません。

def g: Nothing => Int = _ => 1

f:id:tomoki0606:20201110141345p:plain
空集合と Nothing 型

シングルトン集合と Unit 型

次に、シングルトン集合についてです。シングルトン集合は、値を1つだけ持った集合です。値を1つだけ持つような型は、Scala では Unit 型にあたります。Unit 型を引数として持つ関数は、引数としてダミーの値を受け取ります。つまり、Nothing と異なり引数なしでいつでも呼び出すことができます。そのような関数が純粋関数である場合は、常に同じ値を出力します。

f:id:tomoki0606:20201110141350p:plain
シングルトン集合と Unit 型

次のような関数 f44 は、任意の入力に対して必ず Int 型の 44 を返します。

scala> val f44: Unit => Int = _ => 44
f44: Unit => Int = $Lambda$4600/58014670@35989557

scala> f44(())
res4: Int = 44

Unit 型を返り値の型に指定すると、その関数は Unit 値を返します。純粋関数である場合は出力値を得られないので、引数をただ廃棄する関数になります。例えば、以下の関数はいかなる Int 型の値を受け取っても Unit を返します。

val fInt: Int => Unit = x => ()

fInt(1)

fInt(100)

任意の型に対して同じ式で実装できる関数は、パラメータ多相 (parametrically polymorphic) であるといいます。パラメータ多相な関数は、型変数をあらゆる具象型によって置換できるので、非常に便利です。

2要素集合と Boolean 型

最後は、2要素集合についてです。2要素集合は、値を2つだけ持った集合です。2要素集合は、Scala では Boolean 型にあたります。

scala> sealed trait Boolean
defined trait Boolean

scala> case object True extends Boolean
defined object True

scala> case object False extends Boolean
defined object False

まとめ

  • ボトム型を導入することによって、型を対象とし、関数を射とみなす圏を考えることができる。
  • 純粋関数は、副作用を持たず、同じ入力に対して同じ出力を返す関数のことである。
  • 純粋関数が持つ、同じ入力に対して同じ出力を返すような性質のことを参照透過性と呼ぶ。
  • 集合と型の対応
    • 空集合は Nothing 型に対応する。
    • シングルトン集合は Unit 型に対応する。
    • 2要素集合は Boolean 型に対応する。

参考文献