ということで今回は、Freeモナドの「Freeの部分だけを味わっちゃう」コースを用意しました。
つまりFreeモナドではなくてFreeマグマ（マグマについては後述）とかFreeモノイドとかを見て、何となくFreeなんちゃかがどういう物なのか感じてみようということです。
全編、Free, but not as in beer or speech - Dan Piponiをフルにパク参考にしています。
もとはHaskellですが分かりやすい図が一杯載っているので、ぜひそちらも一緒に見てみてください。
マグマ
マグマというのは、ざっくり言うと、「群から逆元を取り去った「モノイドから単位元を取り去った「半群から結合法則を取り去った「もの」」」」がマグマです。 もはや何も残っていないんじゃないかと思いますが、「とりあえず何か一つ足し算的な演算が定義されている」という認識で良いんじゃないでしょうか。*1
一応、
演算について閉じていること: M の任意の元 a, b に対して、その演算結果 a • b が再び M に属する。
という条件が必要なようです。
詳しくはマグマ (数学) - Wikipediaに譲ります。
マグマの持つ演算をoとしたときの実装例は以下のようになります。
Freeマグマ
ここからが本題、Freeマグマです。
おもむろに木構造のようなADTを作り、これをFreeMagmaと名付けます。
// FreeMagmaの定義 sealed trait FreeMagma[A] case class Var[A](a: A) extends FreeMagma[A] case class Tree[A](a: FreeMagma[A], b: FreeMagma[A]) extends FreeMagma[A]
そして、FreeMagma[A]をMagmaのインスタンスにします。
演算oは、引数m1, m2をTree(m1, m2)のように木にする操作ということにします。
// インスタンス定義 implicit def magmaFreeMagmaInstance[A] = new Magma[FreeMagma[A]] { override def o(m1: FreeMagma[A], m2: FreeMagma[A]): FreeMagma[A] = Tree(m1, m2) }
FreeモナドでもあるようなインタプリタをFreeマグマでも実装します。
しかしFreeマグマの中身を取り出しながら関数fを適用という流れを再帰的に繰り返しつつoでまとめていくだけなので簡単です。
// インタプリタの定義 def interpretMagma[A, B: Magma](f: (A => B), a: FreeMagma[A]): B = (f, a) match { case (f, Var(a)) => f(a) case (f, Tree(a, b)) => o(interpretMagma(f, a), interpretMagma(f, b)) }
実行例を含めた全体はこんな感じになります。
コメントにもありますが、FreeMagma[String]を使ってマグマっぽいことができています。
なんだかFreeモナドっぽい感じですね。
モノイド
マグマだけだと物足りないのでモノイドもやります。
モノイドの説明は割愛するとして、実装はこんな感じです。
Freeモノイド?
先ほどと同じように木構造のADTを考えます。
// モノイド則を満たさない怪しげなFreeMonoid(?)の定義 sealed trait FreeMonoid[A] case class MEmpty[A]() extends FreeMonoid[A] case class Var[A](a: A) extends FreeMonoid[A] case class Tree[A](a: FreeMonoid[A], b: FreeMonoid[A]) extends FreeMonoid[A]
コメントでもろバレですが、このような構造だとモノイド則を満たしません。 どうなるかというと
o(Var("a"), MEmpty()) != Var("a") // a + empty == aというモノイド則に反している。
となってしまいます。
FreeMonoid[A]がMonoid[A]のインスタンスになってくれないと、さきほどと同様のテクニックを使えません。
Freeモノイド
木構造がダメだったので、別のデータ構造を使う必要があります。
ちょうどいいことにListはモノイドのインスタンスに出来るようなので、これをFreeMonoidとして扱います。
// FreeMonoidの定義 type FreeMonoid[A] = List[A] object FreeMonoid { def apply[A](xs: A*): FreeMonoid[A] = xs.toList // 後で使うときに正体がListだとばれないように隠蔽 val empty = Nil // 同上 }
インスタンスはこんな感じになります。
// インスタンス定義 implicit def monoidFreeMonoidInstance[A] = new Monoid[FreeMonoid[A]] { override def <>(l1: FreeMonoid[A], l2: FreeMonoid[A]): FreeMonoid[A] = l1 ++ l2 override val mempty = List.empty[A] }
たしかに、モノイド則を満たしそうです。
インタプリタもさきほどとあまり変わりません。
// インタプリタの定義 def interpretMonoid[A, B: Monoid](f: (A => B), a: FreeMonoid[A]): B = (f, a) match { case (f, FreeMonoid.empty) => implicitly[Monoid[B]].mempty case (f, a :: as) => <>(f(a), interpretMonoid(f, as)) }
今回は銀行の預け入れ＆引き出しを表現してみましょう。
実行まで含めて一気に貼ってしまいます。
sealed trait BankOp case class Deposit(d: Int) extends BankOp case class Withdraw(w: Int) extends BankOp def interpretOp(b: BankOp): Int = b match { case Deposit(d) => d case Withdraw(w) => -w } def interpret(bs: FreeMonoid[BankOp]): Int = interpretMonoid(interpretOp, bs) def main(args: Array[String]) = { val program = FreeMonoid(Deposit(10), Withdraw(5), Withdraw(2), Deposit(3)) // FreeMagma[String]で、String => Intな関数fを適用しながらMagma[Int]を利用したのと同じ原理。 // BankOpはMonoidではないが（＝Monoidのインスタンスを具体的に定義していないが）、 // FreeMonoid[BankOp]の中身を取り出しながら、BankOp => Intな関数fを適用していくと // Monoid[Int]を利用することが出来る。 // BankOpでもMonoidっぽいことができるようになった！ val result = interpret(program) println(result) // 6 }
interpretOpはマグマの例ではString => Intな関数のfでした。
したがって、fと同じようにinterpretMonoidの第一引数として渡されています。
intepretの引数bsはマグマの例ではTree(Var("a"), Tree(Var("a"), Var("b")))となっていましたが、
今回の例ではFreeMonoid(Deposit(10), Withdraw(5), Withdraw(2), Deposit(3))のように操作を羅列したリストになっています。
コメントにも書きましたが、BankOpのインスタンスは何も定義していなのにFreeMonoidに包んで、モノイドのインスタンスを持つ型（Intなど）に変換する関数を定義すると、モノイドっぽい計算が出来る寸法になっています。
特に追加はありませんが、今までをまとめたコード全体は以下のようになっています。
まとめ
Freeモナドは「Free感＋モナドの難しさ」になるので慣れが必要ですが、 マグマやモノイドの実装はそこまで複雑なものではないので、FreeマグマやFreeモノイドになってもそこそこのわかりやすさになっていると思います。
インタプリタを作って値を取り出したりするFree感を味わったあとに、もう一度Freeモナドの解説を読むと、ちょっとわかった気になれそうな気が・・・したらいいなと思っています。
参照先のFree, but not as in beer or speech - Dan Piponiでは、この後でFreeモノイドではまだまだ制限が多いので、Freeモナドにしましょう！！！！！と迫ってくるので、受けて立ちましょう₍₍ (ง´･_･`)ว ⁾⁾
