ScalaのF[_]と高カインド型を完全に理解していく

はじめに

Scalaはなんとなく書けるようになったけどライブラリコードとか読めないし、関数型はもっとわかない。
特にF[_]みたいなやついっぱい出てくるけどなに？みたいな人に捧げる記事です。

このようなものは高カインド型などと呼ばれ、なかなか理解が難しいものです。
型のさらなる抽象化の旅に出ましょう。

これはUnderstanding F[_] in Scalaの日本語訳です。

F[_]とかいうすごい抽象的なシンタックスはScalaのあちこちで目にします。
これを直感的に理解して、その意味と使い方がわかるようになりましょう。

Overview

この記事の目標はこのシンタックスがなぜ必要か理解することです。
そのために抽象化のはしごをだんだんと上り、次のような疑問に答えていきます。

valueとは？
proper typeとは？
first-order typeとは？
first-order typeの抽象化とは?
なぜF[_]が必要なのか？

What is a value?

valueとは生データのことです。
抽象化においては最も低い段階にあり、非常に扱いやすい概念です。

val name = "daniel"
val one = 1
val oneAndTwoAsTuple = (1,2)
val oneAndTwoInAList = List(1,2)

この例の右側を見てください。
ただのデータでバカバカしいほどに理解しやすいでしょう。

子供があなたが着ているビッグパンダのtシャツの値段を聞いてきたとしましょう。
$12と答えると彼らは簡単に理解するでしょう。
彼らは答えた数字をvalueとして確かに理解しているはずです。
けどドルって何？っと聞いてきたとするといきなり事は複雑になります。
金や貨幣といったものを説明するのはちょっと骨が折れます。
ここで必要となるのが型です。

What is a proper type?

scala> val name = "daniel"
name: String = daniel

scala> val one = 1
one: Int = 1

scala> val oneAndTwoAsTuple = (1,2)
oneAndTwoAsTuple: (Int, Int) = (1,2)

scala> val oneAndTwoInAList = List(1,2)
oneAndTwoInAList: List[Int] = List(1, 2)

REPLの出力を見ると型について教えてくれます。
String、List[Int]などなど。
これらはproper typeです。

proper typeとはvalueよりは上位の概念です。
どのような関係性があるか見てみましょう。
型はvalueを生み出すためにインスタンス化でき、逆にvalueは型の特定のインスタンスです。

Stringは思いつく限りあらゆるstringリテラルを生み出すことができます。("a", "ab", "algorithmic service operations"など)
上述の金額の例では$は$2、$3、$49,000,000…などにインスタンス化できます。

proper typeを考えることで、抽象レベルが上がりました。
もっと抽象度を上げるとどうなるのでしょう？

What is a first-order type?

前の例ではList[Int]がproper typeだと言いました。
しかしそれではListとは何でしょう？

scala> val l: List = List(1,2,3)
<console>:12: error: type List takes type parameters
       val l: List = List(1,2,3)
              ^

これはコンパイルできません。
valueがListであることをコンパイラが許可してくれないのです。
コンパイラは私達に何らかのリスト、つまりList[_]みたいな感じで宣言してほしいのです。

そのためのスロットが一つあります。
型がほしいのならスロットになにかを入れなければなりません。
これは型を返す関数へのパラメータみたいなものです。
このような関数にはtype constructorという名前がついています。

Option[_]やArray[_]、Map[_,_]といったtype constructorを見たことがあるでしょう。
Mapだけが少し違うことに気をつけてください。
これはkeyとvalueのための２つの型パラメータが必要です。

ListやMap、Arrayなどのfirst-order typeはただの型です。
ただしそれらはList[_]やArray[_]といったtype constructorを持ちます。
type constructorはproper typeを受け取り、List[int]やMap[String, Int]などのproper typeを生み出します。

proper typeからfirst-order typeへとより一層抽象度が上がりました。
殆どのプログラミング言語ではこれ以上の抽象化は不可能です。
しかし、Scalaではもうちょっといけます。
最後の一歩を踏み出し、どのな世界が待っているか見てみましょう。

What abstracts over a first-order type?

これまでの抽象化はその一つ前のステップを抽象したものでした。

List("a") -> List[String] -> List           -> ???
// value     proper type     first order type  ???

Scalaではfirst-order typeを次のやり方で抽象化できます。

trait WithMap[F[_]] {
}

F[_]に集中するために一旦WithMapを忘れましょう。
F[_]は一つだけスロットの空いたfirst-order typeのことです。
例えばList[_]やOption[_]。

さあここで非常に難しい質問です。: WithMapは一体何のことでしょう？

答え: second-order type

つまりこれは型を抽象化した型を更に抽象化したものと言えます。

きっと夢の中で夢を見る映画のインセプションのような多重構造を感じていることでしょう。
希望がもてるのはここまであなたがついてきていることです。
すべての解決までもう少しです。

Higher kinded types

もう一つ言葉を紹介して、全てを説明しようと思います。

type constructorを持つ型([_]がつくような型のことです)はhigher kinded typeといいます。
type constructorは型を受け取り型を返すただの関数です。

型と関数の共通項を簡単に見てみましょう。

type constructorであるList[_]は型の関数です。

T => List[T]

例えば以下のような関数とみなせます。

String => List[String]

proper typeが与えられればproper typeを返すとき、それを型レベルの関数だと考えることができます。

しかしここで返すものがproper typeではなく、他のfirst-order typeだとするとどうなるでしょう。

List[_] => WithMap[List[_]]

これは一つだけパラメータを取る型に一般化して書くことができます。

F[_] => WithMap[F[_]]

型レベルの関数を取って他の型レベルの関数を返しています。

高階関数は関数を返す関数でこれはvalueレベルのお話です。
型レベルでも共通項を見つけられたのではないでしょうか。

The `*` notation

型の型はkindと呼ばれ、*がそれらのオーダーを示すために使用されます。

Stringは*のkindでオーダーが0。
List[_]は* -> *のkind、つまり一つの型を受け取りprope typeを生むオーダー1です。例えばStringを取りList[String]を生み出します。
Map[_,_]は* -> * -> *のkind、つまり２つのオーダー0の型を受け取りproper typeを生むオーダー1です。例えばString, Intを受け取りMap[String, Int]を生み出します。
WithMap[F[_]]は(* -> *) -> *のkind、つまりオーダー1の型(* -> *)を受け取りproper typeを生み出すオーダー２です。

*によって型の型を視覚的に語ることができます。

Why do I need `F[_]`?

一つのパラメータを取るfirst-order typeを抽象化してきました。
これによってそれらに共通関数を定義できます。

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

このコードを読むときにFをListやOptionなどのfirst-order typeと読み代えても構いません。
これはすべてのfirst-order typeにmap関数を定義しているのです。

そう、それだけなのです。
これによってたくさんの異なる型に安全に関数を一挙に定義できます。
これは非常に強力ですが、この記事の主眼ではありません。
忘れないでほしいのは、これで型の実態(OptionやList)によらず何個のパラメータを取る型なのかで型を語ることができるようになったことです。

Takeaways

まとめです。

1、"a"、List(1,2,3)はvalueです
Int、String、List[Int]はproper typeです
List[_]、Option[_]はtype constructorで型を取り新しい型を作ることができ、F[_]といった形に抽象化できます
G[F[_]]は他のtype constructorを取るtype constructorで、型レベルの高階関数です