HOME | EDIT | RSS | ABOUT | GITHUB

范畴论完全装逼手册 / Grokking Monad

第三部分:搞基猫呢Advanced Monads

第二部分介绍了一些实用的monad instances,这些 monad 都通过同样的抽象方式,解决了分离计算与副作用的工作。

通过它们可以解决大多数的基本问题,但是正对于复杂业务逻辑,我们可能还需要一些更高阶的 monad 或者 pattern。

当有了第一部分的理论基础和第二部分的实践,这部分要介绍的猫呢其实并不是很搞基。通过这一部分介绍的搞基猫呢, 我们还可以像 IO monad 一样,通过 free 或者 Eff 自定义自己的计算,和可能带副作用的解释器。

RWS

RWS 是缩写 Reader Writer State monad, 所以明显是三个monad的合体。如果已经忘记 Reader Writer 或者 State,请到第二部分复习一下。

一旦把三个 monad 合体,意味着可以在同一个 monad 使用三个 monad 的方法,比如,可以同时使用 Reader 的 ask, State 的 get, put, 和 Writer 的 tell

readWriteState = do
  e <- ask
  a <- get
  let res = a + e
  put res
  tell [res]
  return res
runRWS readWriteState 1 2
-- (3 3 [3])

注意到跟 Reader 和 State 一样,run的时候输入初始值

其中 1 为 Reader 的值,2 为 State 的初始状态.

Monad Transform

你会发现 RWS 一起用挺好的,能读能写能打 log,但是已经固定好搭配了,只能是 RWS ,如果我还想加入其它的 Monad,该怎么办呢?

这时候,简单的解决方案是加个 T,比如对于 Reader,我们有 ReaderT,RWS,也有对应的 RWST。其中 T 代表 Transform。

ReaderT

让我来通过简单的 ReaderT 来解释到底什么是 T 吧, 首先跟 Reader 一样我们有个 runReaderT

newtype ReaderT e m a = ReaderT { runReaderT :: e -> m a }

比较一下 Reader 的定义

newtype Reader e a = Reader { runReader :: (e -> a) }

有没有发现多了一个 m, 也就是说, runReader e 会返回 a, 但是 runReaderT e 则会返回 m a

p3-ReaderT.png
instance (Monad m) => Monad (ReaderT e m) where
    return   = lift . return
    r >>= k  = ReaderT $ \ e -> do
        a <- runReaderT r e
        runReaderT (k a) e

再看看 monad 的实现, 也是一样的, 先 run 一下 r e 得到结果 a, 应用函数 ka, 再 run 一把.

问题是, 这里的 return 里面的 lift 是哪来的?

instance MonadTrans (ReaderT e) where
  lift m = ReaderT (const m)
p3-MonadTrans-ReaderT-e-m.png

这个函数 lift 被定义在 MonadTrans 的实例中, 简单的把 m 放到 ReaderT 结果中.

例如, lift (Just 1) 会得到 ReaderT, 其中 e 随意, m 为 Maybe Num

重点需要体会的是, Reader 可以越过 Maybe 直接操作到 Num, 完了再包回来.

有了 ReaderT, 搭配 Id Monad 就很容易创建出来 Reader Monad

type Reader r a= ReaderT r Identity a

越过 Id read 到 Id 内部, 完了再用 Id 包回来, 不就是 Reader 了么

ReaderT { runReaderT :: r -> Identity a }
-- Identity a is a
ReaderT { runReaderT :: r -> a }

Alternative

这个 typeclass 提供 <|> 函数, 表示要么计算左边, 要么计算右边

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a
p3-Alternative.png

其实就是 Applicative 的

比如:

Just 1 <|> Just 2 -- Just 1
Just 1 <|> Nothing -- Just 1
Nothing <|> Just 1 -- Just 1
Nothing <|> Nothing -- Nothing

MonadPlus

这跟 Alternative 是一毛一样的, 只是限制的更细, 必须是 Monad才行

class (Alternative m, Monad m) => MonadPlus m where
   mzero :: m a
   mzero = empty
   mplus :: m a -> m a -> m a
   mplus = (<|>)

看, 实现中直接就调用了 Alternative 的 empty<|>

