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)


## 型のイメージ

つまりFree f afffffffaと読み替えられる

たとえば

• Free [] a ~ [[[[[a]]]]]
• Free Maybe a ~ Maybe (Maybe (Maybe a))

## 値と型

Free [Free [Free [Pure ()]]] :: Free [] ()
Free [Pure 3, Pure 2, Free [Pure 1, Free []], Pure 0] :: Num a => Free [] a
Free [] :: Free [] a
Pure () :: Free f ()
Free [Pure $Free [Pure ()]] :: Free [] (Free [] ())  よく分からない ## 手を動かす: join >>=bindと呼ばれるMonad m => m a -> (a -> m b) -> m b Control.Monad.joinことMonad m => m (m a) -> m aで定義できる12ので 理解のためjoinを定義してみる join' :: Functor f => Free f (Free f a) -> Free f a join' (Pure a) = a join' (Free fFreefa) = Free (fmap join' fFreefa)  ### 実際に: Maybe >>> let x = Free$Just (Free$Just (Pure (Free$Just (Pure Nothing))))
>>> :t x
x :: Free Maybe (Free Maybe (Maybe a))
>>> join x
Free (Just (Free (Just (Free (Just (Pure Nothing))))))


join          (Free$Just (Free$Just (Pure (Free$Just (Pure Nothing))))) Free (fmap join$ Just (Free$Just (Pure (Free$Just (Pure Nothing)))))
Free (Just $join (Free$Just (Pure (Free$Just (Pure Nothing))))) Free$Just          (join (Free$Just (Pure (Free$Just (Pure Nothing)))))
Free$Just (Free$Just (join (Pure (Free$Just (Pure Nothing))))) Free$Just          (Free$Just (Free$Just (Pure Nothing)))
Free$Just (Free$Just       (Free$Just (Pure Nothing)))  1. 初期状態 2. joinの展開 3. fmapの展開: fmap f (Just a) = Just (f a) 4. 見やすくしただけ: joinFree$Justが入れ替わったのが分かる
5. 同様にする
6. Purejoinと対消滅する
7. 見やすくしただけ: 外側のPureを道連れにjoinが消え、外側と内側のFreeの境目を潰しているのが分かる

### もう少し複雑な例: List

>>> let x = Free[ Free[ Free[], Pure( Free[] ) ], Pure( Free[ Pure() ] ) ]
>>> :t x
x :: Free [] (Free [] ())
>>> join x
Free [Free [Free [],Free []],Free [Pure ()]]

join$Free[ Free[ Free[], Pure( Free[] ) ], Pure( Free[ Pure() ] ) ] Free[ join$Free[      Free[],      Pure( Free[] ) ], join$Pure( Free[ Pure() ] ) ] Free[ Free[ join$Free[], join$Pure( Free[] ) ], Free[ Pure() ] ] Free[ Free[ Free[], Free[] ], Free[ Pure() ] ]  ### 解釈 joinの型がFree f (Free f a) -> Free f aで、Free f afffffffaなどと読み替えられることから、 joinとはffff(ffffa) -> ffffffffa的ななにかである それともつじつまの合う結果である なんとなく雰囲気はつかめた ### bindへ そして bind :: (Functor m, Monad m) => m a -> (a -> m b) -> m b bind x f = join$ fmap f x


である3

>>> Free[ Pure 7, Pure 2 ] >>= (\ x -> Free[ Pure (show x), Pure (show (x ^ x)) ])
Free [Free [Pure "7",Pure "823543"],Free [Pure "2",Pure "4"]]


## 自由

Freefreeとはおそらくfree monoidやfree magmaのfreeであろう4
つまり、公理の等式以外に元の間の関係式をもたない、という意味
この場合公理とはモナド則

つまりGADTsで定義して見やすくすると

class Functor m => Monad m where
unit :: a -> m a
join :: m (m a) -> m a
data FreeMonad f a where
Unit :: a -> FreeMonad f a
Join :: f (FreeMonad f a) -> FreeMonad f a


とある程度綺麗に対応している

## 結論

Freeとはmonadそのものであり、monadをdataとして表現したものである
lispに似ているなと感じる

## 予防線と残った疑問

free monadには別の定義も存在して

-- join / f無し
data FreeMonad a where
Unit :: a -> FreeMonad a
Join :: FreeMonad (FreeMonad a) -> FreeMonad a

-- bind / f無し
data FreeMonad a where
Return :: a -> FreeMonad a
Bind :: FreeMonad x -> (x -> FreeMonad a) -> FreeMonad a

-- bind / f有り(BindのFreeMonad消去)
data FreeMonad f a where
Return :: a -> FreeMonad f a
Bind :: f x -> (x -> FreeMonad f a) -> FreeMonad f a


と思いつく範囲だけで3つ
しかもこの3つはf Functor制約なしでmonadになる

-- bind / f無し
instance Monad FreeMonad where
return = Return
(>>=) = Bind

-- bind / f有り(BindのFreeMonad消去)
instance Monad (FreeMonad f) where
return = Return
(>>=) (Return a) a2fb = a2fb a
(>>=) (Bind fx x2fa) a2fb = Bind fx ((>>= a2fb) . x2fa)


-- join / f有り(JoinのFreeMonad消去)
instance Functor f => Functor (FreeMonad f) where
fmap a2b (Unit a) = Unit $a2b a fmap a2b (Join ffa) = Join$ fmap (fmap a2b) ffa
join' :: Functor f => FreeMonad f (FreeMonad f a) -> FreeMonad f a
join' (Unit a) = a
join' (Join ffa) = Join $fmap join' ffa instance Functor f => Monad (FreeMonad f) where return = Unit (>>=) fa a2fb = join'$ fmap a2fb fa


と要Functor制約
Joinf (FreeMonad f a)を展開するのにどうしても必要なようだ5

そしてそもそもfが入るとはどういうことなのかいまいち分からない
もしかしたらFreeはfree monadでなく類似の別な概念のfreeかもしれない

### operational

さらに強いと聞くoperational monadはこのbind型のfree monadなのではと考えた

type Program t = Free (Coyoneda t)


らしく、

data Coyoneda t x where
Coyoneda :: t r -> (r -> a) -> Coyoneda t a
instance Functor (Coyoneda t) where
fmap f (Coyoneda t g) = Coyoneda t (f . g)


とcoyonedaは制約なしでfunctorを作るので、ただのdataからmonadになるのだそうだ

coyonedaのmoduleもData.Functor.Coyonedaにあるので、free functor的ななにかだと思い、
free functorとfree monadを合成してもfree monadだろうという発想から少し頑張った
しかし型パズルが解けずinterpretが定義できないので、全く違うのかもしれないし、haskell力足りていないだけかもしれない

## packages

### operational

1. むしろmonadの定義としてはjoinの方が自然に見える

2. functorの制約はhaskellのmonadの定義が悪い

3. あまり圏論に明るくないので少し怪しい

4. haskellのmonadがbindである理由かもしれない

5. 圏論に精通していれば分かるのかどうかも分からない