"conflicting implementations for trait" when trying to be generic

Question

Background: I'm using the nalgebra library and I want to create a structure that represents a multivariate normal distribution. M is the type of the matrix, e.g. Mat4<f64>.

My current attempt looks like this:

use std::ops::Mul;
use std::marker::PhantomData;
use nalgebra::*;

#[allow(non_snake_case)]
pub struct Multivar𝒩<N, V, M: SquareMat<N, V>> {
    μ: V,
    Σ: M,
    marker: PhantomData<N>
}

impl<N, V, M> Mul<Multivar𝒩<N, V, M>> for M {
    type Output = Multivar𝒩<N, V, M>;
    fn mul(self, rhs: Multivar𝒩<N, V, M>) -> Multivar𝒩<N, V, M> {
        Multivar𝒩 {
            μ: self * rhs.μ,
            Σ: self * rhs.Σ * transpose(&self)
        }
    }
}

However, the compiler complains with:

error: type parameter `M` must be used as the type parameter for some local type (e.g. `MyStruct<T>`); only traits defined in the current crate can be implemented for a type parameter

and

error: conflicting implementations for trait `core::ops::Mul`

I don't believe this should be an error since I'm defining an implementation for a struct I have defined in this module. How should I fix this?

Answer 1

The problem with your code is that you have a coherence violation in it, and, very likely, any attempts to fix it would lead to new coherence violations.

Coherence rules in Rust are somewhat complex, however, they are based on one principle: you can implement "your" traits for arbitrary types and you can implement arbitrary traits for "your" types. It sounds simple, but it becomes complicated when type parameters come into picture - it turns out that there are more than one ways to define which types are "yours" and which are not.

In this particular case the error is in that you're implementing a foreign trait for a type parameter directly:

impl<N, V, M> Mul<Multivar𝒩<N, V, M>> for M

This directly violates the above principle - you can't implement traits you don't own for types you don't own (such implementations are called "orphan impls"). This is exactly what your first error is about.

The second error makes me think that you have more Mul implementations than you provided here; anyway, it is also a coherence violation. Typically such error is caused when you have intersections of sets of types applicable for two or more different implementations of a trait:

use std::fmt;

trait X {}

impl X for i32 {}
impl<T: fmt::Display> X for T {}

Here implementations are conflicting because they both are applicable for i32 because i32 implements fmt::Display.

In fact, it is difficult to tell what you want, so it is also difficult to give a satisfying answer. I tried to explain the reason for these errors above, hopefully it would help you to write trait implementations properly. If you're interested, you can find more in this blog post on orphan rules.