Freeモナドって何なのさっ!?

最近Haskellerの間でFreeモナドが熱いです。
Haskellで悟りを開いた人がFreeモナドで再び悟りを開いたりして、なんかよく解らないけど凄いことになっている今日このごろですが、すっかり乗り遅れていました。どうも、貴女のちゅーんです。
で、皆こぞって「すごいすごい」と言っているFreeモナドなので、流石にいつもまでも全然知らないのはマズイんじゃないかなぁとか思って、重い腰を持ち上げ調べながらこの記事を書き始めたワケですよ。はい。*1

けっこう急ぎで勉強して書き上げたので随所に間違いあるかもです。ツッコミお待ちしてます。
さて、この「Freeモナド」について、オレオレ定義で簡単に言葉にすると。「Functorと組み合わせて様々な挙動を実現できるモナド」です。

大抵「Monadインスタンス」というと、MaybeにしてもIOにしても、わりと具体的な事象を扱ってますが、このFreeモナドはそれ自体が抽象的です。
具体的な事象を扱うFunctorと組み合わせてはじめて、具体的な事象を扱うモナドになるワケですね。


先程「Functorと組み合わせて」と書いた以上、当然のごとく、あらゆるFunctorがFreeモナドと組み合わせる事ができるワケですけども、Freeモナドで扱うためには、そのFunctorが、それ自身のFunctorになる構造を基本として考えていく必要があります。
言葉で言うとややこしいので、具体例を示しましょう。

*Main> :t [[[[[[[[]]]]]]]]
[[[[[[[[]]]]]]]] :: [[[[[[[[a]]]]]]]]
*Main> :t Just (Just (Just (Just Nothing)))
Just (Just (Just (Just Nothing)))
  :: Maybe (Maybe (Maybe (Maybe (Maybe a))))

例のように、その型自体を再帰的に包み込んだFunctorを拡張して扱います。
いずれも[]やNothingが終端になっているので、終端の型変数 a は多態に扱う事ができます。*2
注目したいのは、再帰の深さが深くなるほど、型定義も深くなってしまっている点です。
こういった構造を同じ型として扱えるようにするのが、Freeモナドを理解する第一歩となります。

まず、Freeというデータ型は、次のように定義されます。

data Free f r = Free (f (Free f r)) | Pure r

Pure rはリストの[]とか、MaybeのNothingみたいなもんですね。
では、"Free (f (Free f r))"となっている部分について見てみましょう。
型名とデータコンストラクタが共にFreeとなっていて若干ややこしいので、ちょっと読み替えてみます。次のようにしても等価です。

data FreeT f r = FreeC (f (FreeT f r)) | Pure r

外側のFreeCがデータコンストラクタです、内側のFreeTで、再帰的な型になってるのが解ると思います。
fとFreeTがお互いに包み合ってる、なんだか不思議な構造です。

で、このFree型を、先ほどのリストの例で書くと次のようになります。

*Main> :t Free [Free [Free [Free []]]]
Free [Free [Free [Free []]]] :: Free [] r
*Main> :t Free [Free [Free [Free [Free [Free []]]]]]
Free [Free [Free [Free [Free [Free []]]]]] :: Free [] r

Maybe型の例だとこんな感じ。

*Main> :t Free (Just (Free (Just (Free Nothing))))
Free (Just (Free (Just (Free Nothing)))) :: Free Maybe r
*Main> :t Free (Just (Free (Just (Free (Just (Free (Just (Free Nothing))))))))
Free (Just (Free (Just (Free (Just (Free (Just (Free Nothing))))))))
  :: Free Maybe r

お!
ネストさせる回数が変わっても型は変わってないぞっ!!

というワケで、型が揃えられたので、晴れてこいつらを使って色々できるようになったワケです。
Nothingを0、JustをSuccとして、自然数に見立てた計算とかもできそうですが、そういう変態的な事をするのは今回の目的では無いのでちゃっちゃと進めます。*3


突然ですが、Freeはモナドです。
今回の記事の題材が「Freeモナド」ですし。

というわけで、Freeモナドの定義は次のようになっています。

instance Functor f => Monad (Free f) where
  return = Pure
  Free x >>= f = Free (fmap (>>= f) x)
  Pure x >>= f = f x

Freeモナドの>>=の動きを、実際に簡約して追ってみましょう。

Maybeの場合

Free (Just (Pure ())) >> Free (Just (Pure ()))
  == Free (Just (Pure ())) >>= (\_ -> Free (Just (Pure ())))
  == Free (fmap (>>= (\_ -> Free (Just (Pure())))) (Just (Pure ())))
  == Free (Just (Pure () >>= (\_ -> Free (Just (Pure ())))))
  == Free (Just ((\_ -> Free (Just (Pure ()))) ()))
  == Free (Just (Free (Just (Pure ()))))

つまり、

Free (Just (Pure ())) >> Free (Just (Pure ()))
  == Free (Just (Free (Just (Pure ()))))

リストの場合

Free [Free [Pure ()]] >> Free [Free [Pure ()]]
  == Free [Free [Pure ()]] >>= (\_ -> Free [Free [Pure ()]])
  == Free (fmap (>>= (\_ -> Free [Free [Pure ()]])) [Free [Pure ()]])
  == Free [Free [Pure ()] >>= (\_ -> Free [Free [Pure ()]])]
  == Free [Free (fmap (>>= (\_ -> Free [Free [Pure ()]])) [Pure ()])]
  == Free [Free [Pure () >>= (\_ -> Free [Free [Pure ()]])]]
  == Free [Free [(\_ -> Free [Free [Pure ()]]) ()]]
  == Free [Free [Free [Free [Pure ()]]]]

