📝

RustでOptionの配列の最大値・最小値を取り出す

2021/11/21に公開

Rust

tech

はじめに

Optionの配列、例えばVec<Option<usize>>^[1]から最大値と最小値を取り出す方法について書きます。間違ったやり方を紹介してから正しいやり方を紹介します。どちらのやり方も、思考の足跡を辿れるようにしておきます。

間違ったやり方

Option<T: Ord>な配列から最大値と最小値を取り出したいと考えています。たしかIteratorトレイトにmaxメソッドとminメソッドがあるので、ベクタにしろスライスにしろiterを呼んでからこれを使えば最大値と最小値を取り出せるはずです。

ところでOptionはOrdを実装していたでしょうか？Optionのドキュメントを見るとtrait implementationsのところにOrdの実装があると書いてあります。これならいけそうです。試しに書いてみましょう。

書いたコードは下の通りになります。Rust Playgroundのコードではmainの中に簡単なテストを記述しました。実行してみましょう。

fn find_max_of_options<T: Ord>(v: &[Option<T>]) -> Option<&T> {
    v.iter()
     .map(|x| x.as_ref()) // 最後にflattenを呼ぶために、&Option<T>をOption<&T>に変換
     .max()
     .flatten() // Option<Option<&T>>をOption<&T>につぶす
}

fn find_min_of_options<T: Ord>(v: &[Option<T>]) -> Option<&T> {
    v.iter()
     .map(|x| x.as_ref())
     .min()
     .flatten()
}

実行してみると以下のエラーが出ます。最大値の取り出しは問題がないようですが、SomeとNoneが混ざった配列の最小値を計算するとNoneが最小値として取り出されてしまうようです。原因を考えてみましょう。

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 4.05s
     Running `target/debug/playground`
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `None`,
 right: `Some(0)`', src/main.rs:20:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

なぜこうなったのか

まずはOptionがOrdを実装している部分を見てみましょう。Deriveマクロで実装されているようです。

Ordのドキュメントにderiveマクロによる実装についての説明があります。それによるとderiveでenumにOrdを実装した時は、バリアントは上から下の順に順序づけられるとあります^[2]^[3]。つまり、上にあるバリアントの方が小さくなります。

ここでOptionの定義を確認すると、Noneの方が上であることがわかります。したがって、先ほど私が実装した関数find_min_of_optionsは受け取った配列にNoneが混ざっているとNoneを最小値として返します。これは作ろうと思っていた振る舞いではありません。作ろうとしていた関数をより正確に説明すると、Option<T>を出力するイテレータからNoneであるものを除いて最大・最小の要素を取り出す関数ということになります。

正しいやり方

配列にNoneが混ざっているとNoneが最小値になってしまうので、minを取る前にfilter_mapでNoneを取り除きます。filter_mapは与えられたクロージャがNoneを返した時にその要素を取り除きます。なので要素をそのまま返すクロージャをfilter_mapに与えます。

以下にコードが修正したコードになります^[4]。Rust Playgroundで実行してみるとエラーは出ません。正しく動いているようです。

fn find_max_of_options<T: Ord>(v: &[Option<T>]) -> Option<&T> {
    v.iter()
     .map(|x| x.as_ref())
     .filter_map(|x| x)
     .max()
}

fn find_min_of_options<T: Ord>(v: &[Option<T>]) -> Option<&T> {
    v.iter()
     .map(|x| x.as_ref())
     .filter_map(|x| x)
     .min()
}

おわりに

今回の教訓をまとめておきましょう。

Ordの実装に注意しましょう。今回はderiveされた実装でしたが、ライブラリが提供する型には普通にimpl Ordして実装するものもあるでしょう。常に確認する必要があります。
Optionに入った値を大小比較をするときはNone取り除いた方が賢明でしょう。
ユニットテストを書くことで、具体例を通して自分が作りたいプログラムを考えましょう。正確ではないアイデアをテストを使うことでよりクリアーにしていきましょう。

脚注

正確にはIterator<Output = Option<T>>やIterator<Output = &Option<T>>を実装しているオブジェクトです。この記事を書こうと思ったきっかけになったコードでは、データベースから取り出したVec<Option<NaiveDate>>の最大値・最小値を取り出そうとしました。 ↩︎
ちなみに構造体にOrdをderiveしたときは、フィールドを上から下の順の順番にしたときの辞書式順序となります。 ↩︎
もしライブラリを実装していてstructやenumにOrdをderiveしているのであれば、無闇にフィールドやバリアントの順序を変更することは、大小比較の結果を変えてしまうので互換性を破壊することになります。 ↩︎
|x| xの代わりにstd::convert::identityを使うこともできるでしょう。
また、このコードのように配列の要素の参照を返す場合は、mapとfilter_mapをひとまとめにしてfilter_map(|x| x.as_ref())と書くこともできます。
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=28e5e146770926c2b6a3fcf39861f3b1 ↩︎