(Coyoneda編) 型引数の基本から学ぶ、FreeモナドとCoyoneda

scala scalaz

前おき

この記事は型引数の基本から学ぶ、FreeモナドとCoyonedaの続きです。今回はCoyonedaを題材にしつつ、引き続き『Scalaで型を扱うのがちょっとこわい』方の資料となるべくScalaのプログラミングの基本にたっぷり触れていきます。

前回のおさらいをしておくと、我々はFreeモナドという「mapさえできればflatMapが出来るようになる」もののうわさを聞き、ひとまずflatMapのところを全部mapに置き換えるHKFoldを作ってみたら、それが実はFreeモナドだった事を知った所です！ なんてこった！

まだ読んでない方はそちらを先に、すでに読んだけどだいぶ忘れてきた方もなんとなくそちらをチラッと読み返して頂きつつ、では、続きをどうぞ！

Coyonedaのうわさ

mapでflatMapの代わりを担わせたらいつのまにかFreeモナドを作っていた事に気づいたあなた。 ゴキゲンでふんふふーんと過ごしていたら、またまたある噂を耳にします。 それはCoyoneda。なんとそれは『mapが出来ないものすらmapが出来るようになる』、『Coyoneda + Freeで、mapが出来ないものをモナドにできる』とのこと...

はっはっはっ、いやいや、ご冗談を。

...えっ？

Freeモナドと同じ作戦

何ともよくわからないけれど、冗談ではなさそうです。
うーん、困った。でも、前回もとにかくflatMapが使えないのをとにかくmapで補ったら上手くいきました。それなら、今回も同じようなことで良いかも知れません。

前回した事の意味を考えてみます。我々は結局、flatMapが本来やってくれるflatten(join)処理をその場でどうにかする事は諦めて、mapをflatMapの代わりに使いました。つまり、flatten(join)処理は棚上げしてひとまず放棄したのです。
そして、そこで放棄したものは後からインタプリタを別途用意してそこで回収する、それがFreeモナドというものらしいと知りました。
それなら、mapも処理を棚上げ＆あと回しして、後で回収して何とかしてもらえば良いんじゃないでしょうか？

なんだか、果たしてそんな事をして意味があるのかという気もしてきますが、棚上げして処理を放棄するという言い方が悪いだけで、これは処理の分離に成功したとも言えます。それなら融通が利いて良さそうです。やってみましょう！

あとでやる、きっとやる、ぜったいやる

さて、mapのあと回しとは何なのか、ひとまず方針を立てるべくいつも使ってるmapの様子を眺めてみます。

Option(10).map(_ * 2)

結果はOption(20)です。ふつう、mapはこのように関数を受け渡されたら値にすぐ関数適用して返しますよね。上のコードだとOption(10)は中身がすぐ2倍されて、Option(20)が返されます。

でも今回のテーマは"あと回し"です。Freeモナドがflatten(join)をあと回しにしたように、mapも肝心な部分をあと回ししたいです。という事で、今回はmapの関数適用をあと回しにしてみましょう！

目標は「見た目はいつも通りだけど、関数の適用だけを遅延するmap」です。イメージはこうです。

LazyMap(10).map(_ * 2)

関数の適用を遅延するイメージで、LazyMapという名前にしました。LazyMapは見た目ふつうにmapを使えます。しかし、このmapは引数で渡された関数を値に適用しません。受け渡された関数は内部に溜め込んでいく事にします。そうやって溜め込んだ関数を最終的に値に適用するのは、別の何かがあとから行うことにします。つまり上のコードはmapが終わった段階で、値自体はまだLazyMap(10)のままというイメージです。これなら、関数適用があとまわしされたと言えるんじゃないでしょうか！

早速、クラスの大まかな形とmapの定義を書いてみます。

class LazyMap[A](x: A) {
  def map[B](f: A => B) : LazyMap[B]
}

値xを受け取る以外、まだmapをどうするかは決めてません。この部分をどうするか、もうすこしmapの動作イメージを掴むために、ふたたびOptionでもっとmapを使ってみながら考えてみます。今度は、mapに渡す関数を変数に入れてみたり、mapをたくさん繋げてみます。

val f = (_: Int) * 2
val g = (_: Int) + 5
val h = (_: Int) * 10

Option(10).map(f).map(g).map(h)

3回mapしました。このmapの流れに注目してみます。通常、mapを上のようにチェーンしたときは、10にfして、gして、hして...なので

h(g(f(10)))

ということですね。ふむふむ、見たことある形です。どうやらmapで受け渡された関数はただ重なっていくだけなので、これなら関数合成で表現できますね。つまり上のコードは

(h compose g compose f)(10)

と書き直せます。なので、さきほどやりたかった「関数を溜め込んでいく処理」は、mapの度にひたすら関数合成を繰り返していけば良さそうです。やってみましょう！

case class LazyMap[A,B](x: A, acc: A => B) {
  def map[C](f: B=>C): LazyMap[A,C] = LazyMap(x, acc andThen f)
}

値accに注目です。これは関数を溜め込んでいくための関数値です。このaccの型を A => B とするために新たに型引数Bも取りました。
mapの実装部分もシンプルです。値xはそのまま値xとして何もせず次に渡します。そしてmapに渡された関数fをそれまで関数を溜め込んだ結果であるaccと合成します。合成は、なんとなくmapのチェーン順序の並びに合わせてcomposeではなくandThenにしました。

さっそく使ってみましょう！

LazyMap(10, identity[Int]).map(f).map(g).map(h)
// res0: LazyMap[Int,Int] = LazyMap(10,<function1>)

accの初期値にはidentityを渡してみました。これなら、そのあとの関数合成に繋いで行っても影響がないです。

さて、無事意図したとおり動いたのか計算結果も見てみたいですね。runという、あと回しした関数適用を執行するものを実装してみます。

case class LazyMap[A,B](x: A, acc: A => B) {
  def map[C](f: B=>C): LazyMap[A,C] = LazyMap(x, acc andThen f)
  def run = acc(x)
}

