🥷
Rust で柔軟な do 式とモナドを使うために作った幾つかのもの

2025/01/01に公開
 TL;DR: QualifiedDo によるオーバーライド可能な do 式のマクロと、GATを使ってモナド階層を模倣するトリックを考えたよhttps://github.com/konn/qualified_do

 はじめに新年明けましておめでとうございます。前回の記事は思ったよりも反響を頂きましてちょっとかなりびっくりしています。
https://zenn.dev/jij_inc/articles/2024-12-18-pure-haskeller-writing-rust
この記事で、? の中途半端な非局所性や、Try の有無などによる関数の名前の組合せ爆発などを念頭に、認知負荷軽減のためにモナドと do 式を使いたい、という話をしました。

今日はそこの辺りで色々試してみた結果部分的な解が得られそう、という気がしてきたのでその話をします。

部分的、というのは、Foldable や Traversable による認知負荷の軽減は今回のスコープから外れるけど、do-式によって色々な計算を局所的に見通しよく書けるという点は上手く行きそうということです。
内容としては、以下の二点です：
GATs を使ってモナドを模倣する方法は思ったより上手くいきそうだよ

Option や Result をモナドのように使えそうだよ
意味論が差し替え可能な do 式 QualifiedDo を実現する qualified_do::qdo マクロを実装したよ：
use qualified_do::qdo;
use functo_rs::data::*;
let is = vec![1, 2, 3];
let js = vec![4, 5, 6];

let ans: Vec<i64> = {
    let is = is.clone();
    let js = js.clone();
    qdo! {ZipVec {
        i <- is;
        j <- js;
        let k = 100i64;
        return i + j + k
    }
}};
assert_eq!(ans, vec![105, 107, 109]);

use functo_rs::nonlinear::*;
let ans: Vec<i64> = {
    let is = is.clone();
    let js = js.clone();
    qdo! {UndetVec {
        i <- is;
        j <- js;
        let k = 100i64;
        return i + j + k
    }
}};
assert_eq!(ans, vec![105, 106, 107, 106, 107, 108, 107, 108, 109]);

use either::*;
let ans: Vec<i64> = {
    let is: Vec<Option<i64>> = vec![Some(1), None, Some(3)];
    let js: Vec<Either<i64, i64>> = vec![Left(4), Right(5), Right(6)];
    qdo! {Iter {
        Some(i) <- is.clone();
        Right(j) <- js.clone();
        guard j % 2 == 0;
        let k = 100i64;
        return i + j + k
    }}
    .collect()
};
assert_eq!(ans, vec![107, 109]);
この記事の元になっているコードは全て以下のレポジトリにあります。まだ色々とドッグフーディングして改良したいと思っているので、リリースは先になるかとは思いますが、よかったら触ってみてください。
https://github.com/konn/qualified_do

 QualifiedDo: 意味論を差し替えられる do 構文Haskell（やそれに影響を受けた言語）の特色として、任意の「副作用」に対して do-式 というものがあります。

これは、「モナド」やそのサブクラスである「Applicative」であるような任意の制御構造を、あたかも逐次実行＋条件分離を伴う普通のプログラムであるかのような形で記述できる、というものです。

Rustでいえば、Option<T> や Result<T, E>、 Iterator<Value = E>、あとは proptest の BoxedStrategy<T> なんかも見方によってはこうしたクラスに該当します。

特に、proptest をある程度使ったことがある方向けに言えば、prop_compose マクロをもっと通常のプログラムに近い形で書けるようにし、他の型にも使えるようにしたものです。
この機能を提供しているのが、上掲のレポジトリの qualified_do クレートです。
https://github.com/konn/qualified_do/tree/main/qualified_do
早速具体例を見てみましょう。まずは prop_compose! 相当です。
https://github.com/konn/qualified_do/blob/cf29cc2b7174971aa594b686978256fc597a6391/qualified_do_proptest/src/lib.rs#L110-L127
ここでは単純に prop_map を二回重ねれば書けるものではありますが、もっと混み入った例も書けそう、という気がすると思います。
次は、Option と Result が入り乱れている例を見てみましょう。
https://github.com/konn/qualified_do/blob/902b6a32953ff2de122d09a7f884806b677d0da5/qualified_do/src/lib.rs#L31-L49
ネストされた別々の型に対するqdo! が問題なく共存できているのがわかると思います。

