📘

PartialOrdとOrdを使えるように

2024/05/03に公開

Rust

tech

はじめに

Rustで適当にクラスをつくって大小関係を評価したいときが多々あります。その際に使われるPartialEqとEqについては、以前に自分が分かるように整理しました。

PartialEqとEqを使えるように

前の記事はPartialEqとEqについて、今後時間を割かなく良いようにすることが目的でした。この記事はOrdとPartialOrdについても同様に、今後ググったりしなくて済むようにすることが目的です。

これらのトレイトは、型の比較に関する挙動を制御し、コレクション型のソートにおいて重要な役割を果たしていそうなことが分かっています。でも実際何やっているんだ、というところを見ていきます。

PartialOrd vs Ord

PartialOrd: これは、2つの値を比較し、その大小関係を判定するためのトレイトです。<、>、<=、>=演算子をオーバーロードすることで、2つの値の大小を比較する際に、反射、反対称、推移を満たすことを保証します。
Ord: これは、PartialOrdが実装されている型に対してのみ実装できるトレイトです。Ordは、cmpメソッドを提供し、完全な順序付けを行うことができます。

反射律、反対称律、推移律という概念が分からないかもしれません。使えるようになることが目的なので、一旦具体例を見ていきましょう。まず、例として次のコードを考えてみます。

struct MyStruct {
    val: u32,
}

fn main() {
    let a = MyStruct { val: 2 };
    let b = MyStruct { val: 3 };
    println!("Is a less than b? {}", a < b);
}

このコードはコンパイルできません。次のエラーの通り、PartialOrdが実装されていないためです。

error[E0369]: binary operation `<` cannot be applied to type `MyStruct`
note: an implementation of `PartialOrd` might be missing for `MyStruct`

PartialOrdを実装して実行します。

#[derive(Debug, Clone, PartialOrd)]
struct MyStruct {
    val: u32,
}

//以下略

まだコンパイルできません。次のエラーが出てきました。

 = help: the trait `PartialEq` is not implemented for `MyStruct`
note: required by a bound in `PartialOrd`

どうやらPartialOrdを実装するためにはPartialEqも実装する必要があるようです。PartialEqを実装してみます。

#[derive(Debug, Clone, PartialOrd, PartialEq)]
struct MyStruct {
    val: u32,
}
fn main() {
    let a = MyStruct { val: 2 };
    let b = MyStruct { val: 3 };
    println!("Is a less than b? {}", a < b);
}

うまく実行できました。特にエラーなく、a、bの大小を判定できています。これだけ見ると「Ordはいつ使うんだ...?」という気持ちになります。