ST Monad

ST Monad 跟 State Monad 的功能有些像, 不过更厉害的是, 他不是 immutable 的, 而是 "immutable" 的在原地做修改. 改完之后 runST 又然他回到了 immutable 的 Haskell 世界.

sumST :: Num a => [a] -> a
sumST xs = runST $ do           -- do 后面的事情会是不错的内存操作, runST 可以把它拉会纯的世界
    n <- newSTRef 0             -- 在内存中创建一块并指到 STRef
    forM_ xs $ \x -> do         -- 这跟命令式的for循环改写变量是一毛一样的
        modifySTRef n (+x)
    readSTRef n                 -- 返回改完之后的 n 的值

Free Monad

上一章说过的 RWS Monad 毕竟是固定搭配,当你的业务需要更多的 Monad 来表示 Effect 时, 我们就需要有那么个小猪手帮我们定义自己的 Monad。

那就是 Free, Free 可以将任意 datatype lift 成为 Monad

Free

先看 Free 什么定义:

data Free f a = Roll (f (Free f a)) | Return a

其中 f 就是你业务需要的 effect 类型, a 是这个 effect 所产生的返回值类型。

右边两种构造函数,如果把 Role 改成 Cons, Return 改成 Nil 的话, 是不是跟 List 其实是 同构isomophic 的呢? 所以如果想象成 List, 那么 f 在这里就相当于 List 中的一个元素.

到那时, >>= 的操作又跟 List 略有不同, 我们都知道 >>= 会把每一个元素 map 成 List, 然后 flatten, 但 Free 其实是用来构建 顺序的 effect 的, 所以:

instance Functor f => Monad (Free f) where
  return a        = Return a
  Return a >>= fn = fn a
  Roll ffa >>= fn = Roll $ fmap (>>= fn) ffa

你会发现 >>= 会递归的 fmapRoll 上, 直到最后一个 Return.

如果你有一个

data Eff a = Eff1 a | Eff2 a | Eff3 a
program = Roll Eff1 (Roll Eff2 (Return Int))

>>= 一个函数 Int => Free Eff3 Intprogram 会是什么?

Roll Eff1 (Roll Eff2 (Roll Eff3 (Return Int))

真的这么神奇吗?

细心的你可能早都发现了 Eff 这货必须是个 Functor 才行. 那我们如何随便定义一个 data Eff 直接能生成 Functor Eff 的实例呢?

Coyoneda

希望你还依然记得第一部分的米田 引理

data CoYoneda f a = forall b. CoYoneda (b -> a) (f b)
p3-CoYoneda.png

事实上很简单可以把任何 f 变成 CoYoneda f

phi :: f a -> CoYoneda f a
phi fa = CoYoneda id fa
p3-CoYoneda-phi.png

诀窍就是 id, 也就是你把 b 变成 a, 再把 fa 放到 CoYoneda 里就好了

fFunctor 时, 又可以把 CoYoneda 变成 f

psi :: Functor f => CoYoneda f a -> f a
psi (CoYoneda g fa) = fmap g fa
p3-CoYoneda-psi.png

反过来的这个不重要, 重要的是 phi, 因为如果你可以把任何 f 变成 CoYoneda f, 而 CoYoneda f 又是 Functor, 我们不就免费得到一个 Functor?

instance Functor (Coyoneda f) where
  fmap f (Coyoneda g fb) = Coyoneda (f . g) fb

Free Functor

比如我们的 Eff 就可以直接通过 phi 变成 CoYoneda Eff, 从而得到免费的 Functor

data Eff a = Eff1 a | Eff2 a | Eff3 a
program = Roll (phi (Eff1 (Roll (phi (Eff2 (Return Int))))))
p3-Free.png

Interpreter

构造完一个 free program 后,我们得到的是一个嵌套的数据结构, 当我们需要 run 这个 program 时, 我们需要 foldMap 一个 Interpreter 去一层层拨开 这个 free program.

foldMap :: Monad m => (forall x . f x -> m x) -> Free f a -> m a
foldMap _ (Return a)  = return a
foldMap f (Roll a) = f a >>= foldMap f

TODO Eff