Blanket implementations of traits with generics

Question

I am practicing Rust by implementing matrix math and I'm running into a few snags. I defined the traits that I thought were relevant to a matrix.

trait Matrix<T> where T : num::Num  {
    fn dim(&self) -> (usize, usize);
    fn elem(&self, i : usize, j : usize) -> Option<& T>; 
    fn new_const(v: T, rows : usize, cols : usize) -> Self where T : Clone;

    fn same_dim<U>(&self, other: &U) -> bool where U : Matrix<T> {
        self.dim() == other.dim()
    }
}

I have a dumb implementation using Vec<Vec<T>>. I implemented all of the methods and tested them. They are all working. Now I want to simply add two matrices together. So without adding the row iterator that I know will be required and doing an add implementation that I know is going to be incorrect I put the following.

impl <T, U> Add for U where T: num::Num, U: Matrix<T> {
    type Output = U;

    fn add(self, _rhs: U) -> U {
        U::new_const(T::zero(), 5, 5)
    }
}

but I get

lib.rs:41:7: 41:8 error: the type parameter `T` is not constrained by the impl trait, self type, or predicates [E0207]
lib.rs:41 impl <T, U> Add for U where T: num::Num, U: Matrix<T> {
                ^
lib.rs:41:7: 41:8 help: run `rustc --explain E0207` to see a detailed explanation
error: aborting due to previous error
Could not compile `matrix`.
To learn more, run the command again with --verbose.
Compilation failed.

T does seem constrained to me. Can anyone point me in the right direction?

Answer 1

T isn't constrained by the information the compiler can see at the use-site of the implementation. By having trait Matrix<T>, a single type can be a matrix over multiple element types, that is, it's perfectly legal for someone to have both impl Matrix<u8> for Foo and impl Matrix<u16> for Foo in the same program. If this happens, then Foo + Foo (i.e. a use of the Add implementation) can't be sure which T to use: both T = u8 and T = u16 work.

I think the best way to solve this is to remove the T type parameter: a given type is only a matrix over one sort of element (even if it's generic), e.g. Vec<Vec<T>> is a matrix over T, nothing else. This is like Iterator: a given type can only yield one type of element.

In code, this looks like:

trait Matrix {
    type Elem: num::Num;

    fn dim(&self) -> (usize, usize);
    fn elem(&self, i: usize, j: usize) -> Option<&Self::Elem>;
    // ...
}

The Add implementation then becomes

impl<U> Add for U where U: Matrix {
    type Output = U;

    fn add(self, _rhs: U) -> U {
        U::new_const(U::Elem::zero(), 5, 5)
    }
}

However, this also doesn't work, as it hits coherence problems. The compiler can't be sure that this implementation of Add doesn't overlap with other implementations of Add, since one could implement Matrix for a type that already has an Add implementation in some way. One can work around this by making a wrapper type, and using the Matrix trait instead as a "backing storage" trait, i.e. it "just" controls the internal representation.

struct Matrix<T: Storage> {
    x: T
}
trait Storage { // renamed `Matrix` trait
    type Elem;
    fn dim(&self) -> (usize, usize);
    // ...
}

The Matrix type then becomes the place to add more methods and trait implementations etc.