🚲

RustでMonadを作りたい

2024/01/21に公開

Rustで素直にMonadを作ろうとすると

trait Monad {
    type Base;
    type This<T>: Monad<Base = T>;
    
    fn unit(value: Self::Base) -> Self;
    fn bind<U>(self, f: impl FnOnce(Self::Base) -> Self::This<U>) -> Self::This<U>;
}

のようになります．しかし，この定義ではThisとSelfが同じ型クラスであるか示すことが出来ておらず，うまくいきません．(参考: https://zenn.dev/yyu/articles/f60ed5ba1dd9d5)

Rustのimplは特殊化された型に対して実装を与える(※)ものなので仕方がない気もしますが．
※ ↓の様に，型クラスに引数を与えた後の型が対象で型クラス自体が対象ではないということ．

impl Foo for Option<usize> { /* bar */ }

ここで，traitの定義を変えて型クラスと特殊化された後の型に分けます．

traitの定義

trait MonadClass {
    type This<T>: Monad<Base = T, Class = Self>;

    fn unit<T>(value: T) -> Self::This<T>;
    fn bind<T, U>(this: Self::This<T>, f: impl FnOnce(T) -> Self::This<U>) -> Self::This<U>;
}

trait Monad: EqualTo<<<Self as Monad>::Class as MonadClass>::This<Self::Base>> {
    type Base;
    type Class: MonadClass;

    fn unit(value: Self::Base) -> Self {
        Self::from(Self::Class::unit(value))
    }

    fn bind<U>(
        self,
        f: impl FnOnce(Self::Base) -> <Self::Class as MonadClass>::This<U>,
    ) -> <Self::Class as MonadClass>::This<U> {
        Self::Class::bind(self.into(), f)
    }
}

この定義では，MonadClassの方が本来のmonadの定義になります．
また，特殊化した型から型クラスがわからないと困るため，Monadの方にはClassを持たせています．

注意点はClass::This<T>とMonad<Base = T>が一致する必要があることです．
このことを表すためにMonadはEqualsToを継承しています．

追記
MonadとMonadClassはMonadInstance, Monadという命名のほうがよかったかも？

EqualsToの定義

型が一致することを表すtraitですが，少々トリッキーな定義になっています．

trait Tautology {
    type Me;
}

impl<T> Tautology for T {
    type Me = T;
}

trait EqualTo<T>: Tautology<Me = T> + Into<T> + From<T> {}
impl<T: Tautology<Me = T>> EqualTo<T> for T {}

現状のRustでは型の一致を表すことが出来ません．そのため，型が同じであることを表すマーカ(Tautology)と相互変換(From, Into)を使います．

traitはAssociated Typeのみ異なるような複数の実装を持てません．そのため，Tautologyの実装は唯一であることが保証されます．よってTautology<Me = T>を継承することでSelf == Tを保証できます．
しかし，コンパイラはSelf == Tがわからないため，From, Intoを使って変換をします．

テスト

二項演算を持ち上げるliftM2を定義してみます．

fn lift_m2<T0, T1, U>(
    f: impl Fn(T0, T1) -> U,
) -> impl Fn(<U::Class as MonadClass>::This<T0>, <U::Class as MonadClass>::This<T1>) -> U
where
    U: Monad,
{
    move |mx, my| {
        let t = mx.bind(|x: T0| my.bind(|y: T1| f(x, y).into()));
	// t.into() だと型推論がうまくいかない．
        U::from(t)
    }
}

少し不格好ですが定義はできています．

動かしてみましょう．

fn main() {
    let op = lift_m2(|x: usize, y: usize| x.checked_div(y));

    println!("{:?}", op(Some(10), Some(2))); // Some(5)
    println!("{:?}", op(Some(10), Some(0))); // None
}

struct OptionClass;
impl MonadClass for OptionClass {
    type This<T> = Option<T>;
    fn unit<T>(value: T) -> Self::This<T> {
        Some(value)
    }
    fn bind<T, U>(this: Self::This<T>, f: impl FnOnce(T) -> Self::This<U>) -> Self::This<U> {
        this.and_then(f)
    }
}

impl<T> Monad for Option<T> {
    type Base = T;
    type Class = OptionClass;
}

うまく動いています．

あとがき

やっぱりあまり綺麗な定義はできませんでした．
Rust Playgroundのリンクを上げておきます．

traitの定義

EqualsToの定義

テスト

あとがき

Discussion