TreeはMonadなのか

前提

目的

1. 最近関数型デザイン本を読んだのでとりあえずアウトプットしたい
2. なんか難しい単語使いたい
   • 「アボガドロ定数」とか習ったときすぐ口に出さなかったですか？あのノリです
3. プリミティブな奴らじゃなくて、自分でモナドインスタンス作ってみたかったから

注意

• 「モナド完全に理解した！！状態」なので多分間違ってる。冗談半分で聞いて下さい。
• 兄妹の感動の物語も含まれてます。涙腺の弱い方は泣いて下さい。

Monadに触る前に

第一話 「オラ、Monadさなるだ！！ その若き少年の名はTree」

sealed trait Tree[+A]

final case class Branch[A](l: Tree[A], r: Tree[A]) extends Tree[A]
final case class Leaf[A](value: A) extends Tree[A]

とある自然豊かな田舎で育った少年Tree。彼は早くに親に捨てられ、物心つく頃にはすでに物心がついていた。
単純な構造でBranchには2つのTreeを格納することができて、LeafはただのTを格納することができる。そいつらはTreeを継承することで自身もTreeとして振る舞う。
彼はモナドになるべく立ち上がった戦士。果たして若き少年はMonadになれるのか。もう誰かが傷つくところは見たくない。

第二話 「待って!!お兄ちゃん!! 敵は一人じゃない。でも私たちも一人じゃない」

まって、こんな最初から数々のプログラマーを葬ってきた天下の悪魔人を倒せるはずがないじゃない。
噂によると実は抽象概念の中でもMonadは親分みたいなやつで、子分が2人いるらしいわ。
その四天王の名はFunctorとApplicative。こいつらを倒さないとMonadと対峙するどころか死ぬ場所を選ぶことすら許されない。
さあ深い絆で結ばれた兄妹の行方は...

第三話 「我が名はFunctor。 圧倒的抽象力の前にひれ伏す兄妹」

定義

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

あれ、めっちゃ簡単。名前はかっこいいのに中身覗いたらmapしかない...。　　
このmapってみんなが使ってるあのmapです。ListとかOptionとかに生えてるでしょ？

圧倒的抽象力(笑)、これじゃ抽象四天王の面目丸潰れね...

Functor則

map(fa)(identity) == fa

実は返り値がF[B]だったら何でもいいのかというとそうではない。
これはfaに対して恒等写像を渡したときに元と同じであれということです。まあ当たり前ですね。
私たちは一体何に怯えていたの？さあ、この戦いが終わったら、結婚するんだ。

実装してみよう

sealed trait Tree[+A] {
    def map[B](f: A => B): Tree[B] = this match {
        case Leaf(v) => Leaf(f(v))
        case Branch(l, r) => Branch(l.map(f), r.map(f))
    }
}

val treeFunctor = new Functor[Tree] {
    override def map[A, B](fa: Tree[A])(f: A => B): Tree[B] = fa.map(f)
}

まあまだ簡単ですね。Functor則ももちろん満たします。
証明はまだ必要ないくらいに自明ですよね。

第四話 「ふっ、奴は四天王の中でも最弱... 高笑いする奴の名はApplicative」

定義

trait Applicative[F[_]] {
    def unit[A](a: => A): F[A]
    def ap[A, B](fab: F[A => B])(fa: F[A]): F[B]
    def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}

ふぇぇぇ、おにいちゃん... apさんが怖いよぉ🥺🥺
なぁに、よく見てごらん。奴はFの仮面を被ったただの写像だ。高階関数の圧倒的見た目に騙されるんじゃない。
apはmap2を元に作れるしmap2も同様にapを元に作れるじゃないか。
どっちか実装してあげればしっかり動くのさ。

ちょっと寄り道して

trait Applicative[F[_]] extends Functor[F] {
    def unit[A](a: => A): F[A]
    def ap[A, B](fab: F[A => B])(fa: F[A]): F[B]

    def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
        ap(ap(unit(f.curried))(fa))(fb)

    def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
        map2(fa, fb)((_, _))
}