つまり、

Free [Free [Pure ()]] >> Free [Free [Pure ()]]
  == Free [Free [Free [Free [Pure ()]]]]

といった感じで、構造が合成されます。
ぶっちゃけ、これがFreeモナドの全てだったりします。では、「コレを使って何ができんの?」という話をしていきましょう。


ちょとした言語、「挨拶言語」を考えましょう。
この言語は、「Hello!!!」と出力する命令、「Hey!!!」と出力する命令、「GoodBye!!!」と出力して終了する命令、それから年齢を引数に取って、「I'm x years old」と自己紹介する4つの命令を持っています。

ではまず、この構文木のデータを定義してみます。

data MyProgram n = Old Int n | Hey n | Hello n | GoodBye

例えば、これを使って、"Hello!!!" "Hello!" "GoodBye!!!"と表示する場合、こんな構造になります。

*Main> :t (Hello (Hello (GoodBye)))
(Hello (Hello (GoodBye))) :: MyProgram (MyProgram (MyProgram n))

"Hey!!!" "GoodBye!!!" と表示したい場合、こんな構造になります。

*Main> :t (Hey (GoodBye))
(Hey (GoodBye)) :: MyProgram (MyProgram n)

困ったことに、それぞれ型が違ってしまっているので、このままではこの構文木を実行するためのrunProgram関数が実装できません。
そこで、先ほどのFreeを使って、型を揃えてみましょう。

まずはFunctorにしてやります。

instance Functor MyProgram where
  fmap f (Old o n) = Old o (f n)
  fmap f (Hey n) = Hey (f n)
  fmap f (Hello n) = Hello (f n)
  fmap f GoodBye = GoodBye

でもって、Freeで型を整えます。

*Main> :t Free (Hello (Free (Hello (Free GoodBye))))
Free (Hello (Free (Hello (Free GoodBye)))) :: Free MyProgram r
*Main> :t Free (Hey (Free GoodBye))
Free (Hey (Free GoodBye)) :: Free MyProgram r

これで、この構造を順に解析して、処理を実行するrunProgram関数を実装できますね。Pureが来た場合は"return"を表示する事にしておきます。

runProgram :: Show r => Free MyProgram r -> IO ()
runProgram (Free (Old o n)) = putStrLn ("I'm " ++ show o ++ " years old") >> runProgram n
runProgram (Free (Hey n)) = putStrLn "Hey!!!" >> runProgram n
runProgram (Free (Hello n)) = putStrLn "Hello!!!" >> runProgram n
runProgram (Free GoodBye) = putStrLn "GoodBye!!!"
runProgram (Pure r) = putStrLn $ "return " ++ show r

実行結果:

*Main> runProgram $ Free (Hello (Free (Hello (Free GoodBye))))
Hello!!!
Hello!!!
GoodBye!!!
*Main> runProgram $  Free (Hey (Free GoodBye))
Hey!!!
GoodBye!!!

Freeはモナドなので、 >> で処理を繋げながら実行できます。

*Main> runProgram $ (Free (Hello (Pure ())))
Hello!!!
return ()
*Main> runProgram $ (Free (Hello (Pure ()))) >> (Free GoodBye)
Hello!!!
GoodBye!!!
*Main> --勿論do構文でも使えます
*Main> :{
*Main| runProgram $ do {
*Main| Free $ Hello (Pure ());
*Main| Free GoodBye
*Main| }
*Main| :}
Hello!!!
GoodBye!!!

毎回Freeを意識しながら書くのも大変なので、関数にしてしまいましょう。

liftF :: Functor f => f r -> Free f r
liftF cmd = Free (fmap Pure cmd)

old :: Int -> Free MyProgram ()
old o = liftF (Old o ())

hey :: Free MyProgram ()
hey = liftF (Hey ())

hello :: Free MyProgram ()
hello = liftF (Hello ())

goodBye :: Free MyProgram ()
goodBye = liftF GoodBye

後は書くだけです。

--サブルーチン
sub :: Free MyProgram ()
sub = do
  hello
  old 25

pg :: Free MyProgram ()
pg = do
  hey
  sub --サブルーチン呼出し
  hey
  goodBye

main :: IO ()
main = runProgram pg

実行結果:

Hey!!!
Hello!!!
I'm 25 years old
Hey!!!
GoodBye!!!

たったこれだけの定義で独自のモナドになってしましました!
関数定義も分岐も再帰も、Haskellの機能そのまま使えば良いですし、do構文で手続き的な記述ができますし、処理する側でIOや副作用の提供も自由自在です。

runProgramは構文を順に追って好きな時に実行できるので、キーが入力されるまで待機したり、その間もバックグラウンドでアニメーション動かしたり、出来ること上げていくとキリが無い感じです。


てなワケで、「Functorと組み合わせて手軽に独自のモナドに拡張できるFreeモナド」のお話でした。*4
ゲームを作るにあたって、継続モナドを使って実装しようとしていた事が、Freeモナドならわりと簡単に実装できそうな感じですし、チーム開発でちょっとした開発フレームワークを組み立てるのにも役立ちそうです。

【参考資料】Haskell for all: Why free monads matter
http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html?m=1

*1:前々から進めてるゲーム開発にも使えそうですし。

*2:が、今回はその事はあまり重要では無いです。

*3:>>=がそのまま加算になりますね><。

*4:理解と実用性を重視して書いたのでFreeモナドの本質的な話とはちょっとズレてるかもですが・・・