Haskell/Monad transformers

Monad transformers (解答)

Monads

理解 Monad
高级 Monad
Monad 进阶
 MonadPlus
Monadic parser combinators
Monad transformers
Monad 实务

我们已经学习了Monad能够如何简便对于 IO, Maybe, 列表, 和 State 的处理. 每一个Monad都是如此的有用且用途广泛, 我们自然会寻求将几个Monad的特性组合起来的方法. 比如, 也许我们可以定义一个既能处理I/O操作, 又能使用 Maybe 提供的异常处理的函数. 虽然这可以用形如 IO (Maybe a) 的函数实现, 但是在这种方式下我们将被迫在 IO 的 do 代码块中手工模式匹配提取值, 而避免写出这种繁琐而无谓的代码却恰恰是 Maybe Monad存在的原因.

于是我们发明了 monad transformers: 它们能够将几种Monad的特性融合起来, 同时不失去使用Monad的灵活性.

密码验证

我们先来看一看这个几乎每一个IT从业人员都会遇到的实际问题: 让用户设置足够强的密码. 一种方案是: 强迫用户输入大于一定长度, 且满足各种恼人要求的密码 (例如包含大写字母, 数字, 字符, 等等).

这是一个用于从用户处获取密码的Haskell函数:

getPassphrase :: IO (Maybe String)
getPassphrase = do s <- getLine
                   if isValid s then return $ Just s
                                else return Nothing

-- 我们可以要求密码满足任何我们想要的条件
isValid :: String -> Bool
isValid s = length s >= 8
            && any isAlpha s
            && any isNumber s
            && any isPunctuation s

首先, getPassphrase 是一个 IO Monad, 因为它需要从用户处获得输入. 我们还使用了 Maybe, 因为若密码没有通过 isValid 的建议, 我们决定返回 Nothing. 需要注意的是, 我们在这里并没有使用到 Maybe 作为Monad的特性: do 代码块的类型是 IO monad, 我们只是恰巧 return 了一个 Maybe 类型的值罢了.

Monad transformers 不仅仅使 getPassphrase 的实现变简单了, 而且还能够简化几乎所有运用了多个monad的代码. 这是不使用Monad transformers的程序:

askPassphrase :: IO ()
askPassphrase = do putStrLn "输入新密码:"
                   maybe_value <- getPassphrase
                   if isJust maybe_value
                     then do putStrLn "储存中..." -- 假装存在数据库操作
                     else putStrLn "密码无效"

这段代码单独使用了一行来获得 maybe_value, 然后又手工对它进行验证.

如果使用 monad transformers, 我们将可以把获得输入和验证这两个步骤合二为一 — 我们将不再需要模式匹配或者等价的 isJust. 在我们的简单例子中, 或许 monad transformers 只作出了微小的改进, 但是当问题规模进一步扩大时, 它们将发挥巨大的作用.

一个简单的 monad transformer: `MaybeT`

为了简化 getPassphrase 以及所有使用到它的函数, 我们定义一个赋予 IO monad 一些 Maybe monad 特性的 monad transformer; 我们将其命名为 MaybeT. 一般来说, monad transformers 的名字都会以 "T" 结尾, 而之前的部分 (例如, 在本例中是"Maybe") 表示它所提供的特性.

MaybeT 是一个包装 (wrap) 了 m (Maybe a) 的类型, 其中 m 可以是任何Monad (在本例中即为 IO):

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

这里的 datatype 声明定义了 MaybeT, 一个被 m 参数化的类型构造子 (type constructor), 以及一个值构造函数 (value constructor), 同样被命名为 MaybeT, 以及一个作用为简便的内部值访问的函数 runMaybeT.

Monad transformers 的关键在于 他们本身也是monads; 因此我们需要写出 MaybeT m 的 Monad 类型类实例:

instance Monad m => Monad (MaybeT m) where
    return  = MaybeT . return . Just

首先, 我们先用 Just 将值装入最内层的 Maybe 中, 然后用 return 将前述 Maybe 装入 m monad里, 最后再用 MaybeT 将整个值包装起来.

