Freeモナド
code:purs(hs)
data Free f a = Pure a
| Join (f (Free f a))
データ型の定義自体にはfにFunctorの制約はない
f :: * -> *ではある
Joinの部分の値コンストラクタにもFreeという名前を使うことが多いが、分かりづらいmrsekut.icon
型コンストラクタと値コンストラクタの名前の重複によって再帰が見づらい
だから、PureとJoinという名前を使ったほうが親切だと思うmrsekut.icon
Freeの構成を、PureとJoinでした場合の定義
code:hs
data Free f a = Pure a
| Join (f (Free f a))
instance Functor f => Functor (Free f) where
fmap = (<$>)
-- fmap f (Pure x) = Pure $ f x
-- fmap f (Join fx) = Join $ fmap (fmap f) fx
instance (Functor f) => Applicative (Free f) where
pure = Pure
Pure f <*> a = fmap f a
Join f <*> a = Join $ fmap (<*> a) f
instance Functor f => Monad (Free f) where
return = Pure
Pure x >>= f = f x
Join x >>= f = Join $ fmap (>>= f) x
これが最も一般的mrsekut.icon
FreeをPureとBindで構成した場合
code:hs
data Free f a where
Pure :: a -> Free f a
Bind :: f x -> (x -> Free f a) -> Free f a
instance Functor (Free f) where
fmap = (<$>)
instance Applicative (Free f) where
pure = Pure
f <*> x = f >>= \f' -> x >>= \x' -> pure $ f' x'
instance Monad (Free f) where
return = Pure
(>>=) (Pure a) a2fb = a2fb a
(>>=) (Bind fx x2fa) a2fb = Bind fx (a2fb <=< x2fa)
Monadとなる条件を考えると、PureとBindで十分なので、「fがFunctorである」という条件は不要になる 参考
わかりやすいmrsekut.icon
説明がそれなりに簡潔で良い
出てくるコードは上のHaskell for allの類似
かなり親切で詳細
これ読んだおかげで細かい箇所の解像度が上がったmrsekut.icon
Freeモナドの4種の定義
圏論
pursの場合
むかし
code:purs(hs)
-- Type
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
data FreeView f a b = Return a
| Bind (f b) (b -> Free f a)
newtype ExpF f = ExpF (Val -> Free f Val)
data Val
-- Functor
instance Functor (Free f) where
map f k = f <$> k
-- Apply
instance Apply (Free f) where
apply = ap
-- Bind
instance Bind (Free f) where
bind (Free v s) k = Free v (snoc s (ExpF (unsafeCoerceBind k)))
where
unsafeCoerceBind :: forall a b. (a -> Free f b) -> Val -> Free f Val
unsafeCoerceBind = unsafeCoerce
-- Applicative
instance Applicative (Free f) where
pure = fromView <<< Return
-- Monad
instance Monad (Free f)
データ型が複雑になっている理由を解明したい #?? ここにかいてた
Free (f (Free f a))って、Free メイン (続きの計算)ってかんじなのか?
fの無数の入れ子をFreeと見ることが出来る
f aもFree
f f f f ff f f f f faもFree
というか、このネストを潰せる、という性質はMonadにもあったもの
Free fはモナドにできるが、Free自体もモナドらしい ref よくわからんmrsekut.icon
どのへんが「Free」なのか
Maybe == Free Proxy
pursでの実装
pursではちょっと外見が異なる
code:purs(hs)
data Free f a = Free (FreeView f Val Val) (CatList (ExpF f))
Free fだけでなく、Freeそれ自体もmonad
code:hs
data MyProgram n = Old Int n | Hey n | Hello n | GoodBye
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
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
pg :: Free MyProgram ()
pg = do
Free $ Hey (Pure ())
Free $ Hello (Pure ())
Free $ Old 2 (Pure ())
Free GoodBye
main :: IO ()
main = runProgram pg
data Fix f = Fix (f (Fix f))
todos
pursのFreeの構成の意味
TrampolineモナドとFreeTどっちを使うのか
コンパイル後JSでどんなふうに変わっているのか観察
関連
処理効率を考えて実装されたFreeモナド
ASTのデータ型からFreeのアクションを導出する
論文
ユースケース
2Dゲーム
DSLがいまいちピンときていないmrsekut.icon
Parsecみたいに、Parser ..という型で区切られた世界のこととかをそう呼んでるのか?
普通に型で区切られた世界とどう違うのか
あ、普通にMonadを作ることをDSL作成と言ってるだけか
「Monadを作ること」が「DSLを作ること」にほぼ同じなのであれば、「Freeモナドを作ることの嬉しさ」として「DSLを作れること」って挙げるのおかしくない?
あくまでも「Freeモナドの嬉しさ」は「簡単にモナドを作れること」であって、
「DSLを作ること」は「Monadの嬉しさ」の一つに過ぎないだろう
Monad構造を動的に操作する例
それを使ってデータの操作をした有用な例みたいなのを見てみたい
ps
実用例