RustのGATsでモナドを作れるか?
はじめに
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
は次のように定義される。
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
は次のように定義できる。
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
という次のトレイトを考えてみる。
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
の定義を目指す。
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などを書くようになった今はプログラム言語に高階多相を要求するのが大きな障壁となるとも思っている。
Discussion