📦

RustのGATsでモナドを作れるか？

に公開
Rust
関数型プログラミング
tech

はじめに

Rust 1.65で GATs (Generic associated types)[1] が追加された。これは次のようにassociated type（型メンバー）が型パラメーターを取ることできるものとなっている。

trait Monad {
    type This<B>;
}

このように型を取る型を記述できるようになったときに思いつくものとして「モナド」がある。モナドの具体的な定義や性質はいったん放置するとして、任意の型Aについて、たとえばList<A>やOption<A>がモナドとなる。したがって次のようにトレイトMonadを定義すればOptionなどを次のようにモナドへ適合させることができるのではないかと思うだろう。

impl<A> Monad for Option<A> {
    type This<B> = Option<B>
}

この記事では実際に上記のMonadのようなトレイトを実際のOptionなどに適用してどの程度うまくいくのかを伸べる。なお、この記事を読むにあたってモナドや関数型言語などの知識はほぼ必要なく、HaskellやScalaなど他の言語にあるものとしてモナドを選んだだけである。
この記事に記載されている完全なソースコードは下記のGitHubリポジトリーから入手できる。

TL; DR

  • GATsではモナドなどが必要とする高階多相を模倣することはできない（or 難しい🤔）
  • 少なくともGATsでそのまま作れるといった簡単な感じではなさそう

トレイトMonadの定義

トレイトMonadは次のように定義される。

monad.rs
pub trait Monad {
    type A;
    type This<A>: Monad;

    fn pure_m<B>(b: B) -> This<B>;

    fn flat_map<B, F>(self, f: F) -> Self::This<B>
    where
        F: FnMut(Self::A) -> Self::This<B>;
}

たとえばこれのOptionのimplは次のように定義できる。

data/option.rs
impl<A> Monad for Option<A> {
    type A = A;
    type This<B> = Option<B>;

    fn pure_m<B>(t: B) -> Option<B> {
        Some(t)
    }

    fn flat_map<B, F>(self, mut f: F) -> Option<B>
    where
        F: FnMut(A) -> Option<B>
    {
        self.and_then(f)
    }
}

このように一見すると上手くいっているように見える。

MonadからApplicativeの導出

ここでMonadとは別にApplictaiveという次のトレイトを考えてみる。

applicative.rs
pub trait Applicative {
    type A;
    type This<B>: Applicative;

    fn pure_a<B>(t: B) -> Self::This<B>;

    fn map2<B, C, F>(self, mb: Self::This<B>, f: F) -> Self::This<C>
    where
        F: FnMut(Self::A, B) -> C;
}

さきほど作ったトレイトMonadと今回のトレイトApplicativeについて、この違いは「コールバック」という観点で考えると分かりやすいかもしれない。


MonadとApplicativeのf（コールバック）への引数の関係

このようにMonadのflat_mapはselfの値をコールバックであるfに渡しているのに対して、Applicativeのmap2は別のThis<B>を引っ張ってきてそれとselfの値を一気にfで処理している。このときmb: This<B>の構築に型Aの値は一切関与しないことが重要である。つまりMonadのflat_mapには「Aの値が得らればfを実行する」という逐次的な性質があり、一方でApplicativeのmap2は「selfとmbを独立した順で処理して、この2つが得られ次第fを実行する」という順不同な性質を表現していると考えられる。
さて、どうしてあえてApplicativeを出してきたかというと、Monadは順が固定されているのに対して、Applicativeは順がない（= 適当な順でやってもいい）ので、Monadなものは常にApplicativeと言えそうである。したがってimpl<M: Monad> Applicative for Mの定義を目指す。

monad.rs
impl<M: Monad> Applicative for M {
    type A = <M as Monad>::A;
    type This<B> = <M as Monad>::This<B>;

    fn pure_a<B>(t: B) -> Self::This<B> {
        <M as Monad>::pure_m(t)
    }

    fn map2<B, C, F>(self, mb: Self::This<B>, f: F) -> Self::This<C>
    where
        F: FnMut(Self::A, B) -> C
    {
        self.flat_map(|a: Self::A| {
            mb.flat_map(|b: B| {
                M::pure_m(f(a, b))
            })
        })
    }
}

このようにMonadであることを前提にApplicativeを作りだせそうではあるが、実これはコンパイルが通らず次のようなエラーとなってしまう。

  --> src/monad.rs:28:13
   |
15 |   impl<M: Monad> Applicative for M {
   |        - this type parameter
...
28 | /             mb.flat_map(|b: B| {
29 | |                 M::pure_m(f(a, b))
30 | |             })
   | |______________^ expected type parameter `M`, found associated type
   |
   = note: expected associated type `<M as Monad>::This<_>`
              found associated type `<<M as Monad>::This<B> as Monad>::This<_>`

ようするにflat_mapしたあとの型がselfの型と一致しているかが定かではないためこのようにコンパイルエラーとなってしまってうまくいかない。
今mb.flat_mapの返り値の型はmb: <M as Monad>::This<B>のflat_mapなので<<M as Monad>::This<B> as Monad>::This<C>を求めることになる。ところがM::pure_m(f(a, b))の型は<M as Monad>::This<C>であるため型エラーとなってしまっている。

mb.flat_map(|b: B| -> <<M as Monad>::This<B> as Monad>::This<C> {
    M::pure_m(f(a, b)) // -> <M :: Monad>::This<C>
})

複雑なassociated typeが多くなってきたので、下記の表で整理する。

型 意味
<M as Monad>::This<B> mbの型
<M as Monad>::This<C> self.flat_map<C, _>の返り値、またはM::pure_m<C>の返り値
<<M as Monad>::This<B> as Monad>::This<C> mb.flat_map<C, _>の返り値

そして、M: MonadがApplicativeをimplするためには任意の型B,Cにおいて下の型の等価が必要とされている。

<<M as Monad>::This<B> as Monad>::This<C> == <M :: Monad>::This<C>

しかし実はこのMonadトレイトは下記のような穴があり、次のような変なimplを作ることができてしまう。

impl<A> Monad<A> for Option<A> {
    type A = A;
    type This<B> = Result<A, Error>; // 😇 😇 😇 😇 
}

したがって少なくともMonadトレイト制約ではflat_map後のThisが同一かどうかを確定させられないため、RustコンパイラーはこのようなMonadからApplictaive導出を許可してくれない。

余談

このページ👇では早々にGATsでモナド（記事ではFunctor）のような高階多相型（Higer-kinded types）の模倣はできないことを指摘している[2]。

まとめ

Rust 1.65のGATsのニュースでこれはモナドなどをつくっていけるかと思ったが、少なくともこの路線で簡単に作れるということはないようだ。筆者はかつてモナドは万能な副作用の抽象化方法だと思っていたが、RustやSwiftなどを書くようになった今はプログラム言語に高階多相を要求するのが大きな障壁となるとも思っている。

脚注

  1. 似た名前のものにHaskellなどに存在する GADTs (Generalized algebraic datatypes) がある。GATsとGADTsはあまり関係がないとは思うが、個人的にはGADTsをリスペクトして（？）GATsの“G″は“Generalized″にしてもよかったかもしれないと思う。 ↩︎

  2. そして、このような👇文法を提案していたりもする。

    trait Monad where Self<A> {
    fn flat_map<F, B>(self, f: F) -> Self<B>
    where
        F: FnOnce(A) -> Self<B>;
}
    ↩︎

Discussion