runは、溜め込んだ関数accに初期値のまま保持された値xを適用するだけです。動かしてみます！

val lm = LazyMap(10, identity[Int]).map(f).map(g).map(h)
val res = lm.run
// res: Int = 250

無事、Int型の250が返されました！ 概ね、やりたい事の輪郭は得られた感じです。やったー！

ただこのままではFreeモナドとの連携はできません。そもそも、Freeモナドはmapが使えるF[_]な値を受け取って、flatMapを提供してあげていました。それで言うと、今回はmapすら持たないF[_]にmapを提供してあげるべきです。そうする事で、mapすらできないF[_]な値が、mapと、flatMapを芋づる式に獲得する事になります。でも今LazyMapが受け取っていたのは、ただのIntです。F[_]に包まれていない、ただのIntです。

ということで、今まで受け取っていた値xの型をAからF[A]に書き換える必要がありそうです。やってみましょう！

case class LazyMap[F[_], A, B](x: F[A], acc: A => B) {
  def map[C](f: B => C) = LazyMap(x, acc andThen f)
  def run = ???
}

値xの型に注目です。前回たっぷり遊んで覚えた通り型引数F[_]とAに分離してその組合せでF[A]としてます。この段階で型をきちんと分離できているので、値accもmap関数も先程のまま変更なしです！

ただrunの実装がむつかしいです。値xがF[A]型になったので、F[A]型にA => Bな関数を適用する必要があります。でもその、F[A]型にA => Bな関数を適用する仕組みこそmapと呼ばれるものです。つまりここで「ホンモノのmap」が必要になってしまいました。今回は、ホンモノのmapを持ってないF[_]な値を対象にしているので、これは本末転倒です。困りました！

でも、これはあまりに本質的すぎてどうしようもないです。それに、そもそもの目的はrunの瞬間まで関数適用をしない事なので、ここまで関数適用あと回しにしただけで、よくがんばったんじゃないでしょうか...うんうん。という事で、ここはもう諦めて、『runしたかったら、本物のmapを用意すること！』という条件を付けて本物のmapを使ってしまいます！

case class LazyMap[F[_], A, B](x: F[A], acc: A => B) {
  def map[C](f: B => C) = LazyMap(x, acc andThen f)
  def run(implicit functor: Functor[F]) = functor.map(x)(acc)
}

runの暗黙の引数としてFunctorのインスタンスを要求する事にしました。Functorは、mapができるF[_]のことでしたね。これで、このrun内ではホンモノのmapが使えます。(暗黙の引数についての話はここでは控えます)

さて、準備は整ったので動かしてみましょう！ mapすら持ってないシンプルなF[_]な型 MyBox[_] を新たに用意して、それにLazyMapを経由させてまるでmapを持っているかのように振る舞わせてみましょう！

case class MyBox[A](x: A)

val lm = LazyMap(MyBox(10), identity[Int]).map(f).map(g).map(h)

val res = lm.run(
  new Functor[MyBox] {
    def map[A,B](fa: MyBox[A])(f: A => B): MyBox[B] = MyBox(f(fa.x)) 
  } 
)
// res: MyBox[Int] = MyBox(250)

結果はMyBox(250)で、うまく動きました！ 最後結果を見るためにすこし強引に Functor[MyBox] のインスタンスを作って渡してますが今は気にしないことにします。

さて、あとは使い勝手を良くする細かいものも作っておきましょう。ここまでLazyMapのインスタンスを作るときは identity を毎回渡してましたがすこし面倒ですね。これを省略するヘルパ関数を用意しておきます。

def liftLazyMap[F[_], A](x: F[A]) = LazyMap(x, identity[A])

LazyMapの値accをidentity固定にしてインスタンスを作るだけのものです。名前はliftLazyMapとしました。これを使えば

val lm = liftLazyMap(MyBox(10)).map(f)

のように、identityの記述を省けます。

Functorのインスタンス

さて、あとはこのLazyMapをFunctorなるもののインスタンスに出来れば、Freeモナドとの連携もできて目標達成です。Functorという言葉は今まで何度か出てきましたね。とてもざっくり言うと、mapが出来るF[_]のことです。
Functor自体はこのように定義されています。

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

Functorに型引数として高階型F[_]を渡して、あとはふつうにmapを実装すればインスタンスが作れます。たとえば、OptionでFunctorのインスタンスを作ってみるとこうです。

implicit val optionFunctor = new Functor[Option] {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] =
    if (fa.isEmpty) None else Some(f(fa.get))
}

mapの実装はScala標準のOption.scalaの実装そのまま拝借しましたが、今回注目なのはmapの実装より new Functor[Option] の部分です。Functorの型引数F[_]にOptionを渡しています。Optionは具体型を1つ取る型なので、この型引数F[_]にそのまま渡せます。

でも今FunctorのインスタンスにしたいLazyMapはこの通り...

class LazyMap[F[_], A, B]

高階型を1つ、具体型を2つ取る型でした。でもFunctorは具体型を1つ取る型しか受け付けません。そう、このままでは型引数の数が合わずFunctorのインスタンスが作れません！ もうあと一息なのに！

...この最後の一歩を乗り越えるには、型を変数としてさらに自在に扱うテクニックが要ります。ゴールまであと僅かですが、その前に"型引数と対をなすtypeキーワードの使い方"にたっぷり触れて、この一歩を乗り越えることを目指します！

typeキーワードとあそぼう！ - 型引数を隠す編

「型引数を隠す編」としましたが、その前に前回の「型引数と遊ぼう」のおさらいです。まず、型引数を無くすだけならば前回遊んだときチラッと出てました。クラスの継承関係を利用すれば良かったですね。

trait Foo
case class Bar[A](x: A) extends Foo

var a: Foo = Bar(10)
val b: Foo = Bar("abc")

// 問題なし！
a = b

Bar[Int] も Bar[String] も、どちらもFooにアップキャストすれば最後の代入ができるので、型引数 A は隠せたように見えますが、これはIntやStringという情報がなくなってしまうので、むしろ「型引数が消えた」とも言えます。今回は、消すのではなく隠すような事がしたいのです。そのためにtypeキーワードと遊んでいきますよ！

