一時期良く聞いたFree Monad, 最近KMC の中で話が出て, いまいちよくわからないところとかが出てきたので, ちょっとメモ的な.

まず定義

ここ にある.

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

instance Functor f => Monad (Free f) where
    return = Pure
    Pure a >>= k = k a
    Free fm >>= k = Free (fmap (>>= k) fm)

なんなのか

λカ娘の5巻, 第三章 「侵略者と転校生とアイドルとイカが再帰を学ぶそうですよ！」 に, 一般的なリスト

data List a = Nil | Cons a (List a)

を,

data Rec f = In (f (Rec f))

type List a = Rec (L a)
data L a x = Nil | Cons a x

のように定義し, 一般的なツリー

data Tree a = Prune | Leaf a | Branch (Tree a) (Tree a)

をさっきのRec をこっちでも使って,

type Tree a = Rec (T a)
data T a x = Prune | Leaf a | Branch x x

と書くことができると書いてあった.

もともとList とTree は再帰的構造を持っていたが, この書き換えによって, L , T という再帰的構造を持たない単なるデータ型と, Rec という再帰構造だけを持つ型の組み合わせに分けることができる.

これと,

cata :: Functor f => (f a -> a) -> (Rec f -> a)
cata phi (In x) = phi (fmap (cata phi) x)

ref

• そろそろFreeモナドに関して一言いっとくか - fumievalの日記 http://d.hatena.ne.jp/fumiexcel/20121111/1352614885