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

前おき

この記事は型引数の基本から学ぶ、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

• Scalaにおける型パラメータの部分適用 [({type F[X] = G[A,X]})#F] について | ( ꒪⌓꒪) ゆるよろ日記
• scalaz - Free