combine_n should do exponentation by squaring

[ExpHP]

frunk/src/semigroup.rs

Lines 90 to 101 in bdb8b0f

	/// Return this combined with itself `n` times.
	pub fn combine_n<T>(o: &T, times: u32) -> T
	where
	T: Semigroup + Clone,
	{
	let mut x = o.clone();
	// note: range is non-inclusive in the upper bound
	for _ in 1..times {
	x = o.combine(&x);
	}
	x
	}

I'm honestly surprised to see that this doesn't do exponentation by squaring; to me, that has always been the point of having a function like combine_n

N.B. The correctness of using exponentation by squaring is guaranteed by the law of associativity.

[ExpHP]

p.s. pseudocode for monoid (well, okay, this is more code than pseudo):

    pub fn combine_n(&self, mut exp: u64) -> Self {
        let mut acc = Self::identity();
        let mut base = self.clone();
        while exp > 0 {
            if (exp & 1) == 1 {
                acc = acc.combine(&base); // multiply by a power of two
            }
            base = base.combine(&base); // square for next power of two
            exp /= 2;
        }
        acc
    }

and the one for Semigroup is tricky to write out by hand, but IIRC it ultimately can be expressed in terms of the monoid on Option (but don't quote me on this; it needs tests)

// FIXME needs tests
pub fn combine_n_opt(x: &T, n: u64) -> Option<T>
where T: Clone + Semigroup,
{
    // note: &T and &Some(T) have the same representation so
    //      this first clone can be avoided with unsafe...
    monoid::combine_n(&Some(x.clone()), n)
}

// FIXME needs tests
pub fn combine_n(x: &T, n: u64) -> T
where T: Clone + Semigroup,
{
    combine_n_opt(x, n).expect("can't combine 0 copies in a semigroup!")
}

[lloydmeta]

Oh, this is a good idea. This is definitely a much better combine_n!