一見 Some(_) や Ok(_)に包まれている値を再度剥しているだけに見えるので、あまり嬉しさがわからないかもしれません。

ですが、よく見ると行番号40では、クロージャの引数である go の値に対するパターンマッチをしているのがわかると思います。
https://github.com/konn/qualified_do/blob/902b6a32953ff2de122d09a7f884806b677d0da5/qualified_do/src/lib.rs#L40
これによって、ans(Go::Go) のように Go を渡した場合は全体として Ok が返るのに対して、 false を渡して ans(NoGo) とすると、パターンマッチが「失敗」するため、まず内側の qdo!{ Optioned {..}} が全体として None になり、次いで ok_or() でエラー化されて外側の qdo!{ Resulted{..}} にも伝播し、最終的に Err になるわけです。
これと同じものをプレーンな Rust の ? で書こうとすると、? が現在のクロージャの範囲で一つの型に対してしか使えないため、次のようにクロージャを一回つくってすぐ壊すというちょっと持って回った方法が必要になります：
let ans = |go| {
    let x = (|| {
        let x = Some(1)?;
        let y = Some(2)?;
        if x + y % 2 == 1 {
            if let Go::Go = go {
                return Ok(x + y + 100);
            }
        }
        None
    })().ok_or("Fail".to_string());
    let y = Ok(3)?;
    Ok(x + y + 1000);
};
今回は単純な例ですが、例えばパーザや評価器を実装したり、データのバリデーションを行うときなどに、qdo! を使った方が見通しがよくなると思ってもらえるのではないでしょうか。。
次の例は、qdo で Iterator を「制御構造」っぽく書くものです：
https://github.com/konn/qualified_do/blob/da369c425d387e858286f3468c357f67ebf521ae/qualified_do/src/iter.rs#L187-L213
Option<i64> からなる配列 is と Either<i64, i64> から成る列 js が与えられていて、is のうちの Some のもの、 js のうちの Right に包まれている偶数について、その全ての組合せの和 + 100 からなる配列を最終的に作っています。

expected の定義が do を使わない同値な実装ですがやや混み入っていてこれなら for で書いたほうがいいかなあ……という感じがするのに対して、do の方は Some や Right に対するパターンマッチや、guard による枝刈りができているのがわかると思います。
さて、上の例では flat_map を介した総当たりでしたが、今度は zip で「同じ位置にあるやつ」を独立に取ってきて和を取るような例を見てみましょう。
https://github.com/konn/qualified_do/blob/814b807439efd3a72b7e0b2e2dbeb433dd1e8779/qualified_do/src/iter.rs#L217-L236
同じように i <- is; j <- js; のような形でとってきていますが、こちらでは同じindexのもの同士だけが組み合わされる結果になっているのが expected と見比べるとわかると思います。

これは、一つ前の例では qdo!{ UndetVec{..} } としているのに対して、今回の例では qdo!{ ZipVec{..} } のような形で qdo! の直後のプレースホルダで意味論を陽に指定しているためです。
さて、このように qdo! を使うと種々のデータ／制御構造に対して統一的かつ自由に意味論を取り替えてアルゴリズムを記述できそう、と思ってもらえたのではないでしょうか。

これが、正に Haskell の QualifiedDo で実現されていることであり、 qualified_do クレートが目指しているものです。
単純に do 式を使いたいだけであれば monadic や do_notation クレートなどがありますが、前者は各「モナドっぽい」構造ごとに do-風マクロが定義されており、後者は Lift トレイトと使いたい型が and_thenメソッドを実装している、という事を要求しており、決め打ちになっています。mdo クレートはスコープに mzero や bind メソッドがあるかどうかで脱糖をしており、この点 qualified_do の目指す点に近いですが、スコープ依存性があり複数のデータ構造に対して種々の実装を使い分けることはできなさそうです。また、いずれのクレートも最終更新が約5年以上前であるのも不安です。

