Free型はMonadをdata構造として表現したもの

正確に言うと「fがFunctorの場合のFree fはMonadをdataとして表現したもの」

最後の方でGADTsを使いたいのでhsで書くmrsekut.icon

このページ内では、FreeはFreeモナドとして扱う

Free型の定義

code:hs

data Free f a = Pure a

| Join (f (Free f a))

Freeモナドの直感的な理解

Monadとなる条件とFreeの定義を見比べる

monadとなるためには以下の3つがあれば十分

code:hs

fmap :: (a -> b) -> m a -> m b

pure :: a -> m a

join :: m (m a) -> m a

一方でFree型をGADTで書くと

code:hs

Pure :: a -> Free f a

Join :: f (Free f a) -> Free f a

pureとjoinに対応があることがわかる

こうやって見ると、joinのm (m a)の、外側のmはFunctorで十分である、ということもわかるmrsekut.icon

だからあとはmapさえあればMonadにすることが出来る

そこで「Functorのinstanceである型」と組み合わせることで、Monadを作ることが出来る

Freeで構成したデータ型と、実際のMonadが、同じ見た目、同じ挙動になることを確認する

まず普通にPreludeに入っているMaybeで適当な実装を書いてみる

code:hs

maybeMain :: Maybe Integer

maybeMain = do

a1 <- Just 1

a2 <- Just 1

pure $ a1 + a2

ここで独自にMaybe'を用意し、Functorのinstanceにしておく

code:hs

data 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」で以下のように書ける

code:hs

mainWithFree :: Free Maybe' Integer

mainWithFree = do

a1 <- Join $ Just' $ Pure 1

a2 <- Join $ Just' $ Pure 1

Pure $ a1 + a2

型こそ異なれど、ほぼ同じ見た目をしている

便利関数を用意しておけばほぼ同じ見た目になる

code:hs

mainWithFree' :: 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を使って書くと

code:hs

mainWithFree'' :: Free Maybe' Integer

mainWithFree'' = Join $ Just' $ Pure 1 >>= (\x -> Join $ Just' $ Pure 1 >>= \y -> Pure $ x + y)

これを、Monad (Free f)の定義を「左辺→右辺」に簡約していくと以下のような経過を辿る

code:hs

mainWithFree'' = 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なので、連結も出来る

code:hs

f :: Free Maybe' Integer

f = mainWithFree >> mainWithFree' >> mainWithFree''

Monadとなる条件にはmap,pure,joinの他に、bind,pureというのもあった

これを使うと別の仕方でFreeを定義できることができる

code: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を書き直すと

code:hs

mainWithFreeB :: Free Maybe' Integer

mainWithFreeB = (Just' 1) Bind (\a1 -> (Just' 1) Bind (\a2 -> Pure $ a1 + a2))

joinがないので、「do式を消したあるある見た目」っぽくなっているmrsekut.icon

上の例と同様にmainWithFreeBはMonadなので連結も出来る

code:hs

f :: Free Maybe' Integer

f = mainWithFreeB >> mainWithFreeB

参考

free monadとはmonadそのものである - うさぎ小屋

#WIP

↓書く途中に書いてたメモmrsekut.icon

間違っている

というか、意味をなしていない気がするが、

なんか一応残している

なんというか、joinとJoinのアナロジーをしようとして上手くいかなかった

do式内の操作と同様7日を見る

上の理解が本当なのかどうかを確認してみる

Free fはMonadをdataとして表現したものである

ということは、以下の2つは同じような挙動を示すはずである

Free型をネストして組み上げたデータ構造

do式の中ででactionを組み合わせて作った関数

まずFreeとMaybeのネストしたデータ構造を定義してみる

code:purs(hs)

mainWithFree :: ∀ a. Free Maybe (Free Maybe (Maybe a))

mainWithFree = Join $ Just (Join $ Just (Pure (Join $ Just (Pure Nothing))))

これは以下の2つに分解して見たほうがわかりやすい

code: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を呼んでいる感じ

ちょっとちゃうなmrsekut.icon下に合わせて上を修正章mrsekut.iconmrsekut.icon*3

これを普通のMaybeを使った関数で書くとこうなる

code:purs(hs)

main :: ∀ a. Maybe (Maybe (Maybe a))

main = do

a1 <- Just 1

a2 <- Just 1

pure do

b1 <- Just 2

pure Nothing

同様に、分けて書くならこう

code: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

型の対応が取れていることが見て取れる

code:purs(hs)

mainWithFree :: ∀ a. Free Maybe (Free Maybe (Maybe a))

main :: forall a. Maybe (Maybe (Maybe a))

そして、Monadの性質により、joinに適用することでこのネストをflatに出来る

code:purs(hs)

joinedWithFree :: ∀ a. Free Maybe (Maybe a)

joinedWithFree = join mainWithFree

joined :: ∀ a. Maybe (Maybe a)

joined = join main

これも型の対応が取れている