我们也可以这样实现 (虽然是不是增加了可读性仍然有待商榷) return = MaybeT . return . return.

如同在所有monad中一样, (>>=) 也是 transformer 的核心.

-- 特化为 MaybeT m 的 (>>=) 函数类型签名 
(>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b

x >>= f = MaybeT $ do maybe_value <- runMaybeT x
                      case maybe_value of
                           Nothing    -> return Nothing
                           Just value -> runMaybeT $ f value

我们从 do 代码块的第一行开始解释:

首先, runMaybeT 从 x 中取出 m (Maybe a). 我们由此可知整个 do 代码块的类型为 monad m.
第一行稍后, <- 从上述值中取出了 Maybe a.
case 语句对 maybe_value 进行检测:
- 若其为 Nothing, 我们将 Nothing 返回至 m 当中;
- 若其为 Just, 我们将函数 f 应用到其中的 value 上. 因为 f 的返回值类型为 MaybeT m b, 我们需要再次使用 runMaybeT 来将其返回值提取回 m monad 中.
最后, do 代码块的类型为 m (Maybe b); 因此我们用 MaybeT 值构造函数将它包装进 MaybeT 中.

这咋看来获取有些复杂; 但是若剔除大量的包装和解包装, 我们的代码和 Maybe monad 的实现其实很像:

-- Maybe monad 的 (>>=)
maybe_value >>= f = case maybe_value of
                        Nothing -> Nothing
                        Just value -> f value

我们在 do 代码块中仍然能够使用 runMaybeT, 为何要在前者上应用 MaybeT 值构造函数呢? 这是因为我们的 do 代码块必须是 m monad, 而不是 MaybeT m monad, 因为后者此时还没有定义 (>>=). (回想一下 do 语法糖是如何工作的)

注解

在 return 的实现中层层相叠的函数也许可以为我们提供一个(或许)有助于理解的比喻: 将复合的 monad 想象为一个 三明治; 虽然这个比喻似乎在暗示实际上有三个 monad 在起作用, 但是实际上只有两个: 内层的以及"融合了的" monad. 置于基层的 monad (本例中即Maybe) 中并没有用到 (>>=) 或者 return, 它只是作为 transformer 实现的一部分罢了. 如果你觉得这个比喻很有道理, 将 transformer 和底层 monad 想象成三明治的两片包裹着内层 monad 的面包. ^[1]

理论上, 这就是我们所需的全部了; 但是, 为 MaybeT 实现几个其他类型类的 instance 又何妨呢?

instance Monad m => MonadPlus (MaybeT m) where
    mzero     = MaybeT $ return Nothing
    mplus x y = MaybeT $ do maybe_value <- runMaybeT x
                            case maybe_value of
                                 Nothing    -> runMaybeT y
                                 Just _     -> return maybe_value

instance MonadTrans MaybeT where
    lift = MaybeT . (liftM Just)

MonadTrans monad 实现了 lift 函数, 由此我们可以在 MaybeT m monad 的 do 代码块中使用m monad 的值. 至于 MonadPlus, 因为 Maybe 有着这个类型类的 instance, MaybeT 也应该有着对应的 instance.

应用在密码验证的例子中

现在, 前例的密码管理可以被改写为:

getValidPassphrase :: MaybeT IO String
getValidPassphrase = do s <- lift getLine
                        guard (isValid s) -- MonadPlus 类型类使我们能够使用 guard.
                        return s

askPassphrase :: MaybeT IO ()
askPassphrase = do lift $ putStrLn "输入新密码:"
                   value <- getValidPassphrase
                   lift $ putStrLn "储存中..."

这段代码简洁多了, 特别是 askPassphrase 函数. 最重要的是, 有着 (>>=) 为我们代劳, 我们不再需要手动检查结果是 Nothing 和 Just 中的哪一个了.

我们使用了 lift 函数以在 MaybeT IO monad 中使用 getLine 和 putStrLn; 因为 MaybeT IO 有着 MonadPlus 类型类的 instance, guard 可以为我们检查代码的合法性. 在密码不合法时其将返回 mzero (即 IO Nothing).

碰巧, 有了 MonadPlus, 我们可以优雅地不停要求用户输入一个合法的密码:

askPassword :: MaybeT IO ()
askPassword = do lift $ putStrLn "输入新密码:"
                 value <- msum $ repeat getValidPassphrase
                 lift $ putStrLn "储存中..."

泛滥的 transformer

transformers 包提供了许多包含常见 monad 的 transformer 版本的模块 (例如 Template:Haskell lib 模块提供了 MaybeT). 它们和对应的非 transformer 版本 monad 是兼容的; 换句话说, 除去一些和另一个 monad 交互所用到的包装和解包装 , 它们的实现基本上是一致的. 从今往后, 我们称 transformer monad 所基于的非 transformer 版本的 monad 为 基层 monad (例如 MaybeT 中的 Maybe); 以及称应用在 transformer 上的 monad 为 内层 monad (例如 MaybeT IO 中的 IO).

我们随便举一个例子, ReaderT Env IO String. 这是一个能够从某个外部环境读取 Env 类型的值 (并且和 Reader, 也就是基 monad, 使用方法相同) 并且能够进行一些I/O, 最后返回一个 String 类型的值的 monad. 由于这个 transformer 的 (>>=) 和 return 语义和基 monad 相同, 一个 ReaderT Env IO String 类型的 do 语句块从外部看来和另一个 Reader 类型的 do 语句块并无二致, 除了我们需要用 lift 来使用 IO monad.

类型戏法

我们已经了解到, MaybeT 的类型构造子实际上是一个对内层 monad 中的 Maybe 值的包装. 因此, 用于取出内部值的函数 runMaybeT 返回给我们一个类型为 m (Maybe a) 的值 - 也就是一个由内层 monad 包装着的基 monad 值. 类似的, 对于分别基于列表和 Either 构建的 ListT 和 ExceptT transformer:

runListT :: ListT m a -> m [a]

and

runExceptT :: ExceptT e m a -> m (Either e a)

然而并不是所有的 transformer 都和它们的基 monad 有着类似的关系. 不同于上面两例所给出的基 monad, Writer, Reader, State, 以及 Cont monad 既没有多个值构造子, 也没有接收多个参数的值构造函数. 因此, 它们提供了形如 run... 的函数以作为解包装函数, 而它们的 transformer 则提供形如 run...T 的函数. 下表给出了这些 monad 的 run... 和 run...T 函数的类型, 而这些类型事实上就是包装在基 monad 和对应的 transformer 中的那些. ^[2]

基 Monad	Transformer	原始类型 (被基 monad 包装的类型)	复合类型 (被 transformer 包装的类型)
Writer	WriterT	`(a, w)`	`m (a, w)`
Reader	ReaderT	`r -> a`	`r -> m a`
State	StateT	`s -> (a, s)`	`s -> m (a, s)`
Cont	ContT	`(a -> r) -> r`	`(a -> m r) -> m r`

我们可以注意到, 基 monad 并没有出现在复合的类型中. 这些 monad 并没有一个像 Maybe 或列表那样的有意义的构造函数, 因此我们选择不在 transformer monad 中保留基 monad. 值得注意的是, 在后三个例子中我们包装的值是函数. 拿 StateT 作例子, 将原有的表示状态转换的 s -> (a, s) 函数变为 s -> m (a, s) 的形式; 然而我们只将函数的返回值 (而不是整个函数) 包装进内层 monad 中. ReaderT 也与此差不多. ContT 却与它们不同: 由于 Cont (表示延续的 monad) 的性质, 被包装的函数和作这个函数参数的函数返回值必须相同, 因此 transformer 将两个值都包装入内层 monad 中. 遗憾的是, 并没有一种能将普通的 monad 转换成 transformer 版本的万灵药; 每一种 transformer 的实现都和基 monad 的行为有关.

Lifting

我们将仔细研究 lift 函数: 它是应用 monad transformers 的关键. 首先, 我们需要对它的名字 "lift" 做一些澄清. 在理解_Monad中, 我们已经学习过一个名字类似的函数 liftM. 我们了解到, 它实际上是 monad 版本的 fmap:

liftM :: Monad m => (a -> b) -> m a -> m b

liftM 将一个类型为 (a -> b) 的函数应用到一个 m monad 内的值上. 我们也可以将它视为只有一个参数:

liftM :: Monad m => (a -> b) -> (m a -> m b)

liftM 将一个普通的函数转换为在 m monad 上运作的函数. 我们用"提升(lifting)"表示将一样东西带至另一样东西中 — 在前例中, 我们将一个函数提升到了 m monad 中.

有了 liftM, 我们不需要用 do 代码块或类似的技巧就能够把寻常的函数应用在 monad 上了:

do notation	liftM
do x <- monadicValue return (f x)	liftM f monadicValue

类似的, lift 函数在 transformer 上起到了一个相似的作用. 它将内层 monad 中的计算带至复合的 monad (即 transformer monad) 中. 这使得我们能够轻易地在复合 monad 中插入一个内层 monad 的运算.

lift 是 MonadTrans 类型类的唯一一个函数, 参见 Template:Haskell lib. 所有的 transformer 都有 MonadTrans 的 instance, 因此我们能够在任何一个 transformer 上使用 lift.

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

lift 存在一个 IO 的变种, 名叫 liftIO; 这是 MonadIO 类型类的唯一一个函数, 参见 Template:Haskell lib.

class (Monad m) => MonadIO m where
   liftIO :: IO a -> m a

当多个 transformer 被组合在一起时, liftIO 能够带来一些便利. 在这种情况下, IO 永远是最内层的 monad (因为不存在 IOT transformer), 因此一般来说我们需要多次使用 lift 以将 IO 中的值从底层提升至复合 monad 中. 定义了 liftIO instance 的类型被设计成能够使用 liftIO 将 IO 从任意深的内层一次性提升到 transformer monad 中.

实现 `lift`

lift 并不是很复杂. 以 MaybeT transformer 为例:

instance MonadTrans MaybeT where
    lift m = MaybeT (liftM Just m)

我们从接收到一个内层 monad 中的值的参数开始. 我们使用 liftM (或者 fmap, 因为所有Monad都首先是Functor) 和 Just 值构造函数来将基 monad 插入内层 monad 中, 以从 m a 转化为 m (Maybe a)). 最后, 我们使用 MaybeT 值构造函数将三明治包裹起来. 值得注意的是, 此例中 liftM 工作于内层 monad 中, 如同我们之前看到的 MaybeT 的 (>>=) 实现中的 do 代码块一样.