qualified_do は、昨日つくったばっかりですし、do ごとに指定した名前空間の演算子を呼び出す形なので自由に意味論を局所的に取り替えることができるという点がウリです。
また、qualified_do では Haskell の世界で ApplicativeDo と呼ばれる特別な脱糖方法をデフォルトでサポートしており、簡単な変数出現チェックを行って、失敗し得るパターンマッチ[1]がなく、個別の束縛が独立して行える場合は and_then ではなく zip と map 相当の関数のみを使って脱糖するようになります。

これによって、束縛する際にリソースに .clone() が不要になったり、and_then を使えないような構造に対しても do-式を使うことができるようになるという効果があります。
わかりやすいのは、「総当たり Iter」と「同位置 zip の ZipIter」の例でしょう。

最初の Iter の例を再掲しましょう。
https://github.com/konn/qualified_do/blob/da369c425d387e858286f3468c357f67ebf521ae/qualified_do/src/iter.rs#L193-L199
ここでは「Some かどうか」「Right かどうか」といった失敗し得るパターンマッチや、guard 条件文の中で qdo 中で束縛されている j に言及しています。これらにより束縛変数間に依存関係が生じてしまうので、上の qdo-式は and_then を使って次のように脱糖されます：
Iter::and_then(
    is,
    move |i| match i {
        Some(i) => {
            Iter::and_then(
                js.clone(),
                move |j| match j {
                    Right(j) => {
                        Iter::and_then(
                            Iter::guard(j % 2 == 0),
                            move |()| {
                                let k = 100i64;
                                Iter::pure(i + j + k)
                            },
                        )
                    }
                    _ => {
                        Iter::fail("Pattern match failed:\n  expected: Right(j)")
                    }
                },
            )
        }
        _ => Iter::fail("Pattern match failed:\n  expected: Some(i)"),
    },
)
一方で、次の ZipIter の例を考えます：
https://github.com/konn/qualified_do/blob/902b6a32953ff2de122d09a7f884806b677d0da5/qualified_do/src/iter.rs#L223-L228
ここではパターンマッチも使われていませんし、i, j に言及するような条件文があるわけでもないので、各束縛はすべて独立して行えることがわかります。

qdo マクロはこれを検出し、次のように脱糖されます：
ZipIter::fmap(
    |((i, j), k)| i + j + k,
    ZipIter::fmap(
        |x| { let y = 100i64; (x, y) },
        ZipIter::zip_with(
            |i, j| (i, j),
            is, js,
        ),
    ),
)
zip_with と fmap のみで脱糖されていることがわかると思います。ではここで、ZipIter の方を次のようにパターンマッチを使って書きかえてみるとどうでしょうか？
qdo! {ZipIter {
    Some(i) <- is;
    j <- js;
    let k = 100i64;
    return i + j + k
}}
すると、コンパイラは次のようなエラーを出して失敗します：
error[E0599]: no variant or associated item named `and_then` found for enum `ZipIter` in the current scope
  --> qualified_do/examples/debug.rs:23:9
   |
23 |           qdo! {ZipIter {
   |  _________^
24 | |             Some(i) <- is;
25 | |             j <- js;
26 | |             let k = 100i64;
27 | |             return i + j + k
28 | |         }}
   | |__________^ variant or associated item not found in `ZipIter`
   |
   = note: this error originates in the macro `qdo` (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0599]: no variant or associated item named `fail` found for enum `ZipIter` in the current scope
  --> qualified_do/examples/debug.rs:23:9
   |
23 |           qdo! {ZipIter {
   |  _________^
24 | |             Some(i) <- is;
25 | |             j <- js;
26 | |             let k = 100i64;
27 | |             return i + j + k
28 | |         }}
   | |__________^ variant or associated item not found in `ZipIter`
   |
   = note: this error originates in the macro `qdo` (in Nightly builds, run with -Z macro-backtrace for more info)