さて、typeキーワードですが、まず一番の基本は「別名」としての使い方です。

type UserName = String

String型をべつの名前(UserName)と呼んでも良いという事にしました。あくまで別の呼び方というだけなので、UserName型を要求するところにString型の値をそのまま渡せます。たとえばこうです。

case class User(userName: UserName)

val user = User("taro")

UserクラスのコンストラクタはUserName型を要求してますが、String型の値をそのまま渡せます。

また、この別名というのはクラスのメンバーにもできますね。

class User {
  type UserName = String
}

val a: User#UserName = "taro"

Userクラスは、Stringの別名UserNameという型をメンバーとして持ちます。この型名は#を使って、クラス名#型メンバの形で使えます。そして、こういった型メンバーも抽象メンバにできます。つまり、最初は決めないでおいて後から定義できるわけです。

class User {
  type UserName 
}

class HogeUser extends User {
  type UserName = String
}

val a: HogeUser#UserName = "taro"

User#UserName はどんな型を示すのか決まっていませんが、あとから HogeUserクラスでString型と定義されています。

ところでこれは、直接インスタンスを作るときにも定義できますよね。

val hoge = new User {
  type UserName = String
}

val a: hoge.UserName = "taro"

このようにインスタンス化する時にクラスの型メンバをStringに決定することができます。これは見方によっては「クラスの外からクラスの中に型を渡した」と考えても良さそうです。つまり、型引数ととても似ています。

型で考えるとピンと来づらいかも知れないので、またまた値で考えてみます。いまの話を値にするとこうです。

class FooUser(val username: String)

abstract class BarUser {
  val userName: String
}

val foo = new FooUser("taro")
val bar = new BarUser{ val userName = "taro" }

FooUserクラスもBarUserクラスも、userNameというフィールドに外から値"taro"を渡してクラスのインスタンスを作ります。このとき、"taro"という値を渡すという事を、FooUserはコンストラクタで、BarUserは抽象クラスの実装という形で行いました。どちらも、クラスのメンバに値を外から渡しています。

この部分を型でなぞらえると、つまり

  • 型引数は、「コンストラクタで型を渡す仕組み」
  • 抽象型メンバは、「抽象クラスの実装という形で型を渡す仕組み」

として、どちらも型を外から渡すために使えそうだという事です。

これを踏まえて、今まで型引数でやっていた事を抽象型メンバでやってみます。両者を並べるとこうです！

class MyBox1[A](val x: A)

abstract class MyBox2 {
  type A
  val x: A
}

MyBox2に注目です。MyBox1と似たような事をしてみました。
MyBox1 は、型引数としてAを持ちますが、MyBox2 は、抽象型メンバとしてAを持ちます。
大きな違いは、MyBox2は型メンバのAだけでなく、その型の値xもクラス内部に持っている事です。コンストラクタの位置からはこのtype Aが見えないので

// これはできない！
abstract class MyBox2(val x: A) {
  type A
}

これはできません！ type Aはclassの内部の位置にあるので、値xも同じ位置にないとダメです。

両者のインスタンスを作ってみます。

val a = new MyBox1(10)
val b = new MyBox2 { 
  type A = Int
  val x = 10
}

どちらも、10というInt値を保持します。MyBox1は型推論が効いてInt型を明示的に渡さず済んですこし楽ができますが、最終的には両者同じようなことができています。

ところで、型引数のよいところは、型チェックの対象になって型安全！なことでしたね！ でもじつは型メンバも型チェックの対象にできます。

// 問題なし！
val x1: MyBox1[Int]          = a
val x2: MyBox2{type A = Int} = b

// 型エラー！
val y1: MyBox1[String]          = a
val y2: MyBox2{type A = String} = b

x2,y2の型を見て下さい！ typeキーワードがそのまま埋め込まれています。こうする事で、型引数を使ったx1,y1と同じように、型検査が行われています。x2は良いけど、y2はエラーです。

もちろん、typeキーワードは外す事もできます。その時、型メンバ A の型検査は行われません！

var z1: MyBox2 = new MyBox2 { type A = Int;    val x = 10 }
val z2: MyBox2 = new MyBox2 { type A = String; val x = "Hey!" }

// 問題なし！
z1 = z2

つまり、型引数とちがって型メンバは型検査の対象にするかどうかを自在にOn/Offできます。とても柔軟で便利そうですね！ じっさい便利です！

残念なのは見た目がごちゃっとする事ですが、これも「型引数」の形に直す事ができます。じつは、typeキーワード自体が型引数を取れるのです。

type MyBox3[X] = MyBox2{ type A = X }

// z4だけエラー！
val z3: MyBox3[Int]    = new MyBox2 { type A = Int; val x = 10 }
val z4: MyBox3[String] = new MyBox2 { type A = Int; val x = 10 }

MyBox3 に注目です！ 型引数Xを取っています。このXは今まで扱ってきたような、ふつうの型引数です。そのXという型を使って、MyBox2の型を記述しています。

なので、z3とz4の型は、型引数の形で先ほどtypeキーワードを埋め込んだ事と同じことが書けています。当然、型検査が行われて、z4だけがエラーになります。

MyBox3の利点は見た目が整うだけじゃなく、型検査を強制できる点にもあります。MyBox2の時と違って val z3: MyBox3 = b のような記述はできません。MyBox3は型引数が必須です。型安全！な感じでよいですね！

まとめると、typeキーワードによる抽象型メンバは、型引数を柔軟にしたもののように扱える、という事です！ 便利！ じっさい便利！

typeキーワードと遊ぼう - 部分適用編

さて、先ほどの最後のMyBox3では、typeキーワード自体で型引数を取ってみました。引数を取れるなら部分適用もできるはずです。どういうことか、まずは普通の関数（と普通の引数）で考えてみます。

次のような、引数を2つ取るシンプルな関数があるとします。

def add(a: Int, b: Int) = a + b

これを1引数の関数にするには、もう1つ関数を作って、事前に引数aを埋めれば良いです。(bを埋めても良いです)

