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

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]] を含みます