これは、ZipIter が and_then() と fail() を実装していないためです。敢えて実装していないわけではなく、実は、「イテレータを zip する」という形の制御構造にはdoがちゃんと動作する「and_then()」を定義できない事が数学的に証明できます[2]。

今回は他の束縛値に依存するような束縛を書いてしまったので ZipIter の範囲を越えてしまったことがこのエラーによりわかるわけです[3]。and_then だけを使った脱糖では ZipIter に対して do を使うことはできませんが、qualified_do が ApplicativeDo の脱糖にも対応しているため、妥当な範囲では ZipIter に対しても do 式を使って書いてやることができるわけです。

 閑話休題： proc macro を書いてみてHaskell で総称プログラミングで足りない時はしょっちゅう Template Haskell でマクロを書いているのもあり、 syn クレートを使って構文木を変形していく形で実装していくのは手に馴染みました。

proc macro は第一義的には入力となるソースコード片をトークン列として表現し、それを変換する形で書くのもあり、本来は Rust の構文としては不正な構文も定義できるのが面白いと思いました。Haskell ではこういう時は QuasiQuote を使って独自のパーザを書いてやって拡張することになりますね。
一方で、Template Haskell ではトークン列の変換ではなく、マクロへの引数とスコープに入っている型・変数などのメタデータを元に構文木を合成する形でマクロを記述します。メタデータがあるので、 None <- hoge みたいな式があった場合、左辺の None が変数なのか構築子に対するパターンマッチなのか構文的に判断ができますし、渡されたパターンの構築子が newtype のもので従ってマッチが常に成功するかどうか、といった情報も判断できます。また、フレッシュな変数を生成することもでき、衛生的なマクロを書くことができます。
この点、Rust トークン列の変換でしかなく、名前解決もされていないため、必ずしも必要な情報が揃わないのはちょっと不便でした。フレッシュな変数もなんとか名前の規約でカバーするしかなく、この辺りは改善されると嬉しいなあという気持ちになりました。

 GAT を使ったモナド階層の定式化さて、前節では qdo! で do-式を色々な型に対して使えるようにしたという話をしました。

基本的には and_then, fmap, pure, zip_with などが定義されたモジュールないし型を渡してやればよいわけですが、Option や Result などについては、Haskell での Functor や Monad とほぼ同等の構造が入るので、上の Optioned や Resulted などはこうした抽象化を介して do-式を使えるようにしています。

これは、型制約でどこまでの機能が使えるのかドキュメントでわかりやすかったり、規則を満たしていることを明示したいという動機からです。
具体的には、qualified_do の脱糖に関連しているものは次になります：

Functor: .map() 関数があるもの

Apply: Functor に加えて .zip_with() が使えるもの

Pointed: Functor に加えて Some(_) や Ok(_) のような「値を文脈に入れる」関数 Type::pure(x)[4]が使えるもの

Applicative: Apply かつ Pointed[5]

Monad: Applicative に加えて .and_then() または .flatten() が使えるもの

MonadFail: Monad に加えて、失敗関数 Type::fail(message) が使えるもの

Alternative: Applicative かつ .or_else() や .filter() が使えるもの
なんだか色々ありますが、大事なことはdo-式はこうした色々な「制御関数」を手続的な構文で繋げて書くための機構であるということです。

do-式のどの機能までを使えるのか？という観点からは、次のように言い換えることができます：

Functor: qdo!{ Namespace { x <- a; let a = ...; return (f x a) } } の形のもの。

Applicative: ApplicativeDo で脱糖できるもの。束縛した値に関する条件分岐を含まないもの。

Monad: 他の束縛値に依存した値を束縛できるもの。

Alternative: guard 条件式が使えるもの。