def add100(x: Int) = add(100, x)

あまり、このように　def を使って部分適用を書くことはしませんが、typeキーワードの部分適用になぞらえるため、あえてこうしました。

型でも同じ事してみます。まず具体型を2つ取る型があるとします。

case class Foo[A,B]()

ここで、型の受け渡しというのを関数のように捉えると、このFooというのは『具体型AとBを受け取ってFoo[A,B]型を返す関数』です。型の関数と言えそうですね。

そういう意味では、typeキーワードも型の関数です。
なので、具体型を2つ取るFooという型を「具体型を1つ取る型」にするには、もう1つtypeキーワードとして型の関数を用意して、事前にFooの型引数Aを埋めれば良いです(Bを埋めても良いです)。言葉でいうと分かりにくいですが、つまりこうです。

type FooInt[X] = Foo[Int, X]

Fooの型引数AをIntで埋めてみました。型の部分適用です！
初めはちょっと戸惑いますが、流れ自体は上のdefでの部分適用とまったく同じ流れです。typeキーワードで型引数を取れば、このように型の部分適用も実現できます！

typeキーワードと遊ぼう - 関数内部編

さてさて、そんな便利なtypeキーワードですが、若干ざんねんな所もあります。関数内でtypeキーワードを使うと、外からその部分が確認できずに同じ型が同じ型として判定できなくなるのです。

ためしに、関数内で別名をつけるだけの、identityのような関数で見てみます。

def myIdentity[A](x: A) = { 
  type MyA = A
  x : MyA 
}

受け取った型引数Aに、ただMyAという別名を付け、返り値をMyA型として返すだけのものです。A と MyA が同じである事ははっきりしています。しかし...

// 問題なし
val a      = myIdentity(10)

// エラー！
val b: Int = myIdentity(10)

値aはじつは動きます。ただ、これはInt型として扱えないのです。値bのように型注釈でInt型である事を求めるとエラーになります。値aもこのコードが動くとは言え、他のInt型を要求する場所には渡せません。これまで、別名としてのtypeキーワードは同じ型と判定されてきましたが、関数内のtypeキーワードは関数の外側と正しく連携できないのです。

これを解決する方法は、関数の返り値型をしっかり書くことです。

def myIdentity[A](x: A): A = { 
  type MyA = A
  x : MyA 
}

val b: Int = myIdentity(10)

関数の返り値型にAと書いただけです。なので、関数内の最後でMyAにキャストしている部分が、最終的にまたAにキャストされて返されるような流れです。なので、無事に値bはInt型として扱えます。

まとめると

  • 『関数の内部でtypeキーワードを使って定義した型』が、
  • 『関数の返り値型に登場するとき』は、
  • 『関数の返り値型を明示的に書く！』

という事です。ここを忘れると、ひたすら型エラーが出ます。要注意です！

Functorのインスタンスをつくろう！

さて、今回はtypeキーワードとたっぷり遊びました。typeキーワードは、型引数をさらに柔軟に扱うために用いられると知りました。このテクニックを総動員して、いよいよLazyMapのFunctorインスタンスを作ってみましょう！

まず、何が問題かを思い出してみます。LazyMapはこのような実装でした。

case class LazyMap[F[_], A, B](x: F[A], acc: A => B) {
  def map[C](f: B => C) = LazyMap(x, acc andThen f)
  def run(implicit functor: Functor[F]) = functor.map(x)(acc)
}

LazyMap は型引数、F[_], A, B を取りますが、このうち不要な型引数を隠したい（抽象型メンバにしたい）です。
ただ、何でも隠して良いわけではないです。たとえば、Option[String]というのは、要素の型がStringと明示されているからこそ、たとえばmapで_.capitalizeというStringの関数を受け取れます。

Option("abc").map(_.capitalize) 
// Option[String] = Some(Abc)

もし、Option[A]の型引数Aを隠してしまって、外から要素の型がIntかStringか分からなくなっては、mapを使うとき支障が出そうです。

なので、LazyMapのうち不要な型引数を隠したいです。そんなものがあるのかどうか、LazyMapの動作をいろんな角度から眺めてみます！

今まで、LazyMapにはInt型の値と Int => Int な関数を渡してばかりだったので、もっと型の変化を伴う関数を用意してみます。

val f: Int => Int            = _ * 2
val g: Int => String         = _.toString
val h: String => Array[Char] = _.toCharArray

このような関数を用意しました。1つずつmapしてみます。

val a = liftLazyMap(MyBox(10))
val b = a.map(f)
val c = b.map(g)
val d = c.map(h)

値と型を眺めてみましょう！

a: LazyMap[MyBox,Int,Int]         = LazyMap(MyBox(10),<function1>)
b: LazyMap[MyBox,Int,Int]         = LazyMap(MyBox(10),<function1>)
c: LazyMap[MyBox,Int,String]      = LazyMap(MyBox(10),<function1>)
d: LazyMap[MyBox,Int,Array[Char]] = LazyMap(MyBox(10),<function1>)

それぞれの型に注目です！ なかなかきれいな結果が出ました！ どうやらLazyMapの型引数[F[_], A, B]のうち、mapによって変化するのはBだけのようです。
これを踏まえてLayMapの実装を眺めてみると、その意味がわかります。

case class LazyMap[F[_], A, B](x: F[A], acc: A => B) {
  def map[C](f: B => C) = LazyMap(x, acc andThen f)
  def run(implicit functor: Functor[F]) = functor.map(x)(acc)
}

LazyMapとして最初に受け取った値xは、mapしても変化しません。これはmap関数の本体で、何もせずxを次に渡している事からもわかります。
そして、型引数Aはそんな「最初のx」の型を表し続けているだけなのです！ このxは何も変化しないので、この型引数Aも当然変化しません。それなら、この型引数Aは抽象型メンバとしてクラスの内側に仕舞って良さそうです！

さっそくやってみましょう。ただし、型引数のAやBがいろんな場所に散らばると混乱するので、先にまず名前をリファクタリングしておきます。型引数Aや値xの意味がわかったので、それぞれA型をStart型に、xをstartという名前にしておきます。

