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` 函數的返回值.