MonadFail: 更にパターンマッチがバインディング内で使えるもの。
これらの階層を提供しているのが、上述のレポジトリの functo_rs クレートです：
https://github.com/konn/qualified_do/tree/main/functo_rs
ここでは、三種類のモナド階層が定義されています。以前の Linear Haskell の記事や前回の記事でも触れましたが、線型型や所有権システムが絡むと、モナドは複数の種類に分裂します。
https://zenn.dev/jij_inc/articles/2024-12-18-pure-haskeller-writing-rust#monadください-wow-wow-monadください-do：rust-の-try_-とか-%3F-とか、認知負荷高すぎないですか？
https://zenn.dev/konn/articles/2023-10-01-linear-haskell-in-2023#linear-state-monad-で線型状態を引き回す
元ネタは、Linear Haskell の中の人が書いた次の記事です：
https://www.tweag.io/blog/2020-01-16-data-vs-control/
実のところ、Haskell に QualifiedDo が導入されたそもそものモチベーションは、こうした「モナドっぽいけど微妙に異なる型クラスたち」に対しても do 式を使えるようにしたい、というものでした。

簡単にまとめれば、具体的には次の三つです：

無制限（非線型）モナド階層：全ての制御関数の引数・返値に Clone を要求し、取るクロージャも何回でも使われ得る（FnMut）もの。
Haskellで通常「モナド」と呼ばれているものです。

UndetVec などは無制限モナドにしかならない


データモナド階層：渡された値は何回も使われ得、渡されたクロージャを何回も使える（FnMut）。
データ Applicative / Alternative まではあるが、データMonadは定義しても使いようがないので存在しない。

ZipVec はデータ Apply、ZipIter はデータ Applicative だが、次の Control にはならない


制御モナド階層：データモナドであって、mapなどに渡されたクロージャを高々一回しか使わないもの（FnOnce を受け取るもの）。
Haskell の場合は「きっかり一回」使うが、Rustの所有権システムは「高々一回」になる。

Option や Result は Haskell では制御モナドにならないが、Rust では制御モナドになる！

これらが and_then などの引数として FnMut vs FnOnce のどちらを取るのか、各パラメータにどこまで Clone を要求するかで分裂する訳です。

functo_rs ではこれらを使い分けるための AsData や AsControl、AsNonlinear ファントム型などを提供しており、たとえば先の Optioned などは AsControl<OptionFunctor> の型シノニムになっています。
上でもちらっと書いたように、Rust の所有権システムは高々一回消費すればよいという事を要求しているため、値を失敗時に捨て得る Option や Result にも制御モナドの構造を入れることができ、do-式を自由に使えるようになるのは、Rust の大きなアドバンテージだと思います。
こうした階層の定式化に、functo_rs では Generic Associated Types (GAT) の機能を使っています。GATをつかってこうしたパラメータ多相型をエミュレートする方法は、たとえば recursion-schemes クレートなどで使われています。
https://crates.io/crates/recursion-schemes
GAT を使ってモナドを模倣する試みとしては、他にも YOSHIMURA Yu さんの記事があります：
https://zenn.dev/yyu/articles/f60ed5ba1dd9d5
Yu さんの記事では完全には上手く行かなかったようですが、今回開発した functo_rs や上の recursion-schemes では直接 Option や Vec に対する trait を作るのではなく、OptionやVecに乗り得るMonadの実装に対応するファントム型を用意して、そのGAT Container<T> として実際のパラメトリックなデータを定義するようにしています。以下がその定義例です：
https://github.com/konn/qualified_do/blob/902b6a32953ff2de122d09a7f884806b677d0da5/functo_rs/src/data.rs#L20-L26
https://github.com/konn/qualified_do/blob/902b6a32953ff2de122d09a7f884806b677d0da5/functo_rs/src/data.rs#L39-L49
https://github.com/konn/qualified_do/blob/da369c425d387e858286f3468c357f67ebf521ae/functo_rs/src/control.rs#L79-L94
トレイトを実装している UndetVec そのものがコンテナの役割をはたしているのではなく、UndetVec::Container<T> が本来 Functor や Apply などの性質を持たせたいパラメータ多相の型に対応しているのが見てとれるかと思います。
こうすると、直接  and_then や fmap を呼ぼうとした場合メソッドチェーンにならないので使いづらくなりますが、 do 式の脱糖へ利用したいだけであれば特段問題にはならないわけです。また、上の Iter の例で見たように、同一の Vec に対して、zip するのか flat_map するのかという別々の実装を newtype を介さずに分けて扱えるという利点もあります。
前回の記事でも書いたように、また、recursion-schemesで用いられているように、この方法はたとえば再帰的に定義された型に対して Haskell 流の再帰スキームを使って色々な処理を記述するのにも使えるはずです。

 まとめと今後の課題Rust で QualifiedDo を使うためのマクロと、GATを使ってモナド階層を Rust で模倣する方法について紹介しました。