case class LazyMap[F[_], Start, A](start: F[Start], acc: Start => A) {
  def map[B](f: A => B) = LazyMap(start, acc andThen f)
  def run(implicit functor: Functor[F]) = functor.map(start)(acc)
}

リネームが完了しました。ではいよいよ、型引数Startを、抽象型メンバにします。注意点は先ほどtypeキーワードであそんだ時に学んだとおり、このStart型が関わっている値start, accも一緒にクラス内部に移す必要がある事です。やってみましょう！

abstract class LazyMap[F[_], A] { lm =>
  type Start
  val start: F[Start]
  val acc: Start => A

  def map[B](f: A => B): LazyMap[F, B] = new LazyMap[F, B] {
    type Start = lm.Start
    val start: F[Start] = lm.start
    val acc: Start => B = lm.acc andThen f
  }

  def run(implicit functor: Functor[F]): F[A] = functor.map(start)(acc)
}

見た目がだいぶ変わりました。抽象クラスになったのでmap関数内でインスタンスを作るのが少し大変になったのが大きいです。map関数でのインスタンス生成は、self alias lm => を活用してlmという別名を多用しています。でも、やってる事は先ほどとまったく同じなのでゆっくり読んでみてください。ここでやった事は、Start型、start, acc の3つをクラス内部に移しただけです！

さて、無事、具体型を1つ減らせたところで残すはF[_]ですが、これは型の部分適用で乗り切ります。いよいよFunctorのインスタンスを作るときです！ やってみましょう！

implicit def lazymapFunctor[F[_]] = {
  type LM[X] = LazyMap[F, X]
  new Functor[LM] {
    def map[A,B](fa: LazyMap[F,A])(f: A => B): LazyMap[F, B] =
      fa.map(f)
  }
}

関数 lazymapFunctor は、型引数F[_]を受け取ります。そして、そのF[_]はLazyMap型に部分適用して具体型を1つ取るLM[X]型の形にしています。FunctorのインスタンスはこのLM型に対して実装します。といっても、map関数の実装はかんたんです。すでにLazyMap自体にmapを実装してあるので、わざわざここで再実装せずにfa.map(f)とfaのmapに委譲して終わりです。

さて、ただ、ひとつだけ不完全な部分があります。そう、この関数 lazymapFunctor関数の返り値型は Functor[LM] としたい所ですが、LMは関数内部で定義した型です！ これでは、先ほどtypeキーワードで遊んだとき学んだように、型の判定が正しくできません。かといって、LM型は型の部分適用を伴った複雑なものなので、関数の返り値型にすんなり書けません。。

これを解決する方法は、「関数の返り値型のところにもtypeキーワードを埋め込む」です。実際に書いてみます。

implicit def lazymapFunctor[F[_]] : Functor[({type LM[X] = LazyMap[F, X]})#LM] = {
  type LM[X] = LazyMap[F, X]
  new Functor[LM] {
    def map[A, B](fa: LazyMap[F, A])(f: A => B): LazyMap[F, B] = fa.map(f)
  }
}

