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