Just $ A sandbox

プログラミングと計算機科学とかわいさ

Free Monadを使ってみよう!

続編:Free Monadを使ってみよう!(2) - みょんさんの。

Haskell楽しいです。
Haskellは純粋なのでとても大好きです。
ただ、Haskellでは副作用のあるように見える(手続きっぽい)書き方をしたくなる時がどうしてもありますので、そういうところでは手続きっぽい書き方をすることになります。
つまり、

A = do
  m <- BBB
  runSth m

のようなコードを、特にフレームワークがしっかりした大規模なプログラムではしょっちゅう見ることになると思います。
はっきり言いますが、私はこれが嫌いです。
Haskell-likeじゃない!
なので、もっとHaskell-likeな書き方をしたいです*1

はい、さて本題です。
Free Monadを使いましょう。

Free Monadモジュールの中ではFreeというそのままの名前のデータがあって、

data Free f a = Impure (f (Free f a)) | Pure a

と定義されています。データが再帰構造になっていますね?

Free Monad自体はもちろんMonadになっていて、実装は以下です。

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

これだけでは何が嬉しいのかよくわからないかもしれません。
しかし、Free MonadはFunctorの延長のようなものとして捉えること`も'できます。

さらにFree Monadは簡単にFunctorのinstanceにすることができます。
デフォルト実装はこうなっています。

instance Functor f => Functor (Free f) where
    fmap f (Pure a)    = Pure   (f a)
    fmap f (Impure fa) = Impure (fmap (fmap f) fa)

つまり、Free Monad再帰構造を持つデータ型とfmapによる変換則を定めてやれば勝手にMonadが作れるすぐれものというわけです*2


補足:
Free Monadは上のMonad則を満たせばよいだけなので、このようにわざわざデータ型とFunctorを与えてMonadにする必要はありません。
直接Monadのinstanceにしてやればそれは上のような再帰構造を持つFreeなデータ型が得られることになります。
Functorとして使うこととMonadとして使うことのどちらが便利かという話でもありますが、Functorとして使うほうが分かりやすいのではないかと思ってこのように書いています。

Free Monadを実際にMonadとして作って使う方法は参考文献の[2]に詳しく乗っていますので興味のある方はそちらを参照して下さい。

また、上に書いたFree f aのデータ構造は要はリストだと思えばよいのです。
というのも、

data List   a = Cons    a (List   a)  | Nil
data Free f a = Impure (f (Free f a)) | Pure a

ほら、同じことですよね?

要はFree Monadは、Pureな値が何かの型によってリストのように順々にくるまれた構造をもつデータ型を表していて、Listにおけるfoldのような畳み込みと同様に、Impureな部分をたどっていってPureな部分に到達するまでfmapを繰り返して処理を行います。
つまり、
[ Impure, Impure, Impure, Pure ]
な値に対して、fmapが定義されていれば、
fmap [ Impure, Impure, Impure, Pure ] ->
[ fmap Impure, Impure, Impure, Pure ] ->
[ result, fmap Impure, Impure, Pure ] ->
...
[ result, result, result, fmap Pure ] ->
[ result, result, resutl, resultPure ]
のように、fmapが順々に走査していって何かを処理してくれます。

このように、Free Monadは順番がキーになるようなデータ構造のものと非常に相性が良いです。
もしもあなたがそういったデータを扱っているなら、Free Monadを使ってFunctorを定義することだけからMonadを作ってみると、格段に``Haskell-like"な(あんまりdodoしていない)コードが書ける様になるかもしれません。

追記:2012/11/11

Free MonadMonad則を追加しました。
Functorとしての使い方についての補足を追加しました。

*1:もちろんこういう書き方は時には便利なのですが、あらゆるところにIOとかが混ざってくるコードはあんまり美しくは無いと思います

*2:ここではMonadとして扱うことよりもFunctor則を満たすデータ型として扱うことを念頭に置いています