実はunitとapでさまざまな関数を表現できるからApplicativeっていうらしい。名前の由来を知ると結構可愛いとさえ思ってしまう。しかし我々は前に突き進まなければいけない。

まって、productとかいうプリミティブじゃないやつ部外者がでてきた。誰だよお前。お兄ちゃん、私に任せて。
誰もおにいてゃんに指一本触れさせない。もうあんな歴史繰り返したくないの。

絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。絶対倒す。

Applicative則

def associate[A, B, C](value: (A, (B, C))): ((A, B), C) = value match {
    case (a, (b, c)) => ((a, b), c)
}

// 1(恒等写像)
map(fa)(identity) == fa

// 2(準同型写像)
map(map(fa)(f))(g) == map(fa)(g compose f)

// 3(結合法則)
product(product(fa, fb), fc) == map(product(fa, product(fb, fc)))(associate)

おにいちゃん、ごめん。productさんと結婚することになったの。
私は古より結ばれし固い結合法則によって支配されていた。でも決して私のこの魂まで奴に売ったわけじゃない。

私が倒されても、きっと第2第3の私が立ち上がるのだから。

実装してみよう

val treeApplicative = new Applicative[Tree] {
    override def unit[A](a: A): Tree[A] = Leaf(a)

    override def ap[A, B](fab: Tree[A => B])(fa: Tree[A]): Tree[B] =
        fa match {
            case Leaf(v) => fab.map(ab => ab(v))
            case Branch(l, r) => Branch(ap(fab)(l), ap(fab)(r))
        }
}

第五話 「さよなら＿＿。 お兄ちゃん。 裏切りのflatMap」

定義

trait Monad[F[_]] extends Applicative[F] {
    def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}

えっ、flatMap... おまえMonadに加担していたのか...?
ListともOptionとも仲良しだったあいつが... いつもそばにいたやつが実はラスボスだったのだ。こんな感じに仲良しな仲間が実はラスボスだったアニメあったよね。

ちょっと寄り道

flatMapがあるとまじで何でもできる。
今まで限られたリソースで戦ってきたけどついに解禁されたのだ。早速武器調達...

sealed trait Tree[+A] {
    def map[B](f: A => B): Tree[B] = this match {
        case Leaf(v) => Leaf(f(v))
        case Branch(l, r) => Branch(l.map(f), r.map(f))
    }

    def flatMap[B](f: A => Tree[B]): Tree[B] = this match {
        case Leaf(v) => f(v)
        case Branch(l, r) => Branch(l.flatMap(f), r.flatMap(f))
    }
}

trait Monad[F[_]] extends Applicative[F] {
    def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

    override def ap[A, B](fab: F[A => B])(fa: F[A]): F[B] =
        flatMap(fa)(a => fab.map(ab => ab(a)))

    // Kleisli射
    def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] = a =>
        flatMap(f(a))(g)
}

なんかmapとflatMapの実装似てない？ うるさい。あとでリファクタリングするよ、ママ。

モナド則

// 1(結合律)
flatMap(flatMap(fa)(f))(g) == flatMap(fa)(a => flatMap(f(a))(g))

// 1'(結合律) composeを実装することで上記の結合律が結合律に見える！！
compose(f, compose(g, h)) == compose(compose(f, g), h)

// 2(同一律)
compose(f, unit) == f
compose(unit, f) == f

結合律むずくないかァ↑↑！？
でも見て、歴史って偉大なの。昔の偉い人がね、composeっていう魔法をかけるとこれただの結合律じゃないか。
関数に対して結合律をflatMapとかいうあたまでっかちに表現させるからこうなるの。このcompose、圏論の世界では名前がついてるんですって。

その名も... 「Kleisli射」。かっけぇ...

実装してみよう

val treeMonad: Monad[Tree] = new Monad[F] {
    override def flatMap[A, B](fa: F[A])(f: A => Tree[B]): Tree[B] = fa.flatMap(f)
}

最終話 「永遠(とわ)に...。」

やったね！！　Treeは晴れてモナドになれたのでした。
ありがとう。 Functor。
ありがとう。 Applicative。
またね。 Monad。