読者です 読者をやめる 読者になる 読者になる

Freeモナドが分からなくてもFreeマグマなら何とか分かる気がした。[Scala]

Freeモナド、難しいですよね(´・ω・`)

ということで今回は、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としたときの実装例は以下のようになります。

gist.github.com

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, m2Tree(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))
}

実行例を含めた全体はこんな感じになります。

gist.github.com

コメントにもありますが、FreeMagma[String]を使ってマグマっぽいことができています。 なんだかFreeモナドっぽい感じですね。

モノイド

マグマだけだと物足りないのでモノイドもやります。

モノイドの説明は割愛するとして、実装はこんな感じです。

gist.github.com

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))
}

このままだとつまらないので例をDSLチックにします。*2

今回は銀行の預け入れ&引き出しを表現してみましょう。

実行まで含めて一気に貼ってしまいます。

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など)に変換する関数を定義すると、モノイドっぽい計算が出来る寸法になっています。

特に追加はありませんが、今までをまとめたコード全体は以下のようになっています。

gist.github.com

まとめ

Freeモナドは「Free感+モナドの難しさ」になるので慣れが必要ですが、 マグマやモノイドの実装はそこまで複雑なものではないので、FreeマグマやFreeモノイドになってもそこそこのわかりやすさになっていると思います。

インタプリタを作って値を取り出したりするFree感を味わったあとに、もう一度Freeモナドの解説を読むと、ちょっとわかった気になれそうな気が・・・したらいいなと思っています。

参照先のFree, but not as in beer or speech - Dan Piponiでは、この後でFreeモノイドではまだまだ制限が多いので、Freeモナドにしましょう!!!!!と迫ってくるので、受けて立ちましょう₍₍ (ง´・_・`)ว ⁾⁾

*1:ここでまさかりが飛んできて血まみれになる

*2:もちろん参考先と全く同じ例ですが・・