[Rust] スターリンソートと PartialOrd

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる</p>&mdash; やんぎん (@4116You) <a href="https://twitter.com/4116You/status/1155619860027547648?ref_src=twsrc%5Etfw">2019年7月28日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# スターリンソートの実装

スターリンソートの実装がどんどん出てきています ([Haskell](https://qiita.com//MeilCli/items/721526d716851e92192a), [C#他](https://qiita.com/MeilCli/items/721526d716851e92192a)) がまだ Rust はないようなので, 睡眠導入剤代わりに書きました. [追記] 書いたとき寝ぼけてたのでコード修正 (2019-07-31). [追記2] `Copy` をつければより Rust らしく書けたので差し替えます. [`scan` って便利ですね](https://qiita.com/lo48576/items/34887794c146042aebf1). (2019-08-01)

```rust
fn stalin_sort<T: PartialOrd+Copy>(vec: &mut Vec<T>) {
    *vec = vec.iter().scan(vec[0], |prev, x| { 
        if *prev <= *x { *prev = *x; }
        Some(( *x, *prev <= *x ))
    }).filter_map(|(x,r)| if r { Some(x) } else { None }).collect();
}
```

驚くべきことに, 本来ソートは `Ord` にしか導入できない概念ですが, スターリンソートは `PartialOrd` に対しても実行することができます. 


# `Ord` と `PartialOrd`

良い機会なので `Ord` と `PartialOrd` について備忘録を兼ねてまとめておきます. 要は [jawp](https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88) とか集合論の教科書を読んでもらえばそれで良いのですが.

集合 $X$ が与えられたとき, その直積 $X \times X$ の部分集合 $R \subset X \times X$ のことを $X$ 上の __二項関係__ と呼び, $x$, $y \in X$ が $(x, y ) \in R$ を満たすことを $$x R y$$ と表記します. 例えば二項関係 $R = \\{ ( x, x ) | x \in X \\}$ は等号を表します.

集合 $X$ の二項関係 $O$ が次の条件を満足するとき, $O$ を $X$ の __半順序__ (partial order), 組 $( X, O )$ を 半順序集合 (partially orderd set, poset) と呼びます.

* 任意の $x \in X$ について $x O x$. (反射律)
* $x O y$ かつ $y O z$ ならば $x O z$. (推移律)
* $x O y$ かつ $y O x$ ならば $x = y$. (反対称律)

さらに, 上の 3 条件に加えて次の条件もが成り立つとき, $O$ を $X$ の __全順序__ (total order) または単に順序, 組 $( X, O )$ を全順序集合 (totally orderd set) と呼びます.

* 任意の $x$, $y \in X$ について $x O y$ か $y O x$ の少なくとも一方が成立する.

通常, 半順序または全順序を記号 $\leq$ により表します. また, $x \leq y$ かつ $x \neq y$ であることを $x < y$ と表します.

ここまでは純粋な数学でしたが, これらの概念を Rust ではトレイトによって表現します. まず先に全順序について見ておくと, `Ord` トレイトは次のような定義となっています.

```rust
trait Ord: Eq + PartialOrd<Self> {
    fn cmp(&self, other: &Self) -> Ordering;
}
```

ここに `Ordering` は enum (`std::cmp::Ordering`) で, 以下のように定義されます.

```rust
enum Ordering {
    Less,
    Equal,
    Greater,
}
```

つまり同じ型のふたつのインスタンスについて, 比較関数を呼ぶとより大きいか等しいか小さいかが確定するものが `Ord` だ, という訳です. `Ord` トレイトは `.max()` メソッドと `.min()` メソッドを提供します.

一方, 半順序を表す `PartialOrd` トレイトですが, これは比較関数を呼び出したときに $x \leq y$ が成立するかそうでないか, が確定するようなものでした (そもそも二項関係は $( x , y ) \in R$ が成り立つこととして定義されたことを思い出しましょう). 従って, 大きいとも小さいとも判断できない「比較不能」という元の組が存在し得ます. これは Rust では `Option<Ordering>` として表現できますから, `PartialOrd` の定義は次のようなものになります.

```rust
trait PartialOrd<Rhs = Self>: PartialEq<Rhs>
where Rhs: ?Sized, 
{
    fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
}
```

さて, 数値を表す Rust のプリミティブ型はすべて `PartialOrd` です. 浮動小数点数 (`f32` と `f64`) を除くと `Ord` でもあります. 浮動小数点数には大小比較のできない NaN が含まれますから, `Ord` にはできない訳です. 他に全順序ではなく半順序が必要なシチュエーションとしては, 集合の包含関係, 木構造におけるノードの相対的な位置関係, などがあります.

ここまで来ると, スターリンソートがなぜ `PartialOrd` に対しても適用できたのかが明らかです. 例として木構造で考えると, 異なる枝に乗っているノードは明らかに比較不能ですからそれをソートすることは本来できません. しかしスターリンソートでは異なる枝に乗っているノードは粛清されますから, このような問題は生じないのです. 同じ枝に乗っているノードならすべて残るとも言っていませんが...