Rustで(Either)モナドを作る

Rust面白そうだな〜と思い、1日遊んでみた成果です。

Rustの特徴であるポインタの借用などについては、まだ理解ができていないので使っていません。

## はじめに

Rustは高カインド型(型変数を取る型)をサポートしていないので以下のようにモナドを定義することはできません。

```rust
trait Monad<X<_>> {
    ...
}
impl Monad<Option> for Option {
    ...
}
```

これを力業で解決し、`Either`モナドを作成します。

なお、使用したRustのバージョンは`rustc 1.5.0`です。

## Either型を作る

標準ライブラリに`Either`型がなさそうなので、定義します。

```rust
enum Either<E, A> {
    Left(E),
    Right(A),
}
```

`Either`型は、`E`あるいは`A`のどちらかの型を保持します。
一般的に`Left`はエラー値を保持し、`Right`が計算結果を保持します。

## 型クラス

Rustのトレイトはアドホックポリモーフィズムを実現するものであり、Haskellにおける型クラスに相当します。

ここでは、実際に`Show`型を定義し、Rustにおける型クラスの使い方を紹介します。

まずは、`Show`型の定義です。

```rust
trait Show {
    fn show(self) -> String;
}
```

`Show`は自身を文字列で表現できることを宣言します。

`i32`,`String`,`Either`型について実際に`Show`を実装してみましょう。

```rust
impl Show for i32 {
    fn show(self) -> String {
        self.to_string()
    }
}

impl Show for String {
    fn show(self) -> String {
        self
    }
}

impl<E: Show, A: Show> Show for Either<E, A> {
    fn show(self) -> String {
        match self {
            Right(a) => format!("Right({})", a.show()),
            Left(e) => format!("Left({})", e.show()),
        }
    }
}
```

`i32`と`String`型については見たままなので、`Either`型について説明します。

まず、`Either`は型変数を2つ取るため、`Either<String, i32>`のように一意に型を決定することができません。必要な型の組み合わせ全てについて`Show`を実装することもできますが、人間のする仕事ではありません。`impl<E, A>`とすることで、`show()`メソッドが呼ばれたときの`Either`に合わせて`Show`を解決できます。

また、`Either`が`Show`を実装していても、内部に保持する型`E`や`A`が`Show`を実装していなければ、`show()`メソッドを実装するのが困難になります。そこで、`E: Show, A: Show`として、内部に保持する型が`Show`を実装しているという制約をつけます。

実際に`Show`を使ってみましょう。

```rust
let r: Either<String, i32> = Right(100);
println!("{}", r.show());
// Right(100)

let l: Either<String, i32> = Left("Hello".to_string());
println!("{}", l.show());
// Left(Hello)
```

`i32`と`String`のどちらも`Show`を実装しているため、`Either`である`Right`と`Left`で`show()`が使えています。

## モナド

モナドについての説明は省きます。
ファンクタ等を無視して、いきなりモナド実装にとりかかります。(ファンクタは最後のソースコードには入っています)。

まずは、モナドの定義です。

```rust
trait Monad<A, B, MB> {
    fn return_(a: A) -> Self;
    fn bind<F>(self, f: F) -> MB where F: Fn(A) -> MB;
}
```