练习

为什么 lift 必须为每一个 monad transformer 单独定义, 但 liftM 却可以只实现一次呢?
Identity 是一个定义于 Data.Functor.Identity 中实际意义不大的 functor:
```
newtype Identity a = Identity { runIdentity :: a }
```
它有着如下的 Monad instance:
```
instance Monad Identity where
    return a = Identity a
    m >>= k  = k (runIdentity m)
```
实现一个 monad transformer IdentityT, 这个 transformer 和 Identity 类似, 但是将值包裹在 m a 而不是 a 类型的值中. 请你至少写出它的 Monad 和 MonadTrans instances.

实现 transformers

State transformer

作为一个额外的例子, 我们将试着实现 StateT. 请确认自己了解 State 再继续. ^[3]

正如同 State monad 有着 newtype State s a = State { runState :: (s -> (a,s)) } 的定义一样, StateT transformer 的定义为:

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

StateT s m 有着如下的 Monad instance, 旁边用基 monad 作为对比:

State

StateT

newtype State s a =
  State { runState :: (s -> (a,s)) }

instance Monad (State s) where
  return a        = State $ \s -> (a,s)
  (State x) >>= f = State $ \s ->
    let (v,s') = x s
    in runState (f v) s'

newtype StateT s m a =
  StateT { runStateT :: (s -> m (a,s)) }

instance (Monad m) => Monad (StateT s m) where
  return a         = StateT $ \s -> return (a,s)
  (StateT x) >>= f = StateT $ \s -> do
    (v,s') <- x s          -- 取得新的值和状态
    runStateT (f v) s'     -- 将它们传递给 f

我们的 return 实现使用了内层 monad 的 return 函数. (>>=) 则使用一个 do 代码块来在内层 monad 中进行计算.

注解

现在我们能够解释, 为什么在 State monad 中存在手工定义的 state 却没有与类型一同定义的 State 值构造函数了. 在 transformers 和 mtl 包中, State s 被定义为 StateT s Identity 的类型别名, 其中 Identity 是在本章练习中出现的没有特别效果的 monad. 这个定义和我们迄今为止所见的使用 newtype 的定义是等价的.

为了将 StateT s m monad 同 State monad 一般使用, 我们自然需要核心的 get 和 put 函数. 这里我们将使用 mtl 的代码风格. mtl 不仅仅提供了 monad transformers 的定义, 还提供了定义了常见 monad 的关键操作的类型类. 例如, Template:Haskell lib 包所提供的 MonadState 类型类, 定义了 get 和 put 函数:

instance (Monad m) => MonadState s (StateT s m) where
  get   = StateT $ \s -> return (s,s)
  put s = StateT $ \_ -> return ((),s)

注解

instance (Monad m) => MonadState s (StateT s m) 的意思是: "对于任何类型 s 以及任何是 Monad instance 的类型 m, s 和 StateT s m 共同组成了一个 MonadState 的 instance". s 和 m 分别对应了 state monad 和内层 monad. 类型参数 s 是 instance 声明的一个独立部分, 因此函数能够访问到 s: 举个例子, put 的类型为 s -> StateT s m ().

存在为其他 transformer 包装着的 state monad 所定义的 MonadState instance, 例如 MonadState s m => MonadState s (MaybeT m). 这些 instance 使得我们不再需要写出 lift 来使用 get and put, 因为复合 monad 的 MonadState instance 为我们代劳了.

我们还可以为复合 monad 实现内层 monad 所拥有的一些类型类 instance. 例如, 所有包装了 StateT (其拥有 MonadPlus instance) 的复合 monad 也同样能够拥有 MonadPlus 的 instance:

instance (MonadPlus m) => MonadPlus (StateT s m) where
  mzero = StateT $ \_ -> mzero
  (StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

mzero 和 mplus 的实现符合我们的直觉; 它们将实际的操作下推给内层 monad 来完成.

最后, monad transformer 必须有 MonadTrans 的 instance, 不然我们无法使用 lift:

instance MonadTrans (StateT s) where
  lift c = StateT $ \s -> c >>= (\x -> return (x,s))

lift 函数返回一个包装在 StateT 中的函数, 其接受一个表示状态的值 s 作为参数, 返回一个函数, 这个函数接受一个内层 monad 中的值, 并将它通过 (>>=) 传递给一个将其和状态打包成一个在内层 monad 中的二元组的函数. 举个例子, 当我们在 StateT transformer 中使用列表时, 一个返回列表的函数 (即一个在列表 monad 中的计算) 在被提升为 StateT s []后, 将变成一个返回 StateT (s -> [(a,s)]) 的函数. 换句话说, 这个函数用初始状态产生了多个 (值, 新状态) 的二元组. 我们将 StateT 中的计算 "fork" 了, 为被提升的函数返回的列表中的每一个值创建了一个计算分支. 当然了, 将 StateT 和不同的 monad 组合将产生不同效果的 lift 函数.

练习
使用 `get` 和 `put` 来实现 `state :: MonadState s m => (s -> (a, s)) -> m a`. `MaybeT (State s)` 和 `StateT s Maybe` 等价吗? (提示: 比较两个 `run...T` 函数的返回值.