Eqはソートやコレクション型の比較の際に使われるものでした。同様に、Ordもソートやコレクション型の比較に使われます。例えば`単純にソートを行う次のコードを考えてみます。

#[derive(Clone, Debug, PartialOrd, PartialEq)]
struct MyStruct {
    val: u32,
}

fn main() {
    let mut v = vec![
        MyStruct { val: 2 },
        MyStruct { val: 3 },
        MyStruct { val: 1 },
    ];
    v.sort();
    println!("Sorted: {:?}", v); 
}

このコードはコンパイルできません。以下のエラーが出てきました。

error[E0277]: the trait bound `MyStruct: Ord` is not satisfied

どうやらsortではOrdトレイトを使用するため、これがない場合は正しくソートができないようです。Ordを実装しましょう。

#[derive(Clone, Debug, PartialOrd, Ord, PartialEq)]
struct MyStruct {
    val: u32,
}
// 以下省略

まだコンパイルできません。次のエラーが出てきました。

error[E0277]: the trait bound `MyStruct: Eq` is not satisfied
note: required by a bound in `Ord`

PartialOrdがPartialEqを必要としていたのと同様に、OrdもEqを必要としているようです。Eqを実装してみます。

#[derive(Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
struct MyStruct {
    val: u32,
}
fn main() {
    let mut v = vec![
        MyStruct { val: 2 },
        MyStruct { val: 3 },
        MyStruct { val: 1 },
    ];
    v.sort();
    println!("Sorted: {:?}", v); // Sorted: [MyStruct { val: 1 }, MyStruct { val: 2 }, MyStruct { val: 3 }]
}

うまく動きました。OrdにはEqが必要であることと、PartialOrdとOrdを実装することで、ソートができることが分かりました。

最初に

Ordは、PartialOrdが実装されている型に対してのみ実装できます。

と書いたため、これについても確認しておきます。上のコードからPartialOrdを削除します。

#[derive(Ord, PartialEq, Eq, Ord)]
struct MyStruct {
    val: u32,
}
// 以下省略

実行してみると次のエラー文が出てきます。予想通りOrdがPartialOrdを要求しています。完全に予想通りで嬉しいですね。

error[E0277]: can't compare `MyStruct` with `MyStruct`
 --> src/bin/c.rs:1:28
  |
1 | #[derive(Clone, Debug, Eq, Ord, PartialEq)]
  |                            ^^^ no implementation for `MyStruct < MyStruct` and `MyStruct > MyStruct`
  |
  = help: the trait `PartialOrd` is not implemented for `MyStruct`
note: required by a bound in `Ord`

ここまではderiveで付与してきましたが、自分で実装することも出来ます。例えば次の通りです。

#[derive(Debug, Clone)]
struct Pos {
    x: u32,
    y: u32,
}

impl PartialEq for Pos {
    fn eq(&self, other: &Self) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl Eq for Pos {}

impl PartialOrd for Pos {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Pos {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.y
            .cmp(&other.y)
            .then_with(|| self.x.cmp(&other.x))
    }
}

fn main() {
    let pos1 = Pos { x: 1, y: 2 };
    let pos2 = Pos { x: 1, y: 4 };
    let pos3 = Pos { x: 2, y: 4 };
    assert!(pos1 <= pos2);
    assert!(pos1 < pos3);
}

ここまでの例から使用にあたっては次のことが言えそうです。

単に値の大小を比較したいならPartialOrd
さらにソートやコレクション型を使うならば追加でOrd

を実装すればよさそうです。この節のタイトルはPartialOrd vs Ordですが、そもそも対立するものではありませんでした。自分で実装する際に、PartialEqは帰り値がboolであるのに対し、PartialOrdはOption<Ordering>であるなど、まだ分からないところがあります。次の節でそれについても触れていきます。

Partial Ord

先の節では、PartialOrdについて次のように説明しました。

PartialOrd: これは、2つの値を比較し、その大小関係を判定するためのトレイトです。<、>、<=、>=演算子をオーバーロードすることで、2つの値の大小を比較する際に、反射、反対称、推移を満たすことを保証します。

この説明ではいまいち分かりにくいかもしれません。公式ドキュメントを参考に、もう少し詳しく見ていきます

std::cmp::PartialOrd

PartiralOrdは、lt(less than, <)、le(less than or equal to, <=)、gt(greater than, >)、ge(greater than or equal to, >=)の4つを、それぞれ <、<=、>、>=で呼び出します。これらは、互いに、またPartialEqと一貫している必要があります。つまり、以下の条件を満たす必要があります

a == b if and only if partial_cmp(a, b) == Some(Equal).
a < b if and only if partial_cmp(a, b) == Some(Less)
a > b if and only if partial_cmp(a, b) == Some(Greater)
a <= b if and only if a < b || a == b
a >= b if and only if a > b || a == b
a != b if and only if !(a == b).

これを見ると当たり前のことが書かれているような気がします。なぜこんなことを書いているかを理解するためにも、ここで半順序(partial order)について確認しておきましょう。（partial orderについても上の公式ドキュメント上にリンクが貼られています。数学を専攻していた人はもっと詳しく知っていそう。）

二項関係

二項関係という言葉を抑えないと、この後が厳しいため、まず二項関係を説明します。集合 $A$ と $B$ が与えられた時に、その直積 $A\timesB$ の部分集合である $R\subset A×B$ を考えます。ここで $a\in A$ , $b \in B$ について $(a,b)\in R$ であるとき、 $a$ と $b$ は二項関係 $R$ にあると言います。（厳密な書き方は違うかもしれません。間違ってたら許して。）

このように書かれると全く分からない人もいるかもしれません。具体例として自然数の集合 $N$ を考えます。 $n \in N$ について、 $(n,n)$ は $=$ の関係が成り立ちます。 $n$ と $n$ は二項関係 $R$ にあるといえて、この時 $R$ は等号を表します。

さて、二項関係は次のような性質をもつことがあります。

反射性: 任意の $a$ について、 $(a,a)\in R$
対称性: 任意の $a$ , $b$ について、 $(a,b)\in R$ ならば、 $(b,a) \in R$
反対称性：任意の $a$ , $b$ について、 $(a,b)\in R$ かつ $(b,a) \in R$ ならば、 $a=b$
推移性：任意の $a,b,c$ について $(a,b)\in R$ かつ $(b,c)\in R$ ならば、 $(a,c) \in R$

例えば自然数の集合 $N$ での関係 $<$ について考えます。 $<$ は反射性を持ちません（n<nではないため）。一方で関係 $<=$ について考えると、反射性や反対称性、推移性を持つことが分かります。

「すうがくすうがくしてて難しい！！」という人に向けて次のような例を考えてみます。あるクラスの生徒たちが互いに友達関係にあると考えます。この場合、二項関係 $R$ はクラス内の生徒の組み合わせについての友情関係を示します。

ここで、 $A$ をクラス内の生徒全体の集合として、 $R$ を友情関係とします。 $R$ の要素は $(a,b)$ という形を取ります。 $(a,b)$ が $R$ に含まれることは、生徒 $a$ と生徒 $b$ が友達であることを意味します。

このとき、友情関係 $R$ は次の特性を持ちます。

反射性: 任意の生徒 $a$ について、その人自身との友情関係は存在します。つまり $(a,a)$ が $R$ に含まれます。
対称性：生徒 $a$ と生徒 $b$ が友達関係にあるならば、生徒 $b$ と生徒 $a$ も友達関係にあると言えます。つまり $(a,b)$ が $R$ に含まれるならば、 $(b,a)$ も $R$ に含まれます。
推移性：生徒 $a$ と生徒 $b$ が友達関係にあり。生徒 $b$ と生徒 $c$ も友達関係にあるならば、生徒 $a$ と生徒 $c$ も友達関係にあります（多分）。つまり $(a,b), (b,c)$ が $R$ に含まれるならば、 $(a,c)$ も $R$ に含まれます。

半順序

集合 $X$ の二項関係 $R$ が次の3つを満たすとき、 $R$ を $X$ の半順序と呼びます。

反射
反対称
推移

PartialOrd

整数などの集合に対して、 $<=$ は半順序です。そのため、 $<=$ を比較関数として使うことはかなり筋が良い感じがします。つまり $<=$ は、比較した際に、 $a<=b$ であるかそうでないかが分かる便利な二項関係であると言えます。そしてPartialOrdトレイトは実際にこれを行うトレイトでした。（参照：この記事のPartialOrdについての最初の6個の式。）

よくよく考えると、 $a<=b$ であるかそうでないかが分かるというのは、比較ができないペアの存在も許容します。PartialOrdを自分で実装するコードにおいて、返り値がOption<Ordering>だったのはそのような理由からです。

Ord

OrdはPartialOrdを実装している型に対してのみ実装できるトレイトでした。Ordは完全な順序付け（全順序）を行うことができます。完全な順序付けとは、任意の2つの要素に対して、その大小関係が決定できることを意味します。つまり、任意の2つの元 $a,b$ に対して、その大小関係が決定できます。Ordのこの性質から、自分で実装する際には、返り値の型がOrderingであることが分かります。

Ordを実装する際には、PartialOrdとEqが必要であることが分かりました。これは、完全な順序付けを行うためには、大小関係だけでなく等価性も考慮する必要があるためです。Ordを実装することで、ソートやコレクション型の比較を行うことができます。

また、Rustのf64はソートをする際に一工夫が必要です。f64はNaNを持つことができるため、大小関係を比較する際にはNaNを考慮する必要があります。Nanについては大小比較できないためOrdが実装されていません。そのため、単純なソートをすることができませんでした。

まとめ

PartialOrdとOrdは、Rustにおいて値の大小関係を扱うためのトレイトです。
PartialOrdは、半順序を考えます。
Ordは、PartialOrdが実装されている型に対してのみ実装できます。Ordは全順序であり、任意の2つの値について大小関係が決定できます。
Ordを実装することで、ソートやコレクション型の比較を行うことができます。浮動小数点数型のf64は、NaNの存在によりOrdが実装されていません。そのため、単純なソートを行う際には別の処理が必要になります。

このように、PartialOrdとOrdを適切に使い分けることで、Rustにおいて値の大小関係を扱うことができます。これらのトレイトの理解は、コレクション型の操作やソートなどで重要になります。