まだちゃんと使い込んでいないので、しばらくドッグフーディングして育てつつ、いい感じになってきたら crates.io にリリースしたいなと思っています。

また、qualified_do では現状 zip_with しか使っていませんが、場合によっては ap と join を使った方が便利な場合もあります（Haskellではそうしている）。脱糖方法をいいかんじに切り替えられるような方法も考えられたらいいなと思っています。とはいえ、素直にやろうと思うと、与えられた関数が存在するかどうかをマクロ展開時に取得できる必要があり、これは Template Haskell ではできても現状の proc macro ではできないので、どうにかして設定項目を増やすことになるのかなと思っています。
また、今回は Monad 階層だけで、Foldable / Traversable については踏み入っていません。GATを使えば定式化自体はできるかと思いますが、traversable や sequence などを呼び出すときにメソッドチェーンが使えないので結構不便になってしまうのではないかと思っています。

それよりも Iterator の構造を所与のものとして fold や collect の try_ ならぬ effectful_ 版を考えていくのがいいのかなという気がしています。とはいえ、Option<Result<T, E>>から Result<Option<T>, E>にしたりとかにはこの方法は使えなさそうなので、幾つか補助的な機構を用意しないといけないのかなと思っています。
ではでは、そんな感じで。今年もよい Rust & Haskell を！

脚注
newtype などに対するものは等は失敗し得ないパターンマッチになりますが、マクロ展開の行われるタイミングの都合上判断できません。そこで、こういう場合は ~Newtype(x) <- expr のように、パターンの前に ~ を付けてユーザの側で脱糖方法を指定する形になります。失敗し得るパターンに ~ を付けた場合は、Rust の網羅性チェッカが脱糖後のコードをエラーにするので、安全性の上では問題ありません。 ↩︎
ここでいう「do がちゃんと動作する and_then が存在しない」というのは、厳密には「zip するような Applicative 構造と両立するような Monad 構造が存在しない」という事です。 ↩︎
このあたり、proc macro 内の具体的な対応部分をエラー中で報告できるようにしたいんですが、マクロ展開後のエラー報告を弄る方法があるのかよくわかってないです。もうちょっと勉強したいところ。 ↩︎
歴史的注意：かつて Haskell では pure は Monad の一部である return 関数でしたが、Applicative クラスが導入された際に pure メソッドとして再導入され、現在ではどちらでも同値であるものの pure を使うのが主流になっています。 ↩︎
Haskellの標準ライブラリでの階層では、Apply と Pointed は分離されず Functor の次に Applicative があります。とはいえ、有限配列などは たとえば zip に関して Pointed になり得ない（無限配列が必要になる）などの都合があるため、Apply や Pointedを提供しているパッケージがあります。今回は、たとえば Vec などを念頭に置いて Apply と Pointed を分離しています。 ↩︎
Rust で柔軟な do 式とモナドを使うために作った幾つかのもの

TL;DR: `QualifiedDo` によるオーバーライド可能な do 式のマクロと、GATを使ってモナド階層を模倣するトリックを考えたよ

はじめに

QualifiedDo: 意味論を差し替えられる do 構文

閑話休題： proc macro を書いてみて

GAT を使ったモナド階層の定式化

まとめと今後の課題

Discussion