lazymapFunctor関数に返り値型を書いた以外はさきほどと全く同じです。返り値型がFunctor[({type LM[X] = LazyMap[F, X]})#LM]と、すごい事になっていますが、落ち着いて読めば大丈夫です。
まず、関数の返り値型は本当はFunctor[LM]と書きたかったのでした。でも、そのLMは関数内で定義されているので、この位置に書けません。なので、そのLMを定義しているところ(コード2行目)のtypeキーワードで書いた一文をまるまる({ })で囲って関数の返り値型の位置に持ってきます。そうして出来た({type LM[X] = LazyMap[F, X]})という塊は、クラスが型メンバを持つように、この塊も型メンバLMを所持してる状態になり#LMと付ける事でその型メンバLMを参照できる、という仕組みです。見た目がかなり残念ですが、やっている事はFunctor[LM]と書いているのと同じです。

ちなみに、関数の返り値型の({ })内の型名は関数内の型名と名前が違っても良いです。たとえばこうです。

implicit def lazymapFunctor[F[_]] : Functor[({type λ[X] = LazyMap[F, X]})#λ] = {
  type LM[X] = LazyMap[F, X]
  /* 略 */
}

関数の返り値型と、2行目のtype LMを見てください！ どちらも同じ型の形ですが、型名がそれぞれLMとλ(ラムダ)です。このように名前が違っても、同じ型だと分かれば良いので、型名は好きにつけても良いです。

ともあれ、これでLazyMapのFunctorインスタンスも作れました！ やったー！ ばんざい！

すこし振り返ってみましょう。今回は、mapがいつも行っている「関数適用」を後回しするために、関数合成によって適用を遅延するLazyMapというものを作りました。LazyMapは具体型を2つ持つ必要があったため、そのままではFunctorのインスタンスが作りにくかったですね。そこで、typeキーワードとたっぷり遊び、その知識でLazyMapとして表に出てくる必要のない「始めの値の型」を抽象型メンバにしました。型引数を1つクラス内部に隠したわけです。これで具体型の型引数は1つになりました。あともう1つ、LazyMapは高階型F[_]という型引数も取っていましたが、これは型の部分適用を使って対応しました。おかげで無事、Functorのインスタンスを作る事に成功したのです！

これによりmapすら持っていないF[_]な値も、LazyMap経由でmapが使えるようになりました。ただmapを実装しただけでなく、Functorのインスタンスもきちんと作りました。まぁこのmapの実態は、関数合成でひたすら関数適用を遅延してるだけなのだけど！

でもこれで当初の目論見が一通り実現できました。

さてさて、いよいよお時間がやってまいりました。そう、上記のコードはそっくりそのままCoyonedaの実装です（や、やっぱりーーー？！！）

ぜひ、scalazのCoyonedaクラスを読んでみて下さい！ 照らし合わせやすいよう、今回のLazyMapのフィールド名ほかをScalazに合わせてリネームするとこうです。

abstract class LazyMap[F[_], A] { coyo =>
  type I
  val fi: F[I]
  val k: I => A

  def map[B](f: A => B): LazyMap[F, B] = new LazyMap[F, B] {
    type I = coyo.I
    val fi: F[I] = coyo.fi
    val k: I => B = coyo.k andThen f
  }

  def run(implicit F: Functor[F]): F[A] = F.map(fi)(k)
}

scalazでは他にも便利メソッドが追加されていたり、抽象クラスであるCoyonedaのインスタンスをかんたんに得るためのコンストラクタが用意されコードがすっきりしているなどの細かい違いはありますが、それ以外すべて同じです！ ヘルパ関数として作ったliftLazyMap関数は Coyoneda#lift関数 です。Functorのインスタンスを得るために作った lazymapFunctor関数 は coyonedaFunctor関数 です。（ただし現在は、今回紹介した型の部分適用は、もっと読みやすいkind-projectorを利用した形に置き換えが進んでいるようです）

では確認のため、Scalazを使わず今回作ったLazyMapと前回作ったHKFoldのみを使って、mapもflatMapも持ってないMyBox[A]をfor式の中で使ってみましょう。今回は型の移り変わりも大事なポイントなので、途中いじわるとして数字を文字列で渡しつつ、数の計算の後も文字列にして返します。

case class MyBox[A](x: A)

// 型推論を補うための型
type LMMyBox[X] = LazyMap[MyBox, X]

// 型の記述を省力化するための関数
def lazyMyBox[A](x: MyBox[A]): LMMyBox[A] = liftLazyMap(x)

val res = for {
  a <- F1(lazyMyBox(MyBox(3)))
  b <- F1(lazyMyBox(MyBox("5")))
  c <- F1(lazyMyBox(MyBox(10)))
} yield (a * b.toInt + c).toString + "です！"
//  res: HKFold[LMMyBox,String] = F3(LazyMap$$anon$2@34863021)

値resの型を見てください！ 無事、要素型がStringになってます。ただし、この段階では関数が合成されただけでまだ値に適用されていないはずです。結果が見たいので、またまた強引に関数適用してみましょう。自前でMyBoxのFunctorインスタンスを用意しつつ、今回はインタプリタも用意して実行してみます。

implicit val myboxFunctor = new Functor[MyBox] {
  def map[A,B](fa: MyBox[A])(f: A => B): MyBox[B] = MyBox(f(fa.x))
}

def interpreter[A](program: HKFold[LMMyBox, A]): A = program match {
  case F0(a) => a
  case F3(a) => a.run match {
    case MyBox(b) => interpreter(b)
  }
}

interpreter(res)
// res1: String = 25です！

無事、25という値が元気よく得られました！ やったー！
ここまでのコードはこちらのGistにまとめてあります。

余談エトセトラ

さて、今回インタプリタは直接自分で再帰関数を書きましたが、実際には自然変換(NaturalTransformation)を用意してあとはScalazに任せられます。そうすれば、今回のように自前でMyBoxのFunctorのインスタンスを作る必要はないです。

これはたとえば、MyBoxからOptionへの自然変換を書いたなら、Optionに備わっているmapやflatMapが自動的に使われて遅延していた処理が解決する、ということです。今までやってきた諸々の遅延は、自然変換後のモナドにやってもらう事で、無事、自分では担当せずに解決します。めでたし！
自然変換を含めた実際のScalazのFreeの使い方は、ryoppyさんのscalaz - Freeの記事が参考になると思います。

以上で、「型引数の基本から学ぶFreeモナドとCoyoneda」は終了です！ 何か気づいた点などあればコメント欄かツイッター@awekuitまでお知らせ下さい。 それでは、良きFreeモナド生活を！

参考URL

型引数の基本から学ぶ、FreeモナドとCoyoneda

scala scalaz

このエントリは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を呼ぶと考えるより、一番内側から考えていった方が良さそうです。つまり

  1. F[_]の入れ子の一番内側のF[_]がmapを使って中身をHKFolderにする
  2. 1の結果は常にF[HKFolder[F, A]]となるはず。これはF3に渡せる
  3. F3に渡したらそれはHKFolderになってる。だからそれを外側からF[_]で包んでいるならそれをまたF3に渡せばHKFolderになる
  4. 以降繰り返し

という仕組みで、きれいにいきそうです。そういう事なら、もう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キーワードのいろんな使い方に触れていきます。

※ 後編書きました

参考URL

scala

haskell

"Free + OptionによるList実装" で理解したことまとめ

scala scalaz

xuwei_kさんのブログで1年前に紹介されていたrunaroramaさんのFree + OptionによるList実装が、パッと見どういう事だかわからなかったのがそこそこ分かったので、その部分について書きます。 今回書くことは、要約すると
『Freeモナドは、A型やF[A]型からLiftしたときどちらも同じようにFreeモナドとして扱えるけど、mapやflatMapの時はそれらをきちんと見分けて動くし、A型の方はFunctorも使わないよ』というお話です。Freeモナドのその他の話は出てきませんので悪しからず...

ちなみに、ブログの元のコードはScalaz 7.1より前のものでしたが、「これ今のScalaz 7.1では実装できないのでは！」と聞いたところサクッと実装して下さいました。改めてxuwei_kさん、ありがとうございました(深々)

同じ型という曖昧さと、同じ型という制約

今回見ていくコードではまず、次のような型宣言が出てきます。

type PairOpt[A] = Option[(A, A)]

これを見ると、 『えーとOptionに包まれて、あぁ、Tupleの中身はすべて同じ型である事を要求しているんだな』と思いますよね。 Tupleの部分だけ見て言えば、(Int, Int) や (String, String) などが入るんだろうな〜と。 暗黙のうちにそういった『派生型が入る』という気がしていませんか？ 私はしていたので、理解が遅れました。 つまり、こういう事がありえます。

val a: Int        = 10
val b: String     = "hey!"
val t: (Any, Any) = (a, b)

IntもStringもAnyにしてしまいPairにしてます。これは、PairOpt型になりえます。

val p: PairOpt[Any] = Option(t)

つまり、型が同一かどうかは、アップキャストすれば満たせます。 これはもちろんAnyに限らない話です。SomeやNoneをOption型として同一に扱うのは普段からよくやっていますね。継承関係があれば良い訳です。ただ、OptionのようなF[A]型の場合、あくまでF[_]の派生型を親のF[_]で同一に扱うという話であって、たとえば 100 と Option(5) はそのままでは同じ型として扱えません。でもこのような A型 と F[A]型 の関係も、FreeへLiftすればどちらも Free[F, A] として扱う事になります。つまり同じ型です。じつは上記の「Tupleの要素が同じ型」という制約は、このAとF[A]がFree上で同じ型になる仕組みを前提とした制約だったのです（！）

型引数、使わず渡してもいいんだよ

さて、『AとF[A]がFreeになると同じ型になる』とはどういう事なのか、Freeモナドのしている事をすこしおさらいしてみます。つまりこのような事です。(※以下、F[_]でなくS[_]を用います)

trait Foo[S[_], A]
case class Bar1[S[_], A](x: A) extends Foo[S, A]
case class Bar2[S[_], A](x: S[A]) extends Foo[S, A]

Bar1とBar2の引数 x の型に注目してください。ここで肝心なのは
Bar1のxはAで、Bar2のxはS[A]ということです。xの型が違いますね。
でも両者は共通の親 Foo を持つので、Fooにアップキャストすれば同一の型になります。
やってみましょう。

val a: Foo[Option, Int] = Bar1[Option, Int](100)
val b: Foo[Option, Int] = Bar2[Option, Int](Option(100))

a.x はInt ですが
b.x はOption[Int]だという事です(※1)
Bar1では型引数としてOptionという型を渡してはいますが、これは「ただ渡しただけ」で
xという値そのものとはまったく関係ないです。ただ渡しただけです。これ重要です。

つまり、Bar1, Bar2が保持している x という値は本当は異なる型の値だけれども、アップキャストしてFooとして表せば共にFoo[Option, Int]となり、この時aとbは同一の型です。

Freeモナドでもまさに似たような事を行っているので、確認してみましょう。
先ほどのBar1のようにA型の値を受け取るのがFree.pureで、Bar2のようにS[A]型の値を受け取るのはFree.liftFです。

import scalaz._
val a: Free[Option, Int] = Free.pure [Option, Int](100)
val b: Free[Option, Int] = Free.liftF[Option, Int](Option(100))

OptionをFreeにするメリットは無いですが、ひとまずここで行われている事を確認してみます。
まず、関数pureとliftFに渡した値をFreeがどう持っているかですが、これは先ほどと同じくFreeを親とするReturnやSuspendといったサブクラスのインスタンスが作られ、その内部でそれぞれA型とS[A]型の値を保持しています(※2)。なので、さきほどのFooの時と同じく a が保持している値はIntですが、 b が保持している値はOption[Int]です。
特に大事なのはaです。しつこく書きますが、Optionという型は渡しただけで保持しているのはInt型の値です。
でも、このa, bは親のFreeで表すと Free[Option, Int] 型であり、"同一の型"として扱えます。さきほどと全く同じですね。
そして同一の型という事は…そう、この a,b は最初にでてきたPairOpt型になれます。

val p: PairOpt[Free[Option, Int]] = Option(a, b)

面白いですね。

さて、では実際のコードにおいて同じような事をしているcons関数を見てみます。
ちなみにここでは解説のために、なるべく一時変数に入れて型注釈を付けたコードにしてあります。

type List[A] = Free[PairOpt, A]

/** 中略 */

def cons[A](head: A, tail: List[A]): List[A] = {
  val headF: Free[PairOpt, A]       = Free.point[PairOpt, A](head)
  val headL: List[A]                = headF
  val tpl:   PairOpt[List[A]]       = Option(headF -> tail)
  val tplF:  Free[PairOpt, List[A]] = Free.liftF[PairOpt, List[A]](tpl)
  val tplF2: List[List[A]]          = tplF
  Free.freeMonad[PairOpt].join(tplF2)
}

なんだか見た目こわいですが、変数 tpl を作るまでは先ほどと同じ事をしているのでまずはその部分について書きます。

まず、List[A] は 事前の型宣言の通り Free[PairOpt, A] です。このPairOptが今回FreeにするS[_]です。という事で引数 tailのFree[PairOpt, A]はFree[S, A]ですね。
先ほどまではAとS[A]の2つの値を Free[S, A] にしてましたが、その内の1つ S[A] の値はすでにFree[S, A]になった後の形で引数 tail として渡されている訳です。なので、あとはAの値をFree.pureしてあげれば良い訳ですね。
その他は基本的に全く同じ事です。1行目から確認してみましょう。

まず、A型の値である head を、Free.point[PairOpt, A](head)としてFreeにLiftします。(pointはpureの別名で同じものです)
この時PairOptという型を型引数として渡してはいますが、「ただ渡しただけ」で、Freeに渡され内部で保持している値自体はあくまで A型のままです。 そして、このheadFの型はList[A]でもあります（今回は headL という変数にList[A]と型注釈を付けておきました）。
さて、haedL と tail はこの時点で List[A] という同じ型です。あとはもう、TupleにしてOptionに包めば、PairOpt型になれますね。 という事で作ったPairOpt型の値を tpl という変数に入れてます。 ここまでは、すべて先ほどFooでやったのと全く同じ流れです。

あとはこれを List[A]の値にするだけです。変数 tpl は PairOpt[List[A]] なのでこれをFreeにLiftするために Free.liftF を使います。すると Free[PairOpt, List[A]] が返される訳ですが、これはList[List[A]]でもあるので、joinすればList[A]が得られそうですね。という事でモナドインスタンスを得てjoinしています。型エイリアスや型の入れ子でちょっと追いづらいですが、ゆっくり追ってみてください…。
ともあれ、めでたくheadとtailは「同一の型のTuple」として扱われ、Tupleという文脈を伴ってFreeモナドになったのでした。

FreeへのLift周りで混雑しましたが、話を戻すと、肝心なのはheadとtailが同一の型と言っても、headが持ってる値自体は A型 であり、tailが持ってる値はS[A]型(※3)という事です。 この違いはFreeモナド上でどうなっているかというと、実はmap/flatMapの処理が異なります。それが今回のポイントその2です。

FreeモナドのPure(Return)とSuspendの内部処理の違い

さて、ここでFreeモナドのmap/flatMapの実装を確認していきます...が、ScalazのFreeはStackless化されていて追いづらいと思うので、今回はyuroyoroさんの解説Freeモナド in ScalaにあるFreeモナド実装を基本としつつ S[A]が直接Freeになってもよい事を別の角度からイメージするため LiftFree をFreeのサブクラスとして追加した実装を用います。また、Functorはscalazのものを使います。

/**
 * Freeモナド.
 * 理解を補うために、LiftFreeを別途用意
 */
import scalaz._
import scalaz.syntax.functor._

abstract class Free[S[_] : Functor, A] {
  def flatMap[B](f: A => Free[S, B]): Free[S, B]
  def map[B](f: A => B): Free[S, B] = flatMap(x => Pure(f(x)))
}

case class Suspend[S[_] : Functor, A](x: S[Free[S, A]]) extends Free[S, A] {
  def flatMap[B](f: A => Free[S, B]): Free[S, B] =
    Suspend[S, B](x.map( _.flatMap(f) ))
}

case class LiftFree[S[_] : Functor, A](x: S[A]) extends Free[S, A] {
  def flatMap[B](f: A => Free[S, B]): Free[S, B] =
    Suspend[S, B](x.map(f))
}

case class Pure[S[_] : Functor, A](x: A) extends Free[S, A] {
  def flatMap[B](f: A => Free[S, B]): Free[S, B] =
    f(x)
}

まずmapですが、Free#mapは親で実装されていて、中身もflatMapを呼び出してpureする形なので実質flatMap依存です。という事でサブクラスのflatMapを見ていきます。

flatMapですが、SuspendやLiftFreeでは、保持している値 x の型が S[A](※3)で、SがFunctorなので、そのFunctorのmapを使って処理しています。
対してPureは値 x がただのA型なので、実はSのmapを呼び出したりなどはしません。本当に単純に、関数を適用して終わりです。
ただし関数 f 自体が A => Free[S, B] である通り、この関数によりもたらされるS[_]の文脈次第では次もPureであるとは限りませんが、flatMapは「合成」なので、『PureがSuspendと合成されたらもうPureじゃない』と言えば感覚的にもわかりやすい気がします。

さて、話を先ほどのPairOptという特殊なTupleの話に戻します。今回のコードでは、このTupleの要素2つは本当は異なる型の値をFreeで包み同じ型と見なしたものでした。
片方はただのAの値を包んだFree、もう一方はS[_]の文脈を持った値を包んだFree。
これらはFreeなので、mapやflatMapを呼び出せます。しかし実際にそれらが動く時は、 PureとSuspend(LiftFree)に分かれて、保持している値がただのAなのか、S[A]なのかに応じて Aに対しては単純に関数を適用し、S[A]に対してはSの(Functorとしての)mapを使って関数を適用する、ということです。 上手くできてますね。

さて、更にそれを今回の実装にあてはめて確認すると、まずheadは、A型の値なので関数適用して終わり。 tail側のS[A]はS[_]の文脈...ここではTupleという文脈(構造)を持つので、tail自体がTupleな訳ですね。 そうして現れたtailというTupleに対してmap/flatMapで関数を適用すると、先ほどと同じく headの方のAにはただの関数適用、tailの方は再びS[_]の文脈のmapを... と再帰的にたどっていく事になり、すべての要素に関数が適用される訳です。

あとがき

以上、理解したことまとめでした。今回、どうしても長くなりそうだったのでいろいろざっくりとした説明でしたが、アウトラインの把握に役立てばと思います。

ちなみに全く触れてませんでしたが、なぜTupleの外側をOptionで包んでいるかは、単にNoneをListのNilとして使うためですね。

あと、今回用意した LiftFree について補足すると、これはじつは一度mapやflatMapを行うとSuspendに移るので、FreeモナドとしてはSuspendとPureがあれば充分な訳ですが、たとえばScalazのFree.liftFでやっているSuspend(S.map(value)(Return[S, A]))というコードと、今回のLiftFreeを使ったあとmap(identity)するような LiftFree(value).map(identity) が同等のコードである事が、今回のLiftFreeのコードを追うと伺えるかと思います。
またFreeの内部に蓄積される再帰的な構造の流れがイメージしづらいうちも、こういったシンプル実装を使って戯れるのが良いのかなと思います。
今回のコード全体はGistにあげてあります。FreeをScalazから移し替えた以外は概ねそのままです。

間違いなど気づいたことありましたら、コメントかツイッター(@awekuit)までお知らせ下さい。

余談

私がxuwei_kさんのブログの初版のコードをScalaz 7.1に移植できないと最初思った理由はListのconsの所で、S[Free[S, A]]をliftFしてFree[S, Free[S, A]]にするしか無くそれでは困るのでは？と思ったからですが、本文中にもありますがこれは単純な入れ子でした。
Free[S, Free[S, A]] は List[List[A]] です。とっても入れ子です。
なので、外からMonadのインスタンスでjoinすればいいんです。

…1階カインド型と具体型が型引数に両方でてくるの難しい！

今は具体型の方を意識すれば良いのかなと思ってます。

  • ※1: 親のFooの方にxという値を宣言してないので、a,bをFooにアップキャストした時点でxは呼び出せませんがここでは無視します
  • ※2: 実際はS[A]をliftFすると、S[_]のmapを使って中身のA型の値をすべてFree.pureで包み S[Free[S, A]] になります。ちなみにこの時pureは A => Free[S, A] をする訳ですが、このとき渡されるSも「ただ渡しただけ」です
  • ※3: S[Free[S, A]] を含みます