モナド変換子(その１: 基本）

## はじめに
haskellを習得する上で必修ともいえるライブラリがあります。
今回はその1つ、モナド変換子ライブラリ`mtl`を4回に分けて紹介したいと思います。

## なぜモナドをスタックする必要があるのか

例えば環境変数`Env`をIOの中で利用したいとするでしょう。すると環境変数を利用する全ての関数は`Env`を引数にとらなければなりません。

```haskell
someFun :: Env -> IO ()
...

someHandling :: Env -> Int -> IO Int
...
```

**あきらかに面倒です。**
またあるデータを変更する際にエラー処理もしたいと思ったので`Either`モナドを使ったとしましょう。

```haskell
-- Somedataを処理する関数
someFun :: SomeData -> Either String SomeData
....

-- SomeDataからIntを算出する関数
someEither :: SomeData -> Either String Int
```
モナドの基本として、あるモナドを利用する際に他のモナドに途中で変更することはできません。
ここで`State`モナドが使えたらなー。でも既に`Either`モナド使ってるし、、トホホ

これがHaskellの限界なのでしょうか。
**そんなわけありません。**

## モナドスタックの自作を試みる
他の記事では`fmap`を駆使して強引にモナドを組み合わせるという力技に近いことをしている人もみかけました。
しかしもっとエレガントにする方法があります。モナドのインスタンスを自ら定義するのです。例えば`Either`と`State`を組み合わせて`ErrorState`モナドなるものを作りたいとしましょう。

```haskell
newtype ErrorState a = ErrorState { runErrorState :: s -> Either String (a, s) }
```

すると必要となるのはモナドのインスタンスです。

```haskell
instance Monad (ErrorState e) where
  return a   = ErrorState $ \s -> Right (a, s)

  m >>= cont = ErrorState $ \s -> case runErrorState m s of
      (Left e)        -> Left e
      (Right (a, s')) -> runErrorState (cont a) s'
```

次にアプリカティブ、とファンクターのインスタンスも必要です。これは`liftM`と`ap`を利用することによって定義できます。

```haskell
instance Functor (ErrorState e) where
  fmap = liftM

instance Applicative (ErrorState e) where
  pure = return
  (<*>) = ap
```

次に`State`モナドを利用する上で必須となる関数`get`, `put`, `modify`を定義します。

```haskell
get :: ErrorState s s
get = ErrorState $ \s -> Right (s, s)

put :: s -> ErrorState s ()
put = ErrorState $ \_ -> Right ((), s)

modify :: (s -> s) -> ErrorState s ()
modify f = get >>= \s -> put (f s)
```

ついでに`Either`モナドではおなじみの`throwError`も定義しましょう。

```haskell
throwError :: String -> ErrorState s a
throwError str = ErrorState $ \_ -> Left e
```
いい感じです。
それでは、実際にこのモナドをつかってみましょう。

```haskell
addEven :: Int -> ErrorState Int ()
addEven num = if odd num
    then throwError $ "Invalid number: " ++ show num
    else modify (+ num)
```
これは与えられた整数が偶数であれば状態を変更し、奇数であればエラー処理を行う関数です。
実際に試してみましょう。

```terminal
λ: runErrorState (addEven 10) 10
Right ((),20)
λ: runErrorState (addEven 11) 10
Left "Invalid number: 11"
```
与えた状態10に対して`addEven 10`の場合には`10`を足して20に、`addEven 11`の場合にはエラー文が出力されています。
つまり`ErrorState`モナドは`State`モナドと`Either`モナド両方の性質を組み合わせたモナドとなったのです。
**素晴らしい**

## 面倒やろこれ、、
そうですよね。上記の実装では以下の問題があります。

### モナドの作成がボイラープレート化する
まずこのモナドを自作するのに慣れが必要となります。また、慣れたとしてもひたすら同じことを繰り返すことになるでしょう。コピペでできるようなことを何度もするのはかっこよくありません。

### 拡張性に乏しい
2つのモナドを組み合わせたものならまだ問題ありませんが、４つ５つと積み上げていくとモナドインスタンスの実装は指数関数的に難しくなります。また、別のモナドに`lift`する方法も考慮しなければなりません。

### 保守性が低い
また保守性の観点からも上記の実装はよくありません。
例えば`State`モナドから`Reader`モナドに変えようという提案があったとしましょう。するとモナドのインスタンスを再度定義しなおさなけばなりません。また`Reader`モナドなら`ask`,`asks`,`local`関数もほしいところです。
となると**既存のコードもほぼ全て書き換えなければなりません**。

**苦行です**(実際やらされました)

## モナド変換子
これらの問題を解決するのがモナド変換子ライブラリ[mtl](https://hackage.haskell.org/package/mtl)です。mtlでは基本的なモナド（`Maybe`, `Eitehr`, `Reader`, `State`, 等）のモナド変換子を提供しています。

今回は簡単な数式インタプリタから次第に機能を追加してゆき、その上でモナド変換子がいかに有用なのかを紹介したいと思います。

## 実装
まずは基本的なところから始めます。インタプリタは数字、足し算を評価できるようにします。

数式は以下のように表現します。

```haskell
data Expr =
    Lit Int
  | Add Expr Expr
```

次に式を評価する`eval`関数を実装しましょう。これも特に問題ありません。

```haskell
eval :: Expr -> Int
eval (Lit n)     = n
eval (Add e1 e2) = eval e1 + eval e2
```
実際に動かしてみましょう

```terminal
λ: eval (Add (Add (Lit 3) (Lit 4)) (Lit 10))
17
```

いい感じです。
次に割り算を実装しましょう。

```haskell
data Expr =
    Lit Int
  | Add Expr Expr
  | Div Expr Expr
```

`Div`を評価するためには、評価関数も変更する必要があります。

```haskell
eval :: Expr -> Int
eval (Lit n)     = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Div e1 e2) = eval e1 `div` eval e2
```
しかし、ここで0で割る数式を評価しようとするとランタイムエラーとなります。

```terminal
λ:eval (Div (Lit 10) (Lit 0))
*** Exception: divide by zero
```

ここでは`Either`モナドを使ってエラー処理を行いましょう。

```haskell
eval :: Expr -> Either String Int
eval (Lit n)     = pure n
eval (Add e1 e2) = (+) <$> eval e1 <*> eval e2
eval (Div e1 e2) = do
  v1 <- eval e1
  v2 <- eval e2
  if v2 == 0
    then Left "division by 0"
    else return (v1 `div` v2)
```

なんと全てのコードを書き換える結果となってしまいました。
ここで「やっぱり割り算は使わない」と言われたらリライトとなります。辛い。

そもそも全てを書き換える必要になった原因は評価関数がいきなりモナドを使うようになったためです。

この解決策の１つとして**最初からモナドを使う**という考え方があります。
例えば以下のように実装していたとしましょう。

```haskell
eval :: Expr -> ??? Int
eval :: (Lit n)     = pure n
eval :: (Add e1 e2) = (+) <$> eval e1 <*> eval e2
```
これなら割り算を実装したとしても既存の実装に影響を与えません。でもこの`???`ってどんなモナドなのでしょうか。
これってなにもしないモナドですよね。つまり、`Identity`モナドです。

```haskell
eval :: Expr -> Identity Int
eval (Lit n)     = pure n
eval (Add e1 e2) = (+) <$> eval e1 <*> eval e2
```
評価された関数は`Identity`モナドにくるまれています。中身を取り出すには`runIdentity`関数を実行する必要があります。

```terminal
λ: runIdentity $ eval (Add (Lit 10) (Lit 7))
17
```
うーん、なるほど。まぁ良しとしましょう。

次に`Div`の実装ですが、ここで問題が発生します。評価関数は既に`Identity`モナドを使っています。でも`Div`を評価するには`Either`モナドが必要です。うーん困った。

## ExceptT
ここモナド変換子の１つである`ExceptT`が利用できます。`ExceptT`は既存のモナドに`Either`モナドをスタックできるモナドです。

```haskell
eval :: Expr -> ExceptT String Identity Int
eval (Lit n)     = pure n
eval (Add e1 e2) = (+) <$> eval e1 <*> eval e2
eval (Div e1 e2) = do
  v1 <- eval e1
  v2 <- eval e2
  if v2 == 0
    then throwError "division by 0"
    else return (v1 `div` v2)
```

希望通り、既存のコードを一切書き換えずに`Div`を評価できるようになりました。

しかし、これによって評価された式は`ExceptT`そして`Identity`にくるまれてしまいました。
よって中身を取り出すには`runExceptT`、 `runIdentity`の順に関数を適用する必要があります。

```haskell
run :: Expr -> Either String Int
run expr = runIdentity (runExceptT (eval expr))
```

一応できますね。でもなにか**嫌な予感がします**。

## ReaderT
次に予め変数を**どこかに**格納しておき、必要になればその変数を利用できるような機能を追加しましょう。

```haskell
data Expr =
    Lit Int
  | Add Expr Expr
  | Div Expr Expr
  | Var String
```
つまり`Var`が評価されると**どこか**に変数名を問い合わせ、それに対応した値を返してもらいたいわけです。
まず変数とその値が1対1で対応しているテーブルが必要となります。これは`Map`で表現できます。

```haskell
type Env = Map String Int
```

次に「問い合わせる」ということをいかに実装するかです。これには`Reader`モナドがうってつけでしょう。もちろん`mtl`には`Reader`モナドの変換子である`ReaderT`モナドがあります。

次に評価関数の型シグネチャを書き換えなければなりませんね。

```haskell
eval :: Expr -> ReaderT Env (ExceptT String Identity) Int
```
**長い**


今回モナド変換子を利用しているのが`eval`関数のみですが、現実では同じモナドスタックを共有している関数がいくつもあるのが当たり前でしょう。その関数１つずつにこのようなシグネチャを記述するのは*冗長的*ですし、保守性の観点からもよろしくありません。

このスタックを**抽象化**できないでしょうか。

### スタックの抽象化
#### 型シノニムなのか、newtypeなのか

ここでモナドスタックを抽象化する方法は２つあります。型シノニムもしくは`newtype`です。

```haskell
type Eval = ReaderT Env (ExceptT String Identity) Int
-- or
newtype Eval a = Eval (ReaderT Env (ExceptT String Identity) a)
```

実は、ここでは`newtype`が正解です。これはモナドスタックうんぬんよりも、型シノニムと`newtype`をどう使い分ければいいかという話になります。型シノニムは単に任意の型のエイリアスであるため、利用するユーザーにあらゆる利用方法を（もちろん意図しないものも）許してしまいます。

例えばあるライブラリを開発した際に`Message`型を定義したとしましょう。

```haskell
type Message = String

newtype Message = Message String
```
そして`Message`型には付随する関数があり、開発者はそれ以外の関数を利用できないようにしたいとします。

```haskell
someFun :: Message -> Maybe Char
```

型シノニムで定義した場合、ライブラリ利用者にこの制限を強要することはできません。`Message`型は単に`String`のエイリアスなので、リストに関するあらゆる関数を`Message`型に適用することができます。

```haskell
-- Why?
evilFun :: Message -> Char
evilFun = head
```
このように型シノニムを使用すると、全く意図しない操作を許してしまいます。`newtype`であればこれを防ぐことができます。

また`newtype`の場合、より抽象的なモナドスタックを構築することができます。これによってエラーメッセージがよりわかりやすくなるだけではなく、型クラスのインスタンスの実装、変更も自由に行えるため、より汎用性の高いモナドスタックが実現できます。

```haskell
newtype Message = Message String

-- Stringとは全く別の型クラスインスタンスが実装可能
instance Show Message where
   show msg = "New typeclass instance for show" <> show msg
```


#### newtypeの問題点
しかし`newtype`の場合、問題となるのは型クラスの導出です。

```haskell
newtype Eval a = Eval (ExceptT String Identity) a
    deriving (???)
```
型クラスが導出できなければ、それぞれのモナドが提供する型クラスの関数を利用することができません。これを解決するのが言語拡張`GeneralizedNewtypeDeriving`です。

言語拡張`GeneralizedNewtypeDeriving`は`newtype`で作った型の型クラスのインスタンス導出を簡略化するための拡張です。

```haskell
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype Quantity = Quantity Int
  deriving (Eq, Ord, Num, Show)

a = Quantity 2
b = Quantity 6

totalQuantity :: Quantity
totalQuantity = a + b
-- Quantity 8
```

ここでは言語拡張を利用することによって`Num`の型クラスを容易に導出し、それによって`Quantity`同士の四則演算が可能となりました。

実は`mtl`が提供しているモナド変換子`ExceptT`や`ReaderT`はそれぞれの型クラスインスタンスを実装したものなのです。例えば`ReaderT`は型クラス`MonadReader`のインスタンスを実装しています。

```haskell
class (Monad m) => MonadReader r m | m -> r where
  ask   :: m r
  local :: (r -> r) -> m a -> m a

instance (Monad m) => MonadReader r (ReaderT r m) where
  ask       = ReaderT return
  local f m = ReaderT $ \r -> runReaderT m (f r)
```
もちろんこれらの型クラスを以下のように導出することも可能です。[^1]

```haskell
newtype App a = App (ReaderT [Int] (Either String) a)
  deriving (Functor
          , Applicative
          , Monad
          , MonadReader [Int])
```

またモナドスタックを利用する際に問題となるのが`lift`地獄です。[^2] これはスタックを利用する際にどこで、何度`lift`するのかを明示的に記述する必要があるということです。これは保守性の観点からすれば**非常にまずい**です。

これに関しても`GeneralizedNewtypeDeriving`、そして`mtl`が提供する型クラス及びそのインスタンスを利用すれば、`lift`を明示的に記述する必要がなくなります。[^3] 

##再度実装に取り組む
それではモナドスタックの抽象化を行いましょう。

```haskell
newtype Eval a = Eval (ReaderT Env (ExceptT String Identity) a)
  deriving (Functor
          , Applicative
          , Monad
          , MonadReader Env
          , MonadError String)
```

これで評価関数の型シグネチャもすっきりします。

```haskell
eval :: Expr -> Eval Int
```
また`newtype`を定義したので、それを引数にとり、与えられた式を走査する関数も必要となります。

```haskell
runEval :: Eval a -> Env -> Either String a
runEval (Eval m) env = runIdentity (runExceptT (runReaderT m env))
```

つぎに`Var`を評価できるようにしましょう

```haskell
eval (Var x) = do
  env <- ask
  case M.lookup x env of
    Nothing -> throwError $ "Variable not found: " <> show x
    Just num -> pure num
```

いい感じです。さっそく試してみましょう。

```haskell
λ: runEval (eval (Add (Var "x") (Lit 10))) (singleton "x" 10)
Right 20
```

**素晴らしい！**
**既存のコードに一切手を加えずに**`Var`を評価できるようになりました。

## StateT
また機能を追加しましょう。今回は評価の連結(Sequence)そして変数の宣言及び代入(Assign)です。

```haskell
data Expr =
    Lit Int
  | Add Expr Expr
  | Div Expr Expr
  | Var String
  | Seq Expr Expr
  | Assign String Expr
```
`Var`を実装した際にはあらかじめ環境を提供できたので`Reader`モナドでも問題ありませんでしたが、変数の宣言、代入となると`State`モナドがうってつけです。ということは`ReaderT`を`StateT`に取り替えなけれなりません。

まずはモナドスタックである`Eval`を変更します。

```haskell
-- Before (ReaderT)
newtype Eval a = Eval (ReaderT Env (ExceptT String Identity) a)
  deriving (Functor, Applicative, Monad, MonadReader Env, MonadError String)

-- After (StateT)
newtype Eval a = Eval (StateT Env (ExceptT String Identity) a)
  deriving (Functor, Applicative, Monad, MonadState Env, MonadError String)
```

次に走査関数も変更が必要です。

```haskell
-- Before (ReaderT)
runEval :: Eval a -> Env -> Either String a
runEval (Eval m) env = runIdentity (runExceptT (runReaderT m env))

-- After (StateT)
runEval :: Eval a -> Env -> Either String a
runEval (Eval m) env = runIdentity (runExceptT (evalStateT m env))
```

あとは`Var`を評価する際に`Reader`モナドの`ask`関数を使っていたので、それをStateモナドの`get`に取り替えましょう。

```haskell
eval (Var x) = do
  env <- get -- ask
  case M.lookup x env of
    Nothing -> throwError $ "Variable not found: " <> show x
    Just num -> pure num
```
大したことありませんでした。あまりにも変更箇所が少なすぎて、その違いを見分けるのに苦労したかもしれません。
既存のコードに関する変更は**これで完了**です。他の部分を変更する必要は**一切ありません**。

これで新たな機能を追加することができます。

まず`Seq`からです。これは最初のものを評価した後に次のものを評価するだけなので簡単です。

```haskell
eval (Seq e1 e2) = e1 >> e2
```

次は`Assign`です。これもとくに問題ありません。

```haskell
eval (Assign x e) = do
  v <- eval e
  modify (M.insert x v)
  return v
```

最後にこれを試すためにプログラムを用意してみました。

```haskell
program :: Expr
program = Assign "x" (Lit 10)
          `Seq` Assign "x" (Div (Var "x") (Lit 2))
          `Seq` Add (Var "x") (Lit 1)
```
これをJavascriptで大まかに翻訳すると以下のようになります

```javascript
let x = 10;
x = x / 2;
console.log (x + 1);
```

では実際にやってみましょう

```terminal
λ: runEval (eval program) empty
Right 6
```
完璧です。

##リファクタリング
ここでこの記事を追って評価関数を実装してきた人はコードがかなり煩雑としてきたことに気づくでしょう。ここでコードのリファクタリングを行います。

```haskell
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Interpreter where

import Control.Monad.Identity
import Control.Monad.Except
import Control.Monad.State

import Data.Map
import qualified Data.Map as M

import Data.Monoid ((<>))

type Env = Map String Int

data Expr =
    Lit Int
  | Add Expr Expr
  | Div Expr Expr
  | Var String
  | Assign String Expr
  | Seq Expr Expr

newtype Eval a = Eval (StateT Env (ExceptT String Identity) a)
  deriving (Functor, Applicative, Monad, MonadState Env, MonadError String)

eval :: Expr -> Eval Int
eval (Lit n)     = pure n
eval (Add e1 e2) = (+) <$> eval e1 <*> eval e2
eval (Div e1 e2) = doDiv e1 e2
eval (Var x) = varLookup x
eval (Seq e1 e2)  = eval e1 >> eval e2
eval (Assign x e) = varSet x e

doDiv :: Expr -> Expr -> Eval Int
doDiv e1 e2 = do
  v1 <- eval e1
  v2 <- eval e2
  if v2 == 0
    then divByZeroError
    else return (v1 `div` v2)

divByZeroError :: Eval a
divByZeroError = throwError "Division by 0"

varLookup :: String -> Eval Int
varLookup x = do
  env <- get
  case M.lookup x env of
    Nothing -> unknownVar x
    Just num -> return num

varSet :: String -> Expr -> Eval Int
varSet x e = do
  v <- eval e
  modify (M.insert x v)
  return v

unknownVar :: String -> Eval a
unknownVar x = throwError $ "Variable not found: " <> show x

runEval :: Eval a -> Env -> Either String a
runEval (Eval m) env = runIdentity (runExceptT (evalStateT m env))

program :: Expr
program = Assign "x" (Lit 10)
          `Seq` Assign "x" (Div (Var "x") (Lit 2))
          `Seq` Add (Var "x") (Lit 1)
```
ここで注目してほしいがそれぞれの関数の型シグネチャです。
まずモナドスタックを抽象化したことによって簡潔かつ可読性の高いものになりました。

またコード自体は非常にシンプルですがこれでもモナド変換子`StateT`,`ExceptT`をスタックさせたので、エラー処理かつ状態の参照および変更が可能という非常に強力なインタプリタが実装できました。

### 練習問題
標準入力を受け取り、それが数字であれば評価し、それ以外であればエラーを出力する`Get`を実装してください。(ヒント：`IO`が必要となります。)

```terminal
λ: runEval (eval (Add (Lit 10) (Get)) empty
Please enter a number
10
Right 20
```

##　まとめ
以上でモナド変換子ライブラリ`mtl`の基本的な使い方を紹介させて頂きました。
`mtl`を使用する主な利点としては以下の点が挙げられます:

- モナド変換子はモナド同士を組み合わせることでそれぞれの作用を組み合わせることができる。
- 基本的なモナド [^4] に関しては、自身でモナドスタックを定義する必要がなくなる
- モナドスタックが容易に構築可能
- 既存のコードにほとんど手を加えずにスタックを変更することができる。これによって保守性の高いコードが実現される

次回は実際に`mtl`に触れてもらうために、UTXOを利用したトランザクション処理の実装を課題として投稿します。

**追記：** [課題を公開しました](https://qiita.com/HirotoShioi/items/ac75b97aa52f9db9c472)

[^1]: モナドスタックも結局はモナドなので型クラス`Functor`, `Applicative`, `Monad`も導出可能です。
[^2]: liftに関しては[Haskell モナド変換子 超入門](https://qiita.com/7shi/items/4408b76624067c17e933#%E3%83%A2%E3%83%8A%E3%83%89%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF)という大変わかりやすい記事があるので、それを参照してください。
[^3]: これに関しては[Typeclassopedia](https://wiki.haskell.org/Typeclassopedia#Transformer_type_classes_and_.22capability.22_style)を参照してください。
[^4]: 自身で作ったモナドをモナドスタックとして扱えるようにする方法もあるようですが、それに関しては現在勉強中です。