じぶん advent calendar 2019, day 12 の記事です.
たとえば何気ないユークリッドの互除法
pub fn gcd(n: u32, m: u32) -> u32 { // Euclidean let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b != 0 { // いや,普通に再帰にすればよかったんですけど… let tmp = b; b = a % b; a = tmp; } a }
u32
に限ってるのが馬鹿らしいというか,u16
でも u64
でも i32
でもやること一緒なんだし,generic に書きたいな
fn gcd<T>(n: T, m: T) -> T { let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b != 0 { let tmp = b; b = a % b; a = tmp; } a }
where T: Integer
という気持ちです1.
Rust では足し算できるのは std::ops::Add
2, 剰余を取れるのは std::ops::Rem
(これもOutput
が必ずしももとの型と一致しない)
と細かく分けられているので,その辺を補うとだいぶエラーが減る
fn gcd<T>(n: T, m: T) -> T where T: std::cmp::PartialOrd + Copy, T: std::ops::Rem<Output = T>, { let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b != 0 { let tmp = b; b = a % b; a = tmp; } a }
…のだが,結局
error[E0308]: mismatched types --> src/main.rs:22:16 | 15 | fn gcd<T>(n: T, m: T) -> T | - this type parameter ... 22 | while b != 0 { | ^ expected type parameter `T`, found integer | = note: expected type parameter `T` found type `{integer}`
数値リテラルとの比較で怒られる.Haskell だと数値リテラル自身が Num a => a
みたいな型になるので(最強),できればリテラルのまま generic にしたいんだけど….
ドキュメンテーションを読むと型指定のない数値リテラルの型はこう決定されると書いてある:
- If an integer type can be uniquely determined from the surrounding program context, the unsuffixed integer literal has that type.
- If the program context under-constrains the type, it defaults to the signed 32-bit integer i32.
- If the program context over-constrains the type, it is considered a static type error.
のでどうもこのまま行くのは無理っぽい….
Into
むりやり into
を噛ませると一応動くものはできる:
pub fn gcd<T>(n: T, m: T) -> T where T: Ord + Copy, T: Into<i64>, T: Rem<Output = T>, { let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b.into() != 0 { let tmp = b; b = a % b; a = tmp; } a }
のだけどまあダメですね.要らん変換を挟んでるのがあれだし,i64
(でも何でも実装時に選んだ型)に変換できたら何でも使えてしまう.
trait?
「ぜろ」という値をもつ trait を設計してやればいい
fn gcd<T>(n: T, m: T) -> T where T: std::cmp::PartialOrd + Copy, T: std::ops::Rem<Output = T>, T: Zero, { let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b != T::zero() { let tmp = b; b = a % b; a = tmp; } a } trait Zero { fn zero() -> Self; } impl Zero for u32 { fn zero() -> Self { 0 } }
あとは Zero
を思いつく限りの整数型に実装してやればよい…….まあそこそこ……?
実際,Rust でこういうことするときはぜひ使うと良いという噂の num
ではこういうのが実装されている.
とはいえ Zero だからなんか意味のあるっぽい trait になったけど,3と比較(google.com)したいときとかどうするんですかねえ…
「GCDを計算できる」trait?
一旦整数から離れて, Generic というところに立ち返りましょう.とにかく generic な GCD を作りたい.Trait にしてしまいましょうか3
trait GCD { fn gcd(m: Self, n: Self) -> Self; } impl GCD for u32 { fn gcd(m: u32, n: u32) -> u32 { let (mut a, mut b) = if n > m { (n, m) } else { (m, n) }; while b != 0 { let tmp = b; b = a % b; a = tmp; } a } } // あと全部やる
ここでそもそもの「気持ち悪さ」の源が見えてきました. Generic な数値リテラルはないようだが,数値リテラルはどの数値型としても解釈してもらえる. つまり特定の型についての関数定義では,上記のコードがそのまま変更なく使えるということだ. にもかかわらず(コピーするだけなのに)自分で手を動かす必要があるなんて……
結局マクロへ
これを実行するならマクロという気がします. Rustacean たるものマクロを恐れるべからず.どっかで聞いたことがある気がする.
じつは先程の num に,gcd という関数が定義されています.こんなふうに使う
assert_eq!(6.gcd(&8), 2);
これの実装を見てみると,ずばり…
macro_rules! impl_integer_for_isize { ($T:ty, $test_mod:ident) => ( impl Integer for $T { // 中略 /// Calculates the Greatest Common Divisor (GCD) of the number and /// `other`. The result is always positive. #[inline] fn gcd(&self, other: &$T) -> $T { // Use Stein's algorithm let mut m = *self; let mut n = *other; // 展開された $T に合わせてちゃんと 0 の型が定まってくれる if m == 0 || n == 0 { return (m | n).abs() } // 後略
でこう
impl_integer_for_isize!(i8, test_integer_i8); impl_integer_for_isize!(i16, test_integer_i16); impl_integer_for_isize!(i32, test_integer_i32); impl_integer_for_isize!(i64, test_integer_i64); impl_integer_for_isize!(isize, test_integer_isize);
つまりまさにまるっとマクロに定義させているわけでした.
ここまでくれば,上の trait 使ったやつに生やすのはかんたん…なんだけど…ここまでするかなあ…関数で使いたかったのにメソッドになっちゃうし……….
結論: 気軽に project euler とかで使うぶんには多分場当たり的に定義しちゃうのが早い.本格的にはマクロが結構使いやすそうではある.