Rustで(Either)モナドを作る

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

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

はじめに

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

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

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

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

Either型を作る

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

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

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

型クラス

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

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

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

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

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

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

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を使ってみましょう。

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()が使えています。

モナド

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

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

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モナドの実装を見てもらった方が分かりやすいと思います。

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モナドを使ってみましょう。

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_()という同じ名前の関数を定義します。

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

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

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

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の値について実行してみます。

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()を追加したソースコードを張っておきます。

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!)
}