Free型はMonadをdata構造として表現したもの
正確に言うと「
f がFunctorの場合の Free f はMonadをdataとして表現したもの」最後の方でGADTsを使いたいのでhsで書く
このページ内では、FreeはFreeモナドとして扱う
Free型の定義
hsdata Free f a = Pure a
| Join (f (Free f a))Freeモナドの直感的な理解
Monadとなる条件とFreeの定義を見比べる
monadとなるためには以下の3つがあれば十分
hsfmap :: (a -> b) -> m a -> m b
pure :: a -> m a
join :: m (m a) -> m a一方で
Free 型をGADTで書くとhsPure :: a -> Free f a
Join :: f (Free f a) -> Free f a pure と join に対応があることがわかるこうやって見ると、
join の m (m a) の、外側の m はFunctorで十分である、ということもわかるだからあとは
map さえあればMonadにすることが出来るそこで「Functorのinstanceである型」と組み合わせることで、Monadを作ることが出来る
Free で構成したデータ型と、実際のMonadが、同じ見た目、同じ挙動になることを確認するまず普通にPreludeに入っている
Maybe で適当な実装を書いてみるhsmaybeMain :: Maybe Integer
maybeMain = do
a1 <- Just 1
a2 <- Just 1
pure $ a1 + a2ここで独自に
Maybe' を用意し、Functorのinstanceにしておくhsdata Maybe' a = Just' a | Nothing'
instance Functor Maybe' where
map f (Just' a) = Just' $ f a
map f Nothing' = Nothing'以下、
Maybe と書いたときはMonad、 Maybe' と書いたときはFunctorであることに注意する上で書いた「普通の
Maybe 」のコードを、「 Maybe' + Free 」で以下のように書けるhsmainWithFree :: Free Maybe' Integer
mainWithFree = do
a1 <- Join $ Just' $ Pure 1
a2 <- Join $ Just' $ Pure 1
Pure $ a1 + a2型こそ異なれど、ほぼ同じ見た目をしている
便利関数を用意しておけばほぼ同じ見た目になる
hsmainWithFree' :: Free Maybe' Integer
mainWithFree' = do
a1 <- just' 1
a2 <- just' 1
pure $ a1 + a2
liftF :: Functor f => f r -> Free f r
liftF cmd = Join (fmap Pure cmd)
just' = liftF . Just'
nothing' = liftF Nothing' Maybe' はMonadのinstanceではなかったことを思い出すMonadのinstnaceではないのに、Monadかのように扱えている
mainWithFree を、do式ではなく bind を使って書くとhsmainWithFree'' :: Free Maybe' Integer
mainWithFree'' = Join $ Just' $ Pure 1 >>= (\x -> Join $ Just' $ Pure 1 >>= \y -> Pure $ x + y)これを、
Monad (Free f) の定義を「左辺→右辺」に簡約していくと以下のような経過を辿るhsmainWithFree'' = Join $ Just' $ Pure 1 >>= (\x -> Join $ Just' $ Pure 1 >>= \y -> Pure $ x + y)
== Join $ Just' $ Pure 1 >>= (\x -> Join $ Just' $ Pure $ x + 1)
== Join $ Just' $ Join $ Just' $ Pure $ 1 + 1
== Join $ Just' $ Join $ Just' $ Pure 2つまり、
mainWithFree は、 Join $ Just' $ Join $ Just' $ Pure 2 と等価であるこの「
Free と Maybe の入れ子のデータ構造」が、「do式で表現されるMonad」と同じものであることがわかったこうやって見ると、タイトルの「Free型はMonadをdataとして表現したもの」の言っている意味がわかった気がする
do の中の行数の増加に伴って、 Join と Just の入れ子も深くなっていくしかし、全体の型としては
Free Maybe' Integer で一定であるちなみに、
mainWithFree はMonadなので、連結も出来るhsf :: Free Maybe' Integer
f = mainWithFree >> mainWithFree' >> mainWithFree''これを使うと別の仕方で
Free を定義できることができるhs{-# LANGUAGE GADTs #-}
data Free f a where
Pure :: a -> Free f a
Bind :: f x -> (x -> Free f a) -> Free f a pure と bind があれば十分なので、 map を別途定義する必要はないだからFunctorの制限が不要になる
実際、これを用いて上の
mainWithFree を書き直すとhsmainWithFreeB :: Free Maybe' Integer
mainWithFreeB = (Just' 1) `Bind` (\a1 -> (Just' 1) `Bind` (\a2 -> Pure $ a1 + a2)) join がないので、「do式を消したあるある見た目」っぽくなっている上の例と同様に
mainWithFreeB はMonadなので連結も出来るhsf :: Free Maybe' Integer
f = mainWithFreeB >> mainWithFreeB参考
>#WIP
↓書く途中に書いてたメモ
間違っている
というか、意味をなしていない気がするが、
なんか一応残している
なんというか、
join と Join のアナロジーをしようとして上手くいかなかったdo式内の操作と同様7日を見る
上の理解が本当なのかどうかを確認してみる
Free f はMonadをdataとして表現したものであるということは、以下の2つは同じような挙動を示すはずである
Free 型をネストして組み上げたデータ構造 do 式の中ででactionを組み合わせて作った関数まず
Free と Maybe のネストしたデータ構造を定義してみるpurs(hs)mainWithFree :: ∀ a. Free Maybe (Free Maybe (Maybe a))
mainWithFree = Join $ Just (Join $ Just (Pure (Join $ Just (Pure Nothing))))これは以下の2つに分解して見たほうがわかりやすい
purs(hs)mainWithFree :: ∀ a. Free Maybe (Free Maybe (Maybe a))
mainWithFree = Join $ Just (Join $ Just (Pure subWithFree))
subWithFree :: ∀ a. Free Maybe (Maybe a)
subWithFree = Join $ Just (Pure Nothing)mainの中で、subを呼んでいる感じ
ちょっとちゃうな下に合わせて上を修正章
これを普通の
Maybe を使った関数で書くとこうなるpurs(hs)main :: ∀ a. Maybe (Maybe (Maybe a))
main = do
a1 <- Just 1
a2 <- Just 1
pure do
b1 <- Just 2
pure Nothing同様に、分けて書くならこう
purs(hs)main :: ∀ a. Maybe (Maybe (Maybe a))
main = do
a1 <- Just 1
a2 <- Just 1
pure sub
sub :: ∀ a. Maybe (Maybe a)
sub = do
b1 <- Just 2
pure Nothing型の対応が取れていることが見て取れる
purs(hs)mainWithFree :: ∀ a. Free Maybe (Free Maybe (Maybe a))
main :: forall a. Maybe (Maybe (Maybe a))そして、Monadの性質により、
join に適用することでこのネストをflatに出来るpurs(hs)joinedWithFree :: ∀ a. Free Maybe (Maybe a)
joinedWithFree = join mainWithFree
joined :: ∀ a. Maybe (Maybe a)
joined = join mainこれも型の対応が取れている