Operations parametrized by an interface

code review
1

Hi,
I'm learning Rust and would like to know the best way to write generic algorithms on types the library does not own but that are required to satisfy a certain trait. To make things more concrete, let's consider the simple example of a monoid (T,+) on which I want to implement T × ℕ → T: (u,n) ↦ u·n. If the library defines the trait Monoid, then an external program wanting to use it on a concrete type, say [f64; 2] must implement Monoid on [f62: 2] which it can't do because of the orphan rule. In this case, the manual recommends to wrap the target type but this seems subpar to me because it hinders the collaboration with other packages (one may want, say, to apply a function f: fn([f64;2]) → [f64; 2] from another crate to each element of a Vec<[f64; 2]> and converting back and forth from Wrapped([f64; 2]) to [f64; 2] will quickly become painful). Using associated types, I could find the following solution. The library code reads:

trait Monoid {
    type T;
    fn zero() -> Self::T;
    fn add(x: Self::T, y: Self::T) -> Self::T;
}

fn times<M>(x: M::T, n: usize) -> M::T
where M: Monoid, M::T: Copy { // Naive implementation.
    let mut s = M::zero();
    for _ in 1 ..= n { s = M::add(s, x) }
    s
}

and the user would write:

struct M;

impl Monoid for M {
    type T = [f64; 2];
    fn zero() -> [f64; 2] { [0., 0.] }
    fn add(x: [f64; 2], y: [f64; 2]) -> [f64; 2] { [x[0] + y[0], x[1] + y[1]] }
}

He then can use times::<M>(x, n) to call the specialized function. This works but has two drawbacks:

  • the generic types have to be written to all functions which is a lot of repetition;
  • precising the type with ::<M> is heavy (and a bit odd looking to me).

The following alternative fixes these. The library code:

trait Monoid {
    type T;
    fn zero() -> Self::T;
    fn add(x: Self::T, y: Self::T) -> Self::T;
}

struct MonoidAlgo<M>(std::marker::PhantomData<M>);

impl<M> MonoidAlgo<M> where M: Monoid {
    fn times(x: M::T, n: usize) -> M::T
    where M::T: Copy { // Naive implementation.
        let mut s = M::zero();
        for _ in 1 ..= n { s = M::add(s, x) }
        s
    }
}

and the user writes:

struct MonoidArray2;

impl Monoid for MonoidArray2 {
    type T = [f64; 2];
    fn zero() -> [f64; 2] { [0., 0.] }
    fn add(x: [f64; 2], y: [f64; 2]) -> [f64; 2] {
        [x[0] + y[0], x[1] + y[1]]
    }
}

type M = MonoidAlgo<MonoidArray2>;

and can then use M::times(x, n) to call the specialized function.

Is this a reasonable way to achieve the desired goal in Rust? Any better solution?

Best regards,
Christophe

2

Given that there are many possible monoids that could apply to a single type, you want another type somewhere anyway to say which monoid it is.

So you could do something like

struct AdditionMonoid;
impl Monoid<i32> for AdditionMonoid {
    const IDENTITY: i32 = 0;
    fn binary(x: i32, y: i32) -> i32 { x + y }
}
// also for more types

and

struct MultiplicationMonoid;
impl Monoid<f64> for MultiplicationMonoid {
    const IDENTITY: f64 = 1.0;
    fn binary(x: f64, y: f64) -> f64 { x * y }
}
// also for more types
3 Likes
3

If I understand well, you suggest that the trait be:

trait Monoid<T> {
    const IDENTITY: T;
    fn binary(x: T, y: T) -> T;
}

But, then, how do I implement a generic times?

4

I understand that you don't want times to be part of Monoid because, well, that's no longer a monoid. But really, it's more Rustic to do so, and would solve some of your problems.

Example:

// Library
mod monoid {
    pub trait Monoid {
        type T;
        fn zero() -> Self::T;
        fn add(x: Self::T, y: Self::T) -> Self::T;
        fn times(x: Self::T, n: usize) -> Self::T where Self::T: Clone {
            todo!("naive implementation")
        }
    }
}

// Library consumer
struct M;

impl Monoid for M {
    type T = [f64; 2];
    fn zero() -> Self::T { [0., 0.] }
    fn add(x: Self::T, y: Self::T) -> Self::T { /* ... */ }
    // Optionally, an optimized version for this type
    fn times(x: Self::T, n: usize) -> Self::T {
        let n = n as f64;
        [ x[0] * n, x[1] * n ]
    }
}

// Utilizing it
let _ = M::times([3.0, 2.0], 7);
// As part of the trait, the pathing is the same for the other ops
let _ = M::add(M::zero(), [2.3, 4.5]);

Aside from "it's no longer a monoid", the main complaint I could imagine is the bound that we had to put on times in order to supply the default body (I used Clone). However,

  • Your free function also needs the bound (you used Copy)
  • The library implies something like a Copy bound in other ways
    • Like taking two parameters by value and returning one
    • And if I'm not using times, it doesn't seem to offer much else
    • [This last observation is too big for a bullet point, so see below]

If I want to use your library for both Copy and Clone types, I have to supply my own times function for the non-Copy types. But in order to make it useful in a generic context, I also have to definite it for Copy types -- I can only call one of your times or my times! So what I probably do in practice is

trait Times: Monoid {
    fn times(x: Self::T, n: usize) -> Self::T;
}

I can utilize your free function when implementing this if I choose too, but I still need to write the glue.

At this point you could argue that you should keep the free function and add a times function to the trait without the Clone/Copy bound -- then users of the library don't have to write their own subtrait. But then everyone has to supply the glue to call the free function when implementing the trait, because you can't (yet) have a default body based on a bound that doesn't apply universally. It's still an option -- you could supply a macro even -- but given all the other indicators (like taking things by value), it probably makes sense to just restrict the trait to Clone or Copy types.

(I chose Clone because you could wrap things in an Rc, say.)

2 Likes
5

Follow-up thought: You can actually have two traits to maintain both convenience and flexibility.

mod monoid {
    pub trait ClonableMonoid {
        type T: Clone; // <-- note bound
        fn zero() -> Self::T;
        fn add(x: Self::T, y: Self::T) -> Self::T;
        fn times(x: Self::T, n: usize) -> Self::T { // and default body
            todo!("naive implementation")
        }
    }

    pub trait Monoid {
        type T; // <-- note lack of bound
        fn zero() -> Self::T;
        fn add(x: Self::T, y: Self::T) -> Self::T;
        fn times(x: Self::T, n: usize) -> Self::T; // no default body
    }

    impl<U: ClonableMonoid> Monoid for U {
        // just defer everything to the ClonableMonoid impl
    }
}

Then consumers of the library can implement ClonableMonoid if Self::T: Clone, getting the benefit of the default times if desired but not losing the ability to override it. Consumers where Self::T is not Clone can just implement Monoid directly. Both end up with a Monoid implementation, which would be the bound used elsewhere.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.