型引数の基本から学ぶ、FreeモナドとCoyoneda
このエントリはScalaアドベントカレンダーの3日目です。昨日は Kuchitama さんのScalaがつないでくれた縁-NetflixMeetup Kyoto 開催後記- でした。
前おき
この記事は、タイトル通りFreeモナドとCoyonedaを扱うものの、あまりそれらの直接的な話やモナモナした話ではなく、そこに至るまでの実装のあれこれを『Scalaのプログラミングとして』手探りで追ってみよう、というものです。
その過程で、特に型引数(型変数)や高階型や、それらが継承時にどう扱えるかというあたりのScalaの基本にたっぷり触れます。
なので、Freeモナドに興味がない方でも
- 型引数で A とか F[_] とか出てくると、まだちょっとこわい
- Scalaでいざプログラミングすると型が合わずつまづく事が多い
という方にも、役に立つ部分があると思うので参考にぜひ読んでみてもらいたいです。
もちろんFreeモナドに興味がある方にもぜひ読んでいただきたいですが、かなり泥くさくやっていきますのでそこはご承知おきください。ほとんどScalaのプログラミングの工夫の話に終始します。Freeモナド自体は、偉大な先人達の解説記事がありますので、そちらをご覧になって下さい！
(本記事は、Freeモナドを題材とした型引数に関する資料となることを目指しつつ、あわよくば読んだ人をずるずるとFreeモナドに引きずり込むためのものです)
Freeモナドのうわさ
さて、あなたがある時ふとFreeモナドというものの噂を聞いたとします。
なんでも、それを使えば map ができるだけでモナドにできる(※)のだとか。
これはとてもざっくり言うと「map ができれば flatMap を実装しなくても flatMap ができる」と言ってるようなものです。
はてさて、map ができるだけで flatMap が出来るって一体どういう事なんでしょう？
(※ 今回はファンクタもモナドもこのくらいざっくりした扱いになります)
mapだけの世界
みんなだいすき map。OptionやListなどで普段からよく使ってますよね。
Option(100).map(_ * 2) とすれば、Option(200)が得られます。便利です。
flatMapはmapと比べてそこまで使う頻度は高くないですが、forを使う時に裏で働いてくれてますね。
たとえば
for { a <- Option(3) b <- Option(5) c <- Option(10) } yield a * b + c
とすればSome(25)が得られますが、このとき裏側で、aとbはflatMapが、cはmapが呼び出されてる訳です。
確認のために上と同じことをちょっとやってみますね。
val a = Option(3) val b = Option(5) val c = Option(10) a.flatMap(x => b.flatMap(y => c.map(z => x * y + z ) ) )
これで同じくSome(25)が得られます。
flatMapは普段mapほど直接は使わないかもしれませんが、いつもfor式を影から支えてくれています。
さてさて、件のFreeモナドというのは、mapさえ持っていればflatMapが使えるようになっちゃうシロモノとのこと。
どういう事だかさっぱりですが、いま我々もmapしか持ってないとして、試しに今の例のflatMapを全部mapに置き換えてmapだけの世界を眺めてみましょう！
a.map(x =>
b.map(y =>
c.map(z =>
x * y + z
)
)
)
結果は、Some(Some(Some(25)))です。
先ほどまではflatMapを使うことでその都度2重になったSomeを1重にできていたけど、今はmapだけでやってみたので
ちょうどflatMapをmapに置き換えたのと同じ数だけ、Someの入れ子が増えていますね。
でもこれ、一応、計算自体はそれっぽく出来ているんですよ。
Someの入れ子さえ気にしなければ、計算結果の25という数字は合ってます。
それに、たとえば b の中身が None だったとしても、計算はちゃんと止まります。
問題なのは、今確認した通りmapだけ使うと値の入れ子がどんどん増えていって、元の型 Option[Int] と同じ型としては扱えなくなるという事です。
うーん、Freeモナドは気になるけど何だかよく分からないしひとまず置いといて、今はこの「flatMapを強引にmapに置き換えると、型の入れ子が増えていってしまう件」
をなんとかして、常に同じ型として扱えるように工夫できないか考えてみましょう！
型引数であそぼう！ - 関数編
(※型引数周りを知っている方は、"型引数であそぼう！”は飛ばしてください)
さて、今回はOptionやListが何重にも入れ子になった時その入れ子をなんとかしてみたいという事なので、アイデアを得るためにOptionやListの型周りの仕組みや扱いを確認してみます。
まず、OptionもListも具体型(プロパー型)を1つ取る型です。
Option[A]やList[A]などと書いたりしますね。
この時のAはどんな型でも良いです。たとえこの A にどんな型が渡されても、OptionはOptionの、ListはListの仕事に専念する(Aの型に依存した処理をしない)事できちんと動く訳です。
この A などの型引数(型変数)に関して、基本からすこしおさらいしてみます。
まず、特に意味はないですが、型引数を使って、値を渡されたらとにかくそれをOptionに包んで返すという関数を書いてみます。
def toOption[A](x: A): Option[A] = Option(x)
型引数をAとして使ってみました。Aというのはただの名前です。
このAは何か型に関する制約がある訳ではないので、このAにはどんな型が来ても良いのですが、ひとまず適当に値を渡して動かしてみましょう。
toOption("hey!")
文字列を渡してみました。結果はOption[String]型のSome("hey!")です。平和です。
ところで、これはこう書いても良いですよね。
toOption[String]("hey!")
toOptionの直後に[ ]で括って型引数を明示的に渡しました。
普段ここはtoOptionに渡される引数の値(ここだと"hey!")から推論されるので、自分で書かなくても良い訳ですね。
でも普段書かないからといって、無視されている訳ではないですよ！ いつでもちゃんと機能しています。
たとえば次のように無理やりIntのような違う型を型引数として渡すと、型が合わなくてコンパイル時にエラーになります。
// エラー！ toOption[Int]("hey!")
ちゃんと型の整合性をチェックしてくれてますね。
さて、ではもうちょっと慣れ親しむために遊んでみましょう。
たとえば、型引数を要求しておいて使わないとかしてみます。
def foo[A](x: Int): Int = x * 2
特に意味無くAという型引数を要求しているという以外、これは何も問題無いです。
foo(100)とやればIntの200が返ってきます。この場合Aは推論できないのでNothingが入ります。
foo[String](100) でも foo[Option[Any]](100) でも、何も問題無いです。Aにはどんな型でも渡せます。
型引数Aは関数の本体で使っていないので結果はどちらもIntの200が返ってきます。
型引数に慣れ親しんでないと、こういった型の受け渡しだけでもう見た目がこわく感じるかも知れません。
なので普通の関数(と普通の引数)で同じようなことをして比較してみましょう。先ほどの「要求した引数を使わない」というのは、たとえば こうです。
def plus(a: Int, b: Int, c: Int, d: Int) = a + b
これは、『cとdもらっといて使わないのか！！』というツッコミがある以外はべつに問題ない(ちゃんと動く)わけです。
型引数でも同じです。もっと大胆にしてみましょうか。
def toOption[A,B,C,D](x: A): Option[A] = Option(x)
Aという型引数は使うけれど、他の3つは使いません。使わないので、何を渡しても動作に影響はないです。
好き勝手にいろいろ入れてみましょう。
val res = toOption[Int,String,List[Double],Char](100)
このresは、Option[Int]型の値Some(100)です。
さて、先ほど「このAにはどんな型でも渡せる」と書きましたが、実はこれは「具体型(プロパー型)」の話です。
あくまでAに渡せるのはIntとかStringとかOption[Int]などであって、たとえば Option を渡す事は出来ません。
def foo[A](x: Int) = x foo[Option](100) // エラー！！
では、このようにOptionを渡すにはどうしたらいいのか？ という事で話をOptionやListの話に戻します。
まずOptionやListは、Option[A]やList[A]のように、「Aという具体型を1つ取る」型でこれは1階カインド型と呼ばれます。IntやStringのような、他に型を取る必要のない型とは違うものです。
ではOptionやListのようなものを型引数として扱う時にはどうしたらいいのか？というとこれも書き方が違って、 A[_] のように書きます。
これまで同様、Aというアルファベット部分はあくまで名前で、そのあとの[_]の部分で、どのような型を取るかを示しています。
普通の引数との比喩でいうと、普通の引数はx: Int とか x: String などとInt, Stringと型名を書く事でその値がどんな型か指定してましたが、
型引数だと、A や A[_] や A[_, _] など、型引数名のあとに[ ]を付けその中で_を使う事でどれだけ型を取るかを表していて、A[_] は型引数を1個、A[_, _] は型引数を2個取るということを意味してます。
ちなみに、これはどちらも1階カインド型です。具体型(String や Int のようなもの)を2個取っても3個取っても1階のままなのです。マンションで例えるなら、同じ階に部屋が何個あっても1階は1階・・というようなものですね。
でもわざわざ1階と呼んでるならきっと2階もあるはずですね！ちょっと先取りして解説すると、2階カインド型というのもあってそれは「1階カインド型を取るような型」です。具体的には B[A[_]] のBのように A[_] を型引数に取るものです。このBは、型引数を1個だけ取りますが、それはInt や String のようなA 型を取るのではなく Option[_] や List[_] のような A[_] 型を取っているというのが先程との違いです。そしてこのBが、2階カインド型です。
Scala ではこのような1階カインド型や2階カインド型を高階型(higher-kind型)と言いますが、Scala 以外では厳密には1階カインド型は高階型とは呼ばないそうです(参照)。
ただ、この記事では Scala を扱っているので 1階カインド型も高階型と呼ぶ事にします。
さてさて！ 説明が長くなりましたが、とにかくOptionやListなどの具体型を1つ取る型(1階カインド型)を型引数として指定するには、[_]を型引数名の後ろにつければ良いです。さっそくやってみます。
ちなみに、こういった1階カインド型の型変数名はFがよく使われるので、F[_]にしてみます。
def foo[F[_]](x: Int) = x * 2
このfooは今まで同様渡した型引数をまったく使っていませんが、今までとは渡せる型が違ってきます。先ほどのようにfoo[Int](100)などとIntを型引数としては渡せませんので、そこを意識してください。foo[Option[Int]]もダメです。IntもOption[Int]も具体型です。具体型は、型引数で指定する時 A などと指定されている所に渡せるものです。Option[Int]が具体型なのは意外かもしれませんが、Optionが高階型なのは型引数を渡されていない時の話です。F[_]は型引数を何か渡されてF[A]になったら具体型です。
なので、ここでは例えば foo[Option](100)としなくてはいけません。foo[List](100)でも良いです。これでInt型の200が返ってきます。
ただ、foo[List[Int]](100)はダメです。
ちなみに、F[_]とAのようなカインドの異なる型引数を組合せて型を表現することもできるのでそれもやってみましょう。これはかなり重要です！
def foo[F[_], A](x: F[A]): F[A] = x
何もせず値を返すだけですが、とにかく使ってみます。
foo[Option, Int](Some(100))
引数xの値はSome(100)というOption[Int]型の値を渡していますが、このとき外側の型と内側の型を分離してF[_]とAとして別々の型引数として取り扱えるのが重要なポイントです。
分離できると柔軟に扱えそうな気がしてきますよね！ つまりそういうことです！！
型引数で遊ぼう！ - class編
さて、今まで関数でやってきましたが、今度はクラスに対してやってみます。
といっても基本的に何も変わりません。
case class Bar[F[_], A](x: F[A])
先ほどの最後のfoo関数と同じにしてみました。F[A]の値を受け取りつつ、F[_]とAを分離して型変数として保持しています。
インスタンスを作ってみましょう。
val res = Bar[Option, Int](Option(100))
このresはBar[Option, Int]型の値です。
ここで関数の時との重大な違いを言いますが、クラスの場合コンストラクタに値や型を渡すところまでは関数のときと同じですが、渡されたOptionやIntという型はBarという型の一部になります。
なので、たとえばBar[Option, Int]とBar[Option, String]は同じBarではあるけれど違う型です。
これらを同一の型と扱おうとしてもそのままではできません。
// これはできない！！ Bar[F,A]のAが違う! val res2: Bar[Option, String] = res
型安全！な感じで良いですね！
これは普段の例でいうと、List[Int] と List[String] が同じ型として扱えないという話と一緒なので、そう考えると当たり前かも知れません。
でも、関数の時と同じく型引数というのは実際には使わない型をいくつでも受け渡せます。ただし関数の時と違ってclassに渡すとそれは保持され、結果として得られるインスタンスは異なる型になるという事です。例えば
case class Bar[A](x: Int) var a = Bar[Int](100) val b = Bar[Option[String]](100) val c = Bar[Either[Int, Double]](100)
これら、a,b,cは保持しているxという値こそすべてIntで共通ですが、どれも違う型です。
型引数Aは渡されただけでまともに使っていないにも関わらず、a,b,cはどれもすべて違う型なのです。
それぞれに型引数として渡された型はもう、Barの型の一部になっているので、これらは異なる型になります。
上の例だと aはvarですが、このaにbやcを代入する事はできません。それらはすべて型のミスマッチとしてコンパイルエラーになります。
型安全！な感じで良いですね！！
型引数であそぼう！ - 継承編
さてさて、クラスといえば継承関係です。継承関係ではどうなるんでしょう？
trait Foo case class Bar[F[_], A](x: F[A]) extends Foo var res1 : Foo = Bar[Option, Int](Option(100)) val res2 : Foo = Bar[Option, String](Option("yeah!")) // 問題なし！ res1 = res2
BarをFooのサブクラスとした以外は最初の例と同じです。res1とres2の値は型注釈をつけてFooにアップキャストしてみました。
もしアップキャストしなければ先ほど同様Bar[Option, Int] と Bar[Option, String] は違う型ですが、このようにFooにアップキャストすれば同じ型として扱えるので、最後の代入は問題なしです。
さて、次は親も型引数を取ってみましょう。
trait Foo[F[_], A] case class Bar[F[_], A](x: F[A]) extends Foo[F, A]
Barのextends部分に注目してください。
Barの型引数に渡されたF[_]とAを、そのまま親に渡してみました。
でも、べつにそのままじゃなく、渡すときにいろいろ型を「組み立てて」も良いです。
trait Foo[F[_], A] case class Bar1[F[_], A](x: F[A]) extends Foo[F, A] case class Bar2[F[_], A](x: F[A]) extends Foo[F, F[A]] case class Bar3[F[_], A](x: F[A]) extends Foo[F, F[F[A]]] case class Bar4[F[_], A](x: F[A]) extends Foo[F, Int] case class Bar5[F[_], A](x: F[A]) extends Foo[Option, Unit] case class Bar6[F[_], A](x: F[A]) extends Foo[F, Foo[F, A]]
それぞれextends部分に注目してください。
親の2つ目の型引数Aには具体型なら何でも渡せるので、F[A]にしたりそのF[_]を何重にも入れ子にしてみたり、FやAのような型変数を使わず突然IntやUnitを直接入れたり、Fの方にも突然Optionを入れてみたり、最後にはFoo[F, A]のような自分自身の型を渡したりと、めちゃめちゃしてみました。
特に、最後のBar6はすごい事になってますが、この時の Foo[F, A] は具体型なのでこう渡しても問題ないです。
Bar6に実際に値を入れてみるとこうです。
scala> Bar6(Option(100)) res25: Bar6[Option,Int] = Bar6(Some(100))
型をBar6としてるうちは素直なものですが、これをFooにアップキャストする時は、こうしないとダメです。
scala> Bar6(Option(100)) : Foo[Option, Foo[Option, Int]] res26: Foo[Option,Foo[Option,Int]] = Bar6(Some(100)
型注釈でFoo[Option, Foo[Option, Int]]にアップキャストしてますが、すごい型になってますね。
こういった挙動はすべて、Bar6のextendsでどのように型引数を親に渡したかに由来しています。
高階型の入れ子を畳んでみよう
さて、だいぶいろいろ遊んでみましたね。
特に、継承関係にある場合、親の型引数に渡すときには何をどう渡しても良いのがよくわかりました。
かなり柔軟なので、これは最初の問題を解決できるかも知れませんね！
ちょっとやってみましょうか。
今回は、Option(Option(Option(25))) のようなものと Option(25) のようなもの、つまりF[_]の入れ子の数が違ったときにも同じ型として扱いたいのでした。
F[_]の入れ子を畳み込むイメージを持ったので、親traitは HigherKindFolder という名前…だと少し長いのでHKFolderとします。
trait HKFolder[F[_], A] case class F1[F[_], A](x: F[A]) extends HKFolder[F, A] case class F2[F[_], A](x: F[F[A]]) extends HKFolder[F, A]
サブクラスの引数xの型の違いに注目して下さい。
F1はF[A]の値を受け取りますが、F2はF[F[A]]というF[_]が2重に入れ子になっている値を受け取ります。でも、それら値xの型は、FとAに分離され、どちらも親の型引数にはFとAとだけ素直に渡します。これにより、F1とF2はHKFolderにアップキャストすれば同じ型として扱える筈です。
やってみましょう。
val f1: HKFolder[Option, Int] = F1(Option(10)) val f2: HKFolder[Option, Int] = F2(Option(Option(10)))
できました！やった！
まだこれで何かできる訳じゃないですが、とりあえずF[_]が1重でも2重でも同じ型になってます！
…とはいえこの調子でF[_]の入れ子の数だけサブクラスを書いていったらキリがないです。
どげんかせんといかんです。
ひとまず今、F[_]を2重→1重にするような事はできたので、今後はF[_]が1つ増えてもその都度2重→1重にできれば良いですね。
なかなか難しいですが、ひとまずまだ対応してない3重Optionの値でも眺めてみましょう。
Option(Option(Option(25)))
この3重Optionの値を、いきなりHKFolderにはできなくてもせめて3重→2重へと進められればあとはそれを繰り返せば良さそうです。何か、こう、重なりを1つずつで良いので解消できれば良い訳ですね。
重なりを解消するのは今まさに作ったHKFolderとF1、F2の仕組みなので、まずこれをどこかに使えないか考えてみると、、、そういえば今対象としているF[_]はmapが使えるものを前提にしていたのでした。という事でmapを使えないか見てみましょう。
2重Optionの値 val a = Option(Option(25)) で考えてみます。この値がmapを使って例えば a.map(x => 〜) となる時、ここで出てくるxはOption(25)のことですよね。つまり、mapの内側では、Optionの数が1つ減ってる訳です。これは使えそう！
早速、3重Optionの一番外側のmapを使って、中の2重Optionの値をHKFolderにしてしまいましょう。
言葉で書くとややこしいですが、つまりこういう事です。
val a = Option(Option(Option(25))) val b = a.map(x => F2(x) : HKFolder[Option, Int]) // b: Option[HKFolder[Option,Int]] = Some(F2(Some(Some(25))))
できました。
aはもちろんOption[Option[Option[Int]]]という型ですが、
bは、Option[HKFolder[Option,Int]]という型になります。
ただ、まだちょっと先が見えてきませんね。
3重Optionだけだと分かりづらいので、試しに2重Optionに対してもmapを使って中身をHKFolderにしてみましょうか。
map(x => 〜)のxに適用するのは、今度はF1ですね。
val c = Option(Option(25)) val d = c.map(x => F1(x) : HKFolder[Option, Int]) // d: Option[HKFolder[Option,Int]] = Some(F1(Some(25)))
おっ！ ちょっと見えてきました！
先ほどのbと今のdの型に注目です。どちらも同じ型です。つまり、3重Optionの中身にmapでF2を適用しても、2重Optionの中身にmapでF1を適用しても、 どちらの場合も結果の型が Option[HKFolder[Option, Int]] になるという事です。どうやら、この「mapを使って中身をHKFolderにしてしまおう」作戦を適用すれば常にこうなりそうです。どちらもmapの中身をHKFolderにしているのだから、結果が同じになって当然といえばその通りです。
という事で、これを中継地点として繋いでいけないかやってみるべく、新たにこの型を受け取るサブクラスを作ってみます。Option[HKFolder[Option, Int]]は書き直すと、F[HKFolder[F, A]]という事です。この型をHKFolderとして表せないかやってみます。
先ほど遊んだとき型引数の取り回しの柔軟さはよくわかったので、引数xを受け取る時にきちんと型を分離表現できれば問題ない気がします！
case class F3[F[_], A](x: F[HKFolder[F, A]]) extends HKFolder[F, A]
引数xの型に注目してください。先ほど「mapを使って中身をHKFolderにしてしまおう」作戦を実行した時の結果の型です。 これは、これまで通り型引数のF[_]とA、あとは直接の型名であるHKFolderさえあれば、きれいに組み立てて表現できますね。これなら、xとしてこの型の値を受け取ったら、親のHKFolderにこうやってFとAだけ渡せば、他のF1やF2と仲間になれそうです。
ちょっとまとめて並べてみましょうか。
// F3以外先ほどのまま trait HKFolder[F[_], A] case class F1[F[_], A](x: F[A]) extends HKFolder[F, A] case class F2[F[_], A](x: F[F[A]]) extends HKFolder[F, A] case class F3[F[_], A](x: F[HKFolder[F, A]]) extends HKFolder[F, A]
良い感じですね。
早速3重Optionの値にF3を使ってみましょう。
// bまで先ほどと同じ val a = Option(Option(Option(25))) val b = a.map(x => F2(x) : HKFolder[Option, Int]) val b2 = F3[Option, Int](b) : HKFolder[Option, Int] // b2: HKFolder[Option,Int] = F3(Some(F2(Some(Some(25))))
できました！
ただ、出てきた値b2を見てみるとF3(Some(F2(Some(Some(25))))ですが、これはなんというか、こう、統一感がありそうでないのが気持ち悪いです。
値の入れ子の外側はF2/F3とSomeとが交互になっていて、これは先ほど新たに用意した中継地点のF3を毎回経由するから交互なんだなと分かりますが、内側がSome(Some(25))となっていて中継地点F3を経由してないですね。
これはF2を使って直接2重OptionをHKFolderにしているからですが、今試してみてどうやらF3が中継地点としてうまく機能していると分かったので、これをもっと活用できないかやってみましょう。
先ほどは2重Optionを直接HKFolderにしてましたが、今回はmapを使って中の1重Optionに対しF1を使ってHKFolderにして、その結果値をF3で包んでみます。
val a = Option(Option(Option(25))) val b = a.map(x => x.map(y => F1(y) : HKFolder[Option, Int] ) ) val b1 = b.map(x => F3(x) : HKFolder[Option, Int]) val b2 = F3[Option, Int](b1) : HKFolder[Option, Int] // b1: Option[HKFolder[Option,Int]] = Some(F3(Some(F1(Some(25))))) // b2: HKFolder[Option,Int] = F3(Some(F3(Some(F1(Some(25))))))
b2の値を見て下さい！ F3(Some(F3(Some(F1(Some(25))))))と目論見通り行きました！ こうなるとどうもF2は要らなそうですね。だんだん分かってきました。 どうやら、入れ子の外側からmapを呼ぶと考えるより、一番内側から考えていった方が良さそうです。つまり
- F[_]の入れ子の一番内側のF[_]がmapを使って中身をHKFolderにする
- 1の結果は常にF[HKFolder[F, A]]となるはず。これはF3に渡せる
- F3に渡したらそれはHKFolderになってる。だからそれを外側からF[_]で包んでいるならそれをまたF3に渡せばHKFolderになる
- 以降繰り返し
という仕組みで、きれいにいきそうです。そういう事なら、もう1つサブクラスを用意しておいた方が良さそうですね。つまり一番内側の1重Option状態の値がmapを呼び出した時、たとえば
Option(25).map(x => 〜)
このxは、25というInt型ですよね。型引数ではAに相当します。今はまだこのAからHKFolderにするサブクラスは用意してないのでこれは用意しておいた方が良さそうです。
case class F0[F[_], A](x: A) extends HKFolder[F, A]
xの型に注目です。ただのAです。でも型引数としてF[_]はしっかり受け取っていて、それを親の型引数に渡す事で HKFolder[F, A]として他のF1,F3と同じように振る舞えるようにしてます。さきほど遊びで散々やった「型引数を受け取っておいて、xの値には使わない」ですね。なおかつ、「親の型引数には何でも好きに渡して良い」のでFを渡してます。そう、先ほどの長い布石はここを自然に理解するためだったのです！
さて、早速これを使って3重Optionを再び内側から順にHKFolderにしていくというのをやっておきましょう。最も内側から順番に1つずつHKFolderにしてます。
val a = Option(Option(Option(25))) val b1 = a.map{x => x.map{y => y.map(z => F0[Option,Int](z) : HKFolder[Option, Int] ) } } val b2 = b1.map(x => x.map(y => F3(y) : HKFolder[Option, Int] ) ) val b3 = b2.map(x => F3(x) : HKFolder[Option, Int]) val b4 = F3[Option, Int](b3) : HKFolder[Option, Int]
ちょっと追いづらいと思うので、それぞれの結果値と型を見てみます。
内側から順にHKFolderになって、やがてそれが外側を飲み込んでいくのが値からも型からも分かるかと思います。
a: Option[Option[Option[Int]]] = Some(Some(Some(25))) b1: Option[Option[Option[HKFolder[Option,Int]]]] = Some(Some(Some(F0(25)))) b2: Option[Option[HKFolder[Option,Int]]] = Some(Some(F3(Some(F0(25))))) b3: Option[HKFolder[Option,Int]] = Some(F3(Some(F3(Some(F0(25)))))) b4: HKFolder[Option,Int] = F3(Some(F3(Some(F3(Some(F0(25)))))))
うーん、これを見ると、どうやら今用意したF0があればF1も要らなさそうですね。
一度F[_]のmapを使えばF3が適用できる状態になりますから、F0とF3だけあれば良さそうです。
ただ、今はOption(10)などの F[A] の型に対して色々やっていってる話なのでF[A]から直接HKFolderに出来ないとなると、すこし見通しづらい気がするので、F1もしばらく残しておきます。
ということで、現時点でまとめるとサブクラスは全部で3つです。
F2は捨てましたが、この2という添字番号は詰めないでおきますよ。
あと、F[_]はmapが使える事を前提にしているので、F[_] : Functorと指定しておきます。
(とてもざっくり言うと、mapが使えるF[_]のことをFunctorといいます。ただ、これ以上の話はここでは控えます)
abstract class HKFolder [F[_] : Functor, A] case class F0[F[_] : Functor, A](x: A) extends HKFolder[F, A] case class F1[F[_] : Functor, A](x: F[A]) extends HKFolder[F, A] case class F3[F[_] : Functor, A](x: F[HKFolder[F, A]]) extends HKFolder[F, A]
親のHKFolderはtraitのままだとF[_] : Functorと書けないのでabstract classにしました。
flatMapの中身をmapに委譲してみる
さて、ひとまず型の入れ子を何とかして同じ型と見なす試みは成功しました。
ただし、まだこれで何かできる訳ではないので、話を整理してみます。
まず今回は、flatMapを強引にmapに置き換えたかったのでした。でもflatMapをmapに置き換えると、flatMapとしてmapが使われる度に値と型の入れ子が増えていくという問題に遭遇したのでした。ただ、それを解決するテクニックは、先ほどまずまず目処がたちましたね。
という事で、先ほどのHKFolderを使って「flatMapを使うとmapが呼ばれる。そうすると値の入れ子は増えるけど、それを全部同じ型として見なせるようにする」という一連の流れが自動的に行われるものを作ってみたいと思います。 先ほど手作業でやった通り、HKFolderはF3を経由する事で常にHKFolderに戻ってくる事ができます。なので、HKFolderを中心にHKFolder自体にmapやflatMapをうまく実装できるか考えてみます。定義を書いて眺めてみましょう。
abstract class HKFolder[F[_] : Functor, A] { def map[B] (f: A => B): HKFolder[F, B] def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] }
定義は大体このような感じでしょうか。
さて、ここからどう取り組むかですが、実はmapやflatMapに関する1つ重要なテクニックがあります。それはpoint(pure, returnとも言う)があれば、mapはpointとflatMapだけで実現できるというものです。
ざっくりと解説するとpointというのは、何かの値 A を受け取ったらF[A]を返す関数です。
たとえば、OptionならOption(100)のように100というInt型の値をOptionコンパニオンオブジェクトのapply関数に渡すと、受け取った値をただOptionに包んで返しますね。
そういう「ただF[_]で包んで返すだけ」のものをpoint(pure, return)などと呼びます。
それがあるとどうしてflatMapからmapを実装できるかというと、Optionで言うと
Option(100).map(x => x * 2) Option(100).flatMap(x => Option(x * 2))
が同じだからです。flatMapは内側のOptionを押しつぶしてくれるので、逆に故意に1つ余分にOptionで包んでおいてからそれを潰してもらえば、それはもうmapと変わりないという事です。
この辺りは、詳しくはモナドについて調べていただく事にして、ひとまずこのテクニックを今回使ってみます。
HKFolderはF[_]やらAやら型引数を受け取りますがそれらはともかく、とにかく何かA型の値を渡したらHKFolder[F, A] が返ってくるような関数があればpointとして使えそうです。そんな関数なんて、、、関数なんて、、、そういえばありましたね。さっき最後にそういうサブクラスをまさに作ったのでした。サブクラスF0は、引数にただのA型の値を取ってHKFolder[F,A]になります。これはまさにpointです。これをそのまま使いましょう。
abstract class HKFolder[F[_] : Functor, A] { def point[B] (x: B): HKFolder[F, B] = F0[F,B](x) def map[B] (f: A => B): HKFolder[F, B] = flatMap(x => point(f(x))) def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] }
さて、pointを使ってmapも実装できました。flatMap以外は親のHKFolderの時点で完成です。あとはflatMapをサブクラスの方に実装していきましょう。
まずF0について考えてみます。定義を書いて眺めてみましょう。
case class F0[F[_] : Functor, A](x: A) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] }
fは A => HKFolder[F, B] という関数です。今F0が保持している値xはちょうどA型の値なので、この値をそのままfに渡してみます。
case class F0[F[_] : Functor, A](x: A) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] = f(x) }
とってもすんなり行きました。問題ないですね。次はひょっとしたら不要かも知れないF1です。引き続き定義を書いて眺めてみます。
case class F1[F[_] : Functor, A](x: F[A]) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] }
さて、F1が保持している値xはF[A]型です。flatMapに渡される関数fは A => HKFolder[F, B] なので、ひとまずA型の値を触れる形に持って行きたい訳ですが、これは先ほど手作業でやっていた事と同じです。F[A]の中身は今はA型の値ですから、このF[_]のmapを使って内側に1つ入って、中身のAを関数適用してHKFolder型にしてしまえば良さそうです。そうして中身がHKFolder型でその外側をF[_]が包んだ状態に持っていけたら、F3という中継地点に繋げばHKFolderにできます。まったく手作業でやった流れと同じです。やってみましょう。
case class F1[F[_] : Functor, A](x: F[A]) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] = { val y = x.map(f) F3[F,B](y) } }
これもすんなりできました。順調です。さて、次は肝心要の中継地点ことF3です。これが上手く実装できないとちょっと困りますが、ひとまずまた眺めてみましょう。
case class F3[F[_] : Functor, A](x: F[HKFolder[F, A]]) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] }
F3が保持しているxはF[HKFolder[F, A]]型の値です。flatMapに渡される関数fは相変わらず A => HKFolder[F, B] という関数ですから、とにかくこのxという値から、A型の値に触れられる形に持って行きたいです。
これまで通り、xはF[_]だからmapが使えて、1つ内側に入って行けますね。x.map(y => 〜) とすると、yはHKFolder[F, A]型の値です。F[_]な値じゃないものが出てきました。どうしましょうか。
...実はこのHKFolder[_]というのはそもそも自分自身のことで、今まさにmapやflatMapを実装している所ですね。それなら再帰的に書いても問題ないでしょうから、mapやflatMapを使っても良さそうです。F[_]の時より選択肢増えてるやったー！
先ほどのx.map(y => 〜) の続きで、yから考えてみます。仮にy.map(z => 〜)とするとしたらzというのはどんな値かを考えます。yがHKFolder[F,A]という事で型引数が多くて怖いですが、これはちょっと落ち着いて考えれば今書いてるものの事だったので先ほどの親クラスの実装を見てみれば良いです。
確認してみると、普通にmapだから当然 A => B の関数を受け取るので、その関数の引数がここでのzなので、つまりA型の値ですね。よかったよかった。無事A型の値がでてきました。という事で、zは関数fが適用できます。ここまでをちょっと書いてみましょう。
case class F3[F[_] : Functor, A](x: F[HKFolder[F, A]]) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] = { x.map{y => val a = y.map(z => f(z)) } } }
この時のaはというと、HKFolder[F, A]がmapを呼び出し、そこに A => HKFolder[F, B] な関数を適用したのだから、この関数の結果型 HKFolder[F, B] を元のHKFolder[F, A] のAの部分にそのまま入れてみれば分かりますね。つまり HKFolder[F, HKFolder[F, B]] ですね。
これはちょっと望んでいる形ではないですね。今回はHKFolder[F, B]にしたいのです。
でもこれ、型引数が多くて分かりにくいですが、具体型の部分を中心にみたら、G[G[B]] みたいな単純な入れ子ですね。
それなら、先ほどのyはmapじゃなくflatMapを呼び出せば良さそうです。やってみましょう。
case class F3[F[_] : Functor, A](x: F[HKFolder[F, A]]) extends HKFolder[F, A] { def flatMap[B](f: A => HKFolder[F, B]): HKFolder[F, B] = { val res = x.map{y => y.flatMap(z => f(z)) } F3(res) } }
どうやら上手くできたので、確認してみます。
まず、xというのは F[_] な値でした。その中身yは、y.flatMapの関数適用の結果、A から HKFolder[F, B] になったので、resはここまで散々やってきた「F[_]の中身がHKFolder」な状態であり、これは中継地点F3に渡せます。という事でF3(res)と渡して完了です！
さてさて、以上でHKFolderが完成しました！やったー！ぱちぱち！！
すこし振り返ってみましょう。HKFolderのmapは、pointと未実装のflatMapとを合わせる事で実装しました。そしてそのflatMapはというと、サブクラス上で、型引数F[_]の持つmapを必要なとき使用しています。つまり、HKFolderはmapもflatMapも、自身の保持している値がF[A]な時はそのFの持つmapに委譲しているという事です。
F[_]はあくまでmapだけ使えればよいのです。F[_]はflatMapを持ってなくて良いのです。でもそんなF[_]でもHKFolderにすればflatMapが使えてしまう！ まぁ実態はF[_]のmapを呼び出してるだけなのだけど！
これは完全に当初の目論見通りです。
最初の目標の「flatMapを呼ぶと代わりにmapが使われ、そのときF[_]の入れ子が増していっても同じ型をキープする」は、HKFolderを経由する事で実現されたのでした。
ちなみに、上記のコードはそっくりそのままFreeモナドの実装です（な、なんだってーーー！！！）
Freeモナド in ScalaにてyuroyoroさんによるHaskellから移植されたFreeモナドのコードが掲載されていますので、そちらのコードをぜひ参考にしてみてください。
名前が少し違うのと、要らないF1が省かれているのと、mapを使うときmapメソッドを生やすのではなくFunctorインスタンスのmapメソッドを使っている以外は、すべて同じです。なんということでしょう！！
ということで、どうやらこのHKFolderがFreeモナドなのでした。
確認のため、今回のHKFolderで最初の例をちょっとやってみましょう。
こういう時、F1を使うとOption[Int]のようなF[A]の値を直接HKFolderにできるので動作がわかりやすいです。
val x = for { a <- F1(Option(3)) b <- F1(Option(5)) c <- F1(Option(10)) } yield a * b + c // x: HKFolder[Option,Int] = F3(Some(F3(Some(F3(Some(F0(25)))))))
結果の値は、F3(Some(F3(Some(F3(Some(F0(25)))))))になりましたが、このうちF3とF0を飛ばすとSome(Some(Some(25)))で、見事に元の「flatMapの代わりにmapだけでやった」時と同じ値の構造になっています。
目標達成です。そして同時にFreeモナドの実装ができあがったのでした。
といってもScalazのFreeモナドは、ここからさらにStackless化しているのですが、それはここでは割愛します。
ここまでのコードはこちらのGistにまとめてあります。
余談 エトセトラ
さて、FreeモナドがふつうのflatMapのところをmapですべてまかなったもの(そのためにHKFolderを経由して繋げることで同じ型として扱えるようにしたもの)だという事は分かりましたが、では本来のflatMapとしてのF[_]の入れ子を押しつぶす役割(flatten, join)はどうするのかというと、それは「インタプリタ」として別に用意します。
つまり、Freeモナドは、「join処理を遅延したもの」とも言えそうです。そうすることで「joinを省いてモナディックな操作は値の構造として先に蓄積」する事ができるので、モナドに関する操作を先にすべてデータ化しておけるとも言えそうです。そしてそのデータを後から読みだして実際にどう動くのかは別途「インタプリタ」で指定するので、インタプリタを取り替えればモックと本番環境で違う動作をするなどができます。Freeモナドをすでにご存知の方はそういった話はすでに目にしてると思いますが、今回知った方は気になったら、その辺りぜひいろいろ探してみてください。そして面白い使い方を思いついたらぜひ公開してください！
さて、引き続き次はCoyonedaを同様にあれこれしてみますが、ここまでで想像以上に文量が多くなってしまったので、それは別記事で後ほどあげようと思います。
Coyoneda編では、さらに型を柔軟に扱うための typeキーワードのいろんな使い方に触れていきます。
※ 後編書きました
