モナドを理解するために JavaScript で例外モナドを実装してみた

モナドを理解するために [Monads for functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
) の例題にある例外モナドを JavaScript で実装してみたのでメモっとく。

戻るボタンをクリックする前に無心で写経してみてほしい。Web ブラウザーの JavaScript コンソールで試せるようにしてあるので！

ちなみに、モナドを理解するために書いたコードなので JavaScript でモナドを実用する上では役に立たないのでご注意を。

# 前提知識

コードを簡潔に表現するために下記のような言語仕様を活用する。

## アロー関数

アロー関数を活用して関数を簡潔に表現する。

```js
var add = (n, m) => n + m;               // var add = function(n, m) {
                                         //     return n + m;
                                         // };
                                         //  
var mul = n => m => n * m;               // var mul = function(n) {
                                         //     return function(m) {
                                         //         return n * m;
                                         //     };
                                         // };
add(1, 2); // -> 3
mul(3)(4); // -> 12
```

## 自動セミコロン挿入

自動セミコロン挿入を活用してコードを簡潔に表現する。つまりセミコロンを書かないことにする。

```js
var add = (a, b) => a + b                // var add = (a, b) => a + b;
                                         //
var mul = function(n) {                  // var mul = function(n) {
    return function(m) {                 //     return function(m) {
        return n * m                     //         return n * m;
    }                                    //     }
}                                        // }

add(1, 2) // -> 3
mul(3)(4) // -> 12
```

# ユーティリティ関数

コードを簡潔に表現するために関数をいくつか定義しておく。

## 整数除算関数

整数除算する関数。小数は切り捨てられる。

```js
var div = (n, m) => n / m | 0

div(10, 3) // -> 3
```

## パターンマッチ関数

パターンマッチングに使用する関数。

```js
var match = (expression, pattern) => expression(pattern)
```

使用方法を見てもらったほうが理解しやすいかな。

```js
var Add = (n, m) => _ => _.Add(n, m)
var Mul = (n, m) => _ => _.Mul(n, m)

var calculate = expression => match(expression, {
    Add: (a, b) => a + b,
    Mul: (a, b) => a * b
})

calculate(Add(1, 2)) // -> 3
calculate(Mul(3, 4)) // -> 12
```

ちょっと謎めいていると思うけど `Add` と `Mul` と `calculate` の組み合わせで計算できてることだけわかれば大丈夫。実装の詳細は追いかけなくていい。

# 例外モナド

ここからが本題。例外モナドに到達できるように整数除算評価器の例題を改善していってみよう。

## 例題：正整数除算評価器

シンプルな正整数の除算をする評価器について考えてみる。定数 (Constant) と除算 (Division) の2種類の項 (Term) で構成される表現を評価する評価器だ。

(1972 ÷ 2) ÷ 23 は `Div(Div(Con(1972), Con(2)), Con(23))` というように表現する。

評価器である `evaluate` 関数をこの表現を引数にして呼び出すと `42` という評価結果が得られる。

```js
evaluate(Div(Div(Con(1972), Con(2)), Con(23))) // -> 42
```