型変数がごちゃごちゃしていますが、[はじめに](#はじめに)で述べたように高カインド型を扱うことができないので、モナドを定義するために必要な全ての型を具象型で受け取ります。

各型変数が具体的になにを表すかを説明します。

- A: 現在内部に持っている型
- B: 計算後内部に持つ型
- MB: 計算後の自身の型

`return_()`は`A`型の値を現在のモナドに包んで返します。
`bind()`は現在保持している値を使って計算し、その結果を現在のモナドに包んで返します。

実際にEitherモナドの実装を見てもらった方が分かりやすいと思います。

```rust
impl<E, A, B> Monad<A, B, Either<E, B>> for Either<E, A> {
    fn return_(a: A) -> Either<E, A> {
        Right(a)
    }

    fn bind<F>(self, f: F) -> Either<E, B> where F: Fn(A) -> Either<E, B> {
        match self {
            Right(a) => f(a),
            Left(e) => Left(e),
        }
    }
}
```

`Either<E, A>`について`Monad<A, B, Either<E, B>>`を定義しています。先ほど型変数の説明の意味が分かると思います。また、`Show`のときと同じように`impl<E, A, B>`としているので、モナドのメソッドを呼んだタイミングで正確な型が決まります。

`return_()`では`A`型を成功を表す`Right`に包んで返します。
`bind()`では自身が`Right`であるなら内部の値を使って計算を行い、自身が`Left`であるならそのまま値を返します。

これで`Either`モナドの完成です。

## モナドを使う

では、実際に`Either`モナドを使ってみましょう。

```rust
let r: Either<String, i32> = Right(100);
let r2 = r.bind(|i|
    Monad::<i32, i32, Either<String, i32>>::return_(i*2i32)
);
println!("{}", r2.show());
// Right(200)

let l: Either<String, i32> = Left("Hello".to_string());
let l2 = l.bind(|i|
    Monad::<i32, i32, Either<String, i32>>::return_(i*2i32)
);
println!("{}", l2.show());
// Left(Hello)
```

`Right`に対しては計算が行われていて、`Left`に対しては計算が行われていないので、成功しているようです。

ただし、一目で分かるように、`return_()`を使うのがものすごく大変になっています。`Either::return_()`と書けるかと思ったのですが、`Monad`トレイトの`MB`を解決できないためかコンパイルができませんでした。もちろん`return_()`を使わずに`Right()`を使っても良いのですが、そこはモナドの世界なので`return_()`使いたいですよね。

これを解決するために、`return_()`という同じ名前の関数を定義します。

```rust
fn return_<MA, A, M: Monad<A, A, MA>>(a: A) -> M {
    M::return_(a)
}
```

この関数は`Monad::return_()`の型変数を解決してくれます。

これで、準備は整いました。
`Either`モナドを生かした計算をしてみましょう。

```rust

fn div_by_3(i: i32) -> Either<String, i32> {
    println!("div {}", i);
    if i%3 == 0 {
        Right(i/3)
    } else {
        Left(format!("'div_by_3' failed when {}", i))
    }
}

fn try_div_by_3_twice(e: Either<String, i32>) -> Either<String, String> {
    e.bind(|i1|
        div_by_3(i1).bind(|i2|
            div_by_3(i2).bind(|i3|
                return_(format!("{} -> {} -> {}", i1, i2, i3))
    )))
}
```

`div_by_3()`はその名の通り、入力値を3で割ります。ただし、3で割り切れない値については、`Left`を使ってエラーを報告してくれます。関数の先頭で`println!()`しているのは計算過程を見やすくするためです。

`try_div_by_3_twice()`は`div_by_3()`を2回実行します。さらに、計算過程で入力値がどのように変化したのかを文字列として教えてくれます。注目して欲しいのは`return_()`を使っている部分で、最初と比べると明らかに簡単に書けるようになっています。

では、実際にいろいろな`Either`の値について実行してみます。

```rust
let a = Right(9);
let b = try_div_by_3_twice(a);
println!("{}", b.show());
// div 9
// div 3
// Right(9 -> 3 -> 1)

let a = Right(2);
let b = try_div_by_3_twice(a);
println!("{}", b.show());
// div 2
// Left('div_by_3' failed when 2)

let a = Left("I'm Left!".to_string());
let b = try_div_by_3_twice(a);
println!("{}", b.show());
// Left(I'm Left!)
```

`Right(9)`では、`Right(9 -> 3 -> 1)`というように、3で2回割り算を行った結果が出力されています。

`Right(2)`では、2は3で割り切れないため失敗し、`Left('div_by_3' failed when 2)`が出力されています。
また`div 2`が表示されているので、`div_by_3()`が一度呼ばれたことは確認できますが、一度失敗したので、以降の計算は無視されています。

`Left("I'm Left!".to_string())`では、入力値がそもそも失敗しているので`try_div_by_3_twice()`では何も計算が行われずにそのままの値が返ってきています。

## まとめ

Rustでは高カインド型を扱うことができませんが、モナドトレイトを作成し、`Either`モナドを実装することができました。もちろん`Either`だけでなく標準の`Option`等についても実装ができると思います。

Rustにはマクロもあるようなので、モナド用の構文などが作れればより充実したモナドライフがおくれると思います。

質問があればコメントに書いて頂ければ回答しますが、私自身がRust初心者なので、細かい仕組みなどについては分かっていない部分が多いです。

最後に、今回作成したプログラムにFunctorと、Functorを引数に取る関数`decorate()`を追加したソースコードを張っておきます。

```rust
use self::Either::{Left, Right};

enum Either<E, A> {
    Left(E),
    Right(A),
}

trait Show {
    fn show(self) -> String;
}

impl<E: Show, A: Show> Show for Either<E, A> {
    fn show(self) -> String {
        match self {
            Right(a) => format!("Right({})", a.show()),
            Left(e) => format!("Left({})", e.show()),
        }
    }
}

impl Show for i32 {
    fn show(self) -> String {
        self.to_string()
    }
}

impl Show for String {
    fn show(self) -> String {
        self
    }
}

trait Functor<A, B, FB> {
    fn fmap<F>(self, f: F) -> FB where F: Fn(A) -> B;
}

impl<E, A, B> Functor<A, B, Either<E, B>> for Either<E, A> {
    fn fmap<F>(self, f: F) -> Either<E, B> where F: Fn(A) -> B {
        match self {
            Right(a) => Right(f(a)),
            Left(e) => Left(e),
        }
    }
}

trait Monad<A, B, MB>: Functor<A, B, MB> {
    fn return_(a: A) -> Self;
    fn bind<F>(self, f: F) -> MB where F: Fn(A) -> MB;
}

impl<E, A, B> Monad<A, B, Either<E, B>> for Either<E, A> {
    fn return_(a: A) -> Either<E, A> {
        Right(a)
    }

    fn bind<F>(self, f: F) -> Either<E, B> where F: Fn(A) -> Either<E, B> {
        match self {
            Right(a) => f(a),
            Left(e) => Left(e),
        }
    }
}

fn return_<MA, A, M: Monad<A, A, MA>>(a: A) -> M {
    M::return_(a)
}

fn decorate<FA: Functor<A, String, FS>, FS: Functor<String, A, FA>, A: Show>(fa: FA) -> FS {
    fa.fmap(|a| format!("***{}***", a.show()))
}

fn div_by_3(i: i32) -> Either<String, i32> {
    println!("div {}", i);
    if i%3 == 0 {
        Right(i/3)
    } else {
        Left(format!("`div_by_3` failed when {}", i))
    }
}

fn try_div_by_3_twice(e: Either<String, i32>) -> Either<String, String> {
    e.bind(|i1|
        div_by_3(i1).bind(|i2|
            div_by_3(i2).bind(|i3|
                return_(format!("{} -> {} -> {}", i1, i2, i3))
    )))
}

fn main() {
    let a = Right(9);
    let b = try_div_by_3_twice(a);
    let c = decorate(b);
    println!("{}", c.show());
    // div 9
    // div 3
    // Right(***9 -> 3 -> 1***)

    let a = Right(2);
    let b = try_div_by_3_twice(a);
    let c = decorate(b);
    println!("{}", c.show());
    // div 2
    // Left(`div_by_3` failed when 2)

    let a = Left("I'm Left!".to_string());
    let b = try_div_by_3_twice(a);
    let c = decorate(b);
    println!("{}", c.show());
    // Left(I'm Left!)
}
```