Namaran

Code daily. Without assist.

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)) が返ります。