Free Monad

• Free は再帰的なデータ構造, Pure が終端
  • ex. List型 data List a = Nil | Cons a (List a)

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

data Teletype a = PutStrLn String a | GetLine (String -> a)
 
derive instance teletypeFunctor :: Functor TeleType
 
t :: Free Teletype Unit
t = Free (GetLine
    (\line -> (Free (PutStrLn
        line (Pure unit)
    )))
)
-- Free がモナドであれば以下のように書ける
t = do
  line <- getLine
  putStrLn line

flowchart BT
Apply-->Functor
Bind-->Apply
Applicative-->Apply
Monad-->Bind
Monad-->Applicative

instance functorFree :: (Functor f) => Functor (Free f) where
  map :: forall a b. (a -> b) -> (Free f a) -> (Free f b)
  map fn (Free f) = Free (map fn <$> f) 
  map fn (Pure a) = Pure (fn a)
 
instance applicativeFree :: (Functor f) => Applicative (Free f) where
  pure = Pure
 
instance bindFree :: (Functor f) => Bind (Free f) where
  bind :: forall a b. Free f a -> (a -> Free f b) -> Free f b
  bind (Free f) fn = Free $ (\a -> bind a fn) <$> f
  bind (Pure a) fn = fn a

参考文献

• つくってわかるFreeモナド 〜 Freeモナド、その仕組み 〜