動機

興趣

free monad

data Free f a where
  Pure   :: a -> Free f a
  Impure :: f (Free f a) -> Free f a

eta :: Functor f => f a -> Free f a
eta = Impure . fmap Pure

這裡的f要是functor，所以free有兩種case

  • 從一般數值生的Pure
  • 把functor拔掉的Impure

另外有一個eta從functor生free

兩個動作

  1. 打包
  2. 把functor轉成free

free只剩下拆DS的功能，真的有做事的都回到fmap去

接著就能利用fmap，把applicative與monad做出來

instance Functor f => Functor (Free f) where
  fmap f (Pure x)   = Pure $ f x
  fmap f (Impure m) = Impure $ fmap (fmap f) m

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure f <*> m   = fmap f m
  Impure f <*> m = Impure $ fmap (<*> m) f

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a   >>= k = k a
  Impure m >>= k = Impure (fmap (>>= k) m)

freer monad

fmap的type是(a -> b) -> f a -> f b

如果有一個type直接把(a -> b)與f a先存好，是不是就直接是functor，同時利用free monad，就可以生出applicative與monad

所以有了Lan(freer monad)

data Lan g a where
  Lan :: g x -> (x -> a) -> Lan g a

instance Functor (Lan g) where
  fmap f (Lan gx h) = Lan gx (f . h)

lan :: g a -> Lan g a
lan ga = Lan ga id # return!!

吃 1. 被打包的值 2. 與轉type的函數 生freer(Lan) 這根本就是fmap

把free monad生出來

data FFree g a where
  FPure   :: a -> FFree g a
  FImpure :: g x -> (x -> FFree g a) -> FFree g a

etaF :: g a -> FFree g a
etaF fa = FImpure fa FPure

剩下的部分

instance Functor (FFree g) where
  fmap f (FPure x)     = FPure (f x)
  fmap f (FImpure u q) = FImpure u (fmap f . q)

instance Applicative (FFree g) where
  pure = FPure
  FPure f     <*> x = fmap f x
  FImpure u q <*> x = FImpure u ((<*> x) . q)

instance Monad (FFree g) where
  return = FPure
  FPure x      >>= k = k x
  FImpure u k' >>= k = FImpure u (k' >>> k)

看lan的fmap的實作會發現，根本只有函數合成而已!!

這裡可以注意Impure與FImpure Impure的目的是把被打包的值轉成Free 但FImpure本來就是吃被打包的值，那這裡怎麼模擬Impure? 把被打包的值的type換掉就好!!

Ref

Free and Freer Monads: Putting Monads Back into Closet