この整数除算評価器を実装すると下記のようになる。なお、[ユーティリティ関数](#ユーティリティ関数)にある `div` 関数と `match` 関数も事前に定義してから実行することを忘れずに。

```js
var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    Con: a => a,
    Div: (t, u) => div(evaluate(t), evaluate(u))
})

evaluate(Div(Div(Con(1972), Con(2)), Con(23))) // -> 42
```

コードについて説明していこう。

```js
var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)
```

`Con` は構築子 (Constructor) 。`Con(1)` や `Con(1972)` という表現で値が構築できる。なお `Con(1)` は `_ => _.Con(1)` という関数に簡約される。

`Div` も構築子。`Div(Con(6), Con(3))` という表現で値が構築できる。

```js
var evaluate = term => match(term, {
    Con: a => a,
    Div: (t, u) => div(evaluate(t), evaluate(u))
})
```

`evaluate` 関数は引数に渡された項を評価する。パターンマッチによって項ごとに評価を変更している。`Con: a => a` は定数の項にマッチし、定数の項の値を返す。`Div: (t, u) => div(evaluate(t), evaluate(u))` は除算の項にマッチし、被演算子を再帰的に `evaluate` 関数で評価して、その結果を除算した値を返す。

構築子とパターンマッチングの中身までは考えなくていいので動いたら先に進んでみよう。

## ゼロ除算

さて、この評価器には問題がありゼロ除算すると `0` になってしまう。

```js
evaluate(Div(Con(1), Con(0))) // -> 0
```

これは正しい動作ではないので、ゼロ除算の場合はエラーになるように修正していこう。

## 非純粋関数プログラミング

ゼロ除算が発生したときにエラーになるよう実装しよう。非純粋関数プログラミングでは一般的に例外を使用して実装される。

正常値は戻り値として返す。

```js
evaluate(Div(Div(Con(1972), Con(2)), Con(23))) // -> 42
```

例外値は例外として返す。

```js
evaluate(Div(Con(1), Con(0))) // -> Exception: "divide by zero"
```

これを非純粋関数プログラミングで実装すると下記のようになる。除数が `0` だったら例外を投げるようなコードに修正しただけだ。

```js
var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    Con: a => a,
    Div: (t, u) => {
        var a = evaluate(t)
        var b = evaluate(u)
        if (b === 0) throw "divide by zero"
        else         return div(a, b)
    }
})

evaluate(Div(Div(Con(1972), Con(2)), Con(23))) // -> 42
evaluate(Div(Con(1), Con(0))) // -> Exception: "divide by zero"
```

これで、ゼロ除算が発生したときにエラーになった。ただ、例外によって `evaluate` 関数は純粋関数ではなくなった。つまり、`evaluate` 関数は副作用がある関数になってしまったのだ。

普段のコーディングであれば、例外という副作用を利用して解決しても全然構わない。でも今回は副作用がない関数、純粋関数でこれを実現してみたい。

## 純粋関数プログラミング

ゼロ除算が発生したときもきちんと値を返すように実装する。構築子を定義して正常値と例外値を返すことで純粋な世界に連れ戻そう。

正常値は `Return` 構築子で構築して返す。

```js
show(evaluate(Div(Div(Con(1972), Con(2)), Con(23)))) // -> Return(42)
```

例外値は `Raise` 構築子で構築して返す。

```js
show(evaluate(Div(Con(1), Con(0)))) // -> Raise("divide by zero")
```

これを純粋関数プログラミングで実装すると下記のようになる。

```js
var Raise = e => _ => _.Raise(e)
var Return = a => _ => _.Return(a)

var show = m => match(m, {
    Raise: e => "Raise(\"" + e + "\")",
    Return: a => "Return(" + a + ")"
})

var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    Con: a => Return(a),
    Div: (t, u) => match(evaluate(t), {
        Raise: e => Raise(e),
        Return: a => match(evaluate(u), {
            Raise: e => Raise(e),
            Return: b =>
                (b === 0) ? Raise("divide by zero")
                          : Return(div(a, b))
        })
    })
})

show(evaluate(Div(Div(Con(1972), Con(2)), Con(23)))) // -> Return(42)
show(evaluate(Div(Con(1), Con(0)))) // -> Raise("divide by zero")
```

コードについて説明していこう。

```js
var Raise = e => _ => _.Raise(e)
var Return = a => _ => _.Return(a)
```

`Raise` は構築子。`Raise("divide by zero")` という表現で例外値が構築できる。`Return` も構築子。`Return(42)` という表現で正常値が構築できる。

```js
var show = m => match(m, {
    Raise: e => "Raise(\"" + e + "\")",
    Return: a => "Return(" + a + ")"
})
```

`show` 関数は引数に渡された値を表示する。パターンマッチによって値ごとに表示を変更している。`Raise: e` は例外値にマッチし、例外値を表示する。`Return: a` は正常値にマッチし、正常値を表示する。

JavaScript インタプリターでは構築子によって構築された値を表示できないので `show` 関数を定義しているのだ。

```js
var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    ...
})
```

`Con` 構築子・`Div` 構築子・`evaluate` 関数の外側はこれまでの例題と同じ。

```js
    Con: a => Return(a),
```

`evaluate` 関数の内側の `Con: a` は定数の項にマッチし、定数の項の値を正常値として返す。

```js
   Div: (t, u) => match(evaluate(t), {
        Raise: e => Raise(e),
        Return: a => match(evaluate(u), {
            Raise: e => Raise(e),
            Return: b =>
                (b === 0) ? Raise("divide by zero")
                          : Return(div(a, b))
        })
    })
```

`Div: (t, u)` は除算の項にマッチする。被演算子をそれぞれ `evaluate` 関数で評価し、例外値でないかをチェックして、その結果を除算した値を返す。

これで `evaluate` 関数を純粋関数にすることに成功した。しかし、被演算子を評価した結果をチェックするネストした処理は複雑で、副作用を持つ一般的な例外と比較して、「自然に実装できている」とは言い難いよね。

それを解決するために例外モナドが登場するのだ！

## 純粋関数プログラミング＋例外モナド

モナドを使用しない例と同様にゼロ除算が発生したときもきちんと値を返すように実装する。構築子を定義して正常値と例外値を返すことで純粋な世界に連れ戻すのも同様だ。

正常値は `Return` 構築子で構築して返す。

```js
show(evaluate(Div(Div(Con(1972), Con(2)), Con(23)))) // -> Return(42)
```

例外値は `Raise` 構築子で構築して返す。

```js
show(evaluate(Div(Con(1), Con(0)))) // -> Raise("divide by zero")
```

`evaluate` 関数を使用する側から見るとまったく変化がない。変化があるのはその実装になる。

さて、これを例外モナドによる純粋関数プログラミングで実装すると下記のようになる。

```js
var Raise = e => _ => _.Raise(e)
var Return = a => _ => _.Return(a)

var show = m => match(m, {
    Raise: e => "Raise(\"" + e + "\")",
    Return: a => "Return(" + a + ")"
})

var raise = e => Raise(e)

var unit = a => Return(a)
var bind = (m, k) => match(m, {
    Raise: e => Raise(e),
    Return: a => k(a)
})

var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    Con: a => unit(a),
    Div: (t, u) =>
        bind(evaluate(t), a =>
            bind(evaluate(u), b =>
                (b === 0) ? raise("divide by zero")
                          : unit(div(a, b))))
})

show(evaluate(Div(Div(Con(1972), Con(2)), Con(23)))) // -> Return(42)
show(evaluate(Div(Con(1), Con(0)))) // -> Raise("divide by zero")
```

コードについて説明していこう。

```js
var Raise = e => _ => _.Raise(e)
var Return = a => _ => _.Return(a)

var show = m => match(m, {
    Raise: e => "Raise(\"" + e + "\")",
    Return: a => "Return(" + a + ")"
})
```

ここまでは例外モナドを使用しない例とまったく同じ。

```js
var raise = e => Raise(e)
```

`raise` 関数は `Raise` 構築子を呼び出して例外値を返す関数だ。

```js
var unit = a => Return(a)
var bind = (m, k) => match(m, {
    Raise: e => Raise(e),
    Return: a => k(a)
})
```

ここが例外モナドの勘所。

モナドは構築子・`unit` 関数・`bind` 関数の三つ組らしい。ということで、例外モナドは前述の `Raise` 構築子・`Return` 構築子・ `unit` 関数・ `bind` 関数で構成されることになる。

`unit` 関数は `Return` 構築子を呼び出して正常値を返す関数。

`bind` 関数は `m` を評価し、例外値と正常値でパターンマッチし、例外値か正常値のいずれかを返す関数。例外値の値は `Raise` 構築子を呼び出し、ふたたび例外値にして返す。正常値の値は `k` 関数を呼び出して例外値か正常値のいずれかを返す。

よくわからなかったとしても前に進んでみよう。そして戻ってこよう。

```js
var Con = a => _ => _.Con(a)
var Div = (t, u) => _ => _.Div(t, u)

var evaluate = term => match(term, {
    ...
})
```

`Con` 構築子・`Div` 構築子・`evaluate` 関数の外側は例外モナドを使用しない例とまったく同じ。

```js
    Con: a => unit(a),
```

`evaluate` 関数の内側の `Con: a` は定数の項にマッチし、定数の項の値で `unit` 関数を呼び出して正常値を返す。

```js
    Div: (t, u) =>
        bind(evaluate(t), a =>
            bind(evaluate(u), b =>
                (b === 0) ? raise("divide by zero")
                          : unit(div(a, b))))
```

`Div: (t, u)` は除算の項にマッチする。被演算子をそれぞれ `evaluate` 関数で評価して、`bind` 関数の第1引数としている。ここで `bind` 関数の実装を見ると、例外値だったら例外値を返し、正常値だったら第2引数に渡された関数、`k` 関数を実行していることがわかる。そして最後に除数項 `u` の評価結果である除数 `b` がゼロでないかをチェックして、ゼロであれば例外値を、ゼロでなければ正常値を返す。

動作はわかってもらえただろうか？ただ、モナドを使用しない例からの改善には見えないかもしれない。そのことは次の節で説明しよう。

## 純粋関数プログラミングと非純粋関数プログラミングの比較

純粋関数プログラミングと非純粋関数プログラミングの例をインデント・改行を調整した上で横並びにしてみる。

```js
var Con = a => _ => _.Con(a)             // var Con = a => _ => _.Con(a) 
var Div = (t, u) => _ => _.Div(t, u)     // var Div = (t, u) => _ => _.Div(t, u)
                                         //
var evaluate = term => match(term, {     // var evaluate = term => match(term, {
  Con: a => unit(a),                     //   Con: a => a,
  Div: (t, u) =>                         //   Div: (t, u) => {
    bind(evaluate(t), a =>               //     var a = evaluate(t)
    bind(evaluate(u), b =>               //     var b = evaluate(u)
    (b === 0) ? raise("divide by zero")  //     if (b === 0) throw "divide by zero"
              : unit(div(a, b))))        //     else         return div(a, b)
                                         //   }
})                                       // })
```

共通性が見えてくるはず。非純粋関数プログラミングで自然に実現できる例を純粋関数プログラミングでも自然に実現できていそうだ。つまり、副作用のある例外という言語機能でやっていたことが、副作用のない例外モナドで自然に実現できている。

また、エラーハンドリングを単純化する例外という仕組みは例外モナドとして実装されて再利用できるようになっている。（名前空間を作成していなかったりするので、このコード自体は再利用性がないのだけどね。）

ただ、関数ということもあり実質的にはネストしているので、最終行に括弧が連続しているのは美しくない。この美しくない点を Scala では for 式、 Haskell では do 記法という糖衣構文で解決している。残念ながら、これを解決できる糖衣構文が JavaScript には存在しない。

---

今回はモナドを理解するために JavaScript で例外モナドを実装してみた。モナド難民になっているところで [Monads for functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
) に出会ってふむふむなるほどとなったので記事にしてみた。いまだにモナドを意識的に使用してプログラミングできてるわけではないし、圏論のモナドにはまったく手を出せていないので、Haskell を書きながら精進していきたい。

# 参考文献

[Monads for functional programming](http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
)
関数型プログラミングの基礎 JavaScript を使って学ぶ