2026-11-08
monoid.rs
trait Monoid {
const EMPTY: Self;
fn combine(self, other: Self) -> Self;
}
impl Monoid for i32 {
const EMPTY: i32 = 0;
fn combine(self, other: i32) -> i32 {
self + other
}
}
impl Monoid for String {
const EMPTY: String = String::new();
fn combine(self, other: String) -> String {
self + &other
}
}
impl<A: Monoid, B: Monoid> Monoid for (A, B) {
}
fn concat_all<M: Monoid>(xs: Vec<M>) -> M {
}
トレイト Monoid は、2つの値を1つに結合する combine と、どの値と結合しても相手を変えない空の値 EMPTY を持ちます。2つの Monoid の組 (A, B) を、成分ごとに結合する Monoid にする実装と、xs の要素を先頭から順に結合した値を返す concat_all を書いてください。xs が空なら EMPTY を返します。
入力例 1
concat_all(vec![(1, "a".to_string()), (2, "b".to_string())])
出力例 1
(3, "ab")
入力例 2
concat_all(Vec::<(i32, String)>::new())
出力例 2
(0, "")
入力例 3
concat_all(vec![(1, (2, 3)), (10, (20, 30))])
出力例 3
(11, (22, 33))
Reference
Reference
trait Monoid {
const EMPTY: Self;
fn combine(self, other: Self) -> Self;
}
impl Monoid for i32 {
const EMPTY: i32 = 0;
fn combine(self, other: i32) -> i32 {
self + other
}
}
impl Monoid for String {
const EMPTY: String = String::new();
fn combine(self, other: String) -> String {
self + &other
}
}
impl<A: Monoid, B: Monoid> Monoid for (A, B) {
const EMPTY: Self = (A::EMPTY, B::EMPTY);
fn combine(self, other: Self) -> Self {
(self.0.combine(other.0), self.1.combine(other.1))
}
}
fn concat_all<M: Monoid>(xs: Vec<M>) -> M {
xs.into_iter().fold(M::EMPTY, M::combine)
}
組の空の値は、両方の成分の空の値を並べた (A::EMPTY, B::EMPTY) です。impl<A: Monoid, B: Monoid> の中では A と B が何の型かは決まっていませんが、境界から Monoid を実装していることは分かるので、関連定数 A::EMPTY を型引数から取り出せます。combine は self と other を値で受け取るので、self.0 や other.0 をそのまま成分の combine に渡して所有権ごと移せます。成分が String でも複製は要りません。concat_all は fold で、初期値を M::EMPTY に、各要素との結合を M::combine にします。メソッドは M::combine と書けば2引数の関数として渡せます。これは参考実装で、唯一の正解ではありません。
入力例1では、fold が (0, "") から始まり、(1, "a") と結合して (1, "a")、(2, "b") と結合して (3, "ab") になります。入力例2は要素が無いので、初期値の (0, "") がそのまま返ります。EMPTY を初期値にしておけば、空の場合を別に扱う必要はありません。入力例3の要素の型は (i32, (i32, i32)) です。内側の (i32, i32) も同じ impl で Monoid になるので、外側の組は B = (i32, i32) として同じ impl をもう一度使え、(1 + 10, (2 + 20, 3 + 30)) が返ります。