Strugling with generics

Awesome! that did compile but then I am immediately stumbling on the impl

impl Submatrix<4, 4, f32> for Matrix<4, 4, f32>
where
    Self: Index<(usize, usize)>,
    Self::Result: Default + IndexMut<(usize, usize)>,
    <Self as Index<(usize, usize)>>::Output: Sized,
{
    type Result = Matrix<3, 3, f32>;
}

(Rust Playground)

with:

error[E0275]: overflow evaluating the requirement `<Matrix<4, 4, f32> as Submatrix<4, 4, f32>>::Result == _`
  --> src/lib.rs:71:1
   |
71 | impl Submatrix<4, 4, f32> for Matrix<4, 4, f32>
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: required for `Matrix<4, 4, f32>` to implement `Submatrix<4, 4, f32>`
  --> src/lib.rs:71:6
   |
71 | impl Submatrix<4, 4, f32> for Matrix<4, 4, f32>
   |      ^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^
...
74 |     Self::Result: Default + IndexMut<(usize, usize)>,
   |                   ------- unsatisfied trait bound introduced here

For more information about this error, try `rustc --explain E0275`.

You generally only need bounds on generics. [1] When you're working with concrete types, you don't have to state the bounds they implement in order to make use of them. That's why you can print a String without a where String: Display on your function, add literal integers, etc.

(And stating bounds that aren't true won't make them come true either.)


So I removed those bounds:

impl Submatrix<4, 4, f32> for Matrix<4, 4, f32> {
    type Result = Matrix<3, 3, f32>;
}

And that compiles, but the the bounds on the submatrix method doesn't compile if you try to use it:

76 |     m4.submatrix(0, 0)
   |        ^^^^^^^^^ the trait `for<'a> From<&'a f32>` is not implemented for `f32`
...

  --> src/lib.rs:55:13
   |
51 |     fn submatrix(&self, skiprow: usize, skipcol: usize) -> Self::Result
   |        --------- required by a bound in this
...
55 |             for<'a> From<&'a <Self as Index<(usize, usize)>>::Output>,
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Submatrix::submatrix`

I haven't deep-dived on understanding this code, but offhand it looks like your T are generally simple, Default-able, maybe even always Copy-able types. So I tweaked things a bit:

pub trait FromOtherOutput<Other: ?Sized>
where
    // No longer `for<'any> From<&Other::Output>`
    Self: From<Other::Output>,
    Other: Index<(usize, usize)>,
    // Added and we have to repeat it everywhere
    Other::Output: Clone,
{}
// ... replaced bounds everywhere...
// ... added `: Clone` where needed...
// ... and in `fn submatrix`:
                let tmp = &self[(r, c)];
                acc[(ir, ic)] = tmp.clone().into();

And now that compiles.


However, I don't think it's really an ideal construction. Now we have another bound that's not implied and has to be carried around everywhere. Also, is the real requirement that everything uses the same underlying T? Do you have a concrete use-case where you need to be this generic?

Because it feels like a lot of heavy machinery for maybe being able to get a 3x3 f32 submatrix out of a 4x4 f64 matrix without an intermediate 3x3 f64 submatrix, so far. (Or maybe a whole lot of machinery for nothing, if there's no demand for such operations.)

I.e., is there a reason this doesn't work for you?

pub trait Submatrix<const ROW: usize, const COL: usize, T>
where
    T: Clone,
    Self: Index<(usize, usize), Output = T>,
{
    type Result: Default + IndexMut<(usize, usize), Output = T>;
    fn submatrix(&self, skiprow: usize, skipcol: usize) -> Self::Result {
        iproduct!(0..ROW, 0..COL)
            .filter(|(r, c)| *r != skiprow && *c != skipcol)
            .enumerate()
            .fold(Self::Result::default(), |mut acc, (i, (r, c))| {
                let ir = i / (COL - 1);
                let ic = i % (COL - 1);
                acc[(ir, ic)] = self[(r, c)].clone();
                acc
            })
    }
}

  1. Though I think there's some niche cases where stating a bound on a concrete type influences method resolution. ↩︎

1 Like

Thank you! Thank you!
My first Impl did not have any bounds but it failed and I incorrectly assumed that it failed due to lack of bounds. After a lot of errors and searches I was hitting up loop bounds bugs and similar found issues where I started hitting the limits of my rust generics/traits knowledge and couldn't really find a workaround for the experimental generic_const_exprs bugs.

And yes I agree on the second part, just wasn't sure what the right way to do this and all of that was basically what I could sum up. I don't see/want an implicit conversion from f32 <=> f64, just that I was struggling to create a bound which would enforce Result to have the same Type, or create a predefined Result type like you did in the last example with type Result: Default + IndexMut<(usize, usize), Output = T>;

Thank you so much,

1 Like

This is awesome exactly what I wanted in the first place and expected from Rust (coming from C++ templates I was struggling):

pub trait Submatrix<const ROW: usize, const COL: usize, T>
where
    Self: Index<(usize, usize), Output = T>,
{
    type Result: Default + IndexMut<(usize, usize), Output = T>;

    fn submatrix(&self, skiprow: usize, skipcol: usize) -> Self::Result {
        iproduct!(0..ROW, 0..COL)
            .filter(|(r, c)| *r != skiprow && *c != skipcol)
            .enumerate()
            .fold(Self::Result::default(), |mut acc, (i, (r, c))| {
                let ir = i / (COL - 1);
                let ic = i % (COL - 1);
                acc[(ir, ic)] = self[(r, c)];
                acc
            })
    }
}

Got a bit further and now stuck with this:

pub trait Minor<const ROW: usize, const COL: usize, T>
where
    Self: Submatrix<ROW, COL, T> + Sized,
    T: Copy,
    <Self as Submatrix<ROW, COL, T>>::Result: Determinant<(ROW - 1), (COL - 1), T>,
{
    fn minor(self, row: usize, col: usize) -> f32 {
        let submatrix = self.submatrix(row, col);
        submatrix.determinant()
    }
}

playground

The syntax would be

<Self as Submatrix<ROW, COL, T>>::Result: Determinant<{ROW-1}, {COL-1}, T>,
//                                     Curly brackets ^     ^  ^     ^

But math in generic constants is an experimental feature.

That's entirely possible. Generic code often fails to compile due to missing bounds.

However, a concrete type doesn't need any explicit concrete bounds because both the types on the LHS and the traits on the RHS are known, and they can't influence whether your function compiles (under your feet and after the fact), because concrete types can't change (String is always String, u64 is always u64, and this won't ever change).

The whole point why Rust requires trait bounds when either the bounded type (LHS) or the bounding trait (RHS) is generic is that these involve type variables, which can stand in for a whole lot of types, they are not one concrete type. Thus, it's possible that a particular substitution isn't satisfied – after all, not every type implements every trait.

For example: given a type variable T, it's possible that T: Ord is not true, e.g. for T = f32. Or, given a type variable T, it's possible that str: AsRef<T> is not true, e.g. str: AsRef<u32> is not implemented.

Thus, in order to let the compiler know that you want to restrict types (either the LHS or the RHS) to a specific subset with specific capabilities, you have to tell the compiler via bounds/where clauses upfront.

Awesome this was it. :person_facepalming:

Most likely this has been answered somewhere but I can't find it (likely cause not really sure what to search)

But why does Rust force derived traits to re-declare all bounds? Isn't it causing code duplication and code rot where parent traits may remove bounds and child traits may miss it? Should a trait only have bounds required for the current trait, and compiler automatically inherits the parent traits?
It is also making recursive traits impossible as far as I can tell?

In my example I have Determinant -> Minor -> Cofactor -> Determinant loop, and bounds for each trait is a duplicate of other.

It's more flexible. Let's say we have

trait Foo<T: Clone> {}

// elsewhere
trait Bar<T: Clone>: Foo<T> {
    // implementation, utilizing T: Clone
}

Then this is not a breaking change:

// Removed `Clone` bound on `T`
trait Foo<T> {}

// elsewhere
trait Bar<T: Clone>: Foo<T> {
    // implementation, utilizing T: Clone
}

But if T: Clone were implied instead:

trait Foo<T: Clone> {}

// elsewhere
trait Bar<T>: Foo<T> {
    // implementation, utilizing T: Clone
    // (even though that's not declared here!)
}

Then removing the T: Clone bound on trait Foo would break the far-away trait Bar.

And in particular, an upstream crate could break a downstream crate, so implied bounds restricts the types of changes a library can make within a major Semver version, for example.


I recently wrote a bit more about this here, albeit in the context of bounds on structs, not traits.

1 Like

It's not clear what you mean by "recursive traits". However, type-level recursion is certainly possible in Rust. (If you search this forum for "type-level linked lost" or "hlist", you can see implementations of a typical example others and I have written.)


Furthermore, what you are talking about is not really "code duplication". A type variable is just like a regular variable, but at the type level (a regular variable can have any value at a given point at runtime; a type variable can stand in for any particular type at a specific point at compilation time). The bounds on the type variable are like the type of a regular value: they constrain what set of types it can stand in for, and what type-level operations you are allowed to perform on it (eg. what associated types it has).

Just like you can't omit type declarations from variables in function argument position, you can't omit these bounds from type variables that you re-declared for the purpose of using in a subtrait. The equivalent of what you want the compiler to do at the type level would be the following at the value level:

fn foo(x: u64) {
    bar(x);
}
// no type annotation on `x`:
// after all, it's only called from `foo`,
// so the type is "obvious"!
fn bar(x) {}

This is one of the "not gonna happen" territories of language design in Rust — it would actually result in spooky action at a distance if more callers were ever introduced. The type declaration in the bar function isn't redundant — it's making the type explicit, and it consequently makes the function more decoupled from its callers.


Also note that "code duplication" is really only a problem when it can cause inconsistency. Types and traits are fully checked by the compiler, so any perceived "redundancy" of trait bounds cannot accidentally result in code that is incorrect.

Sorry I should have specified that a trait should be required to declare all the bounds it uses, just not the bounds inherited but a bound trait too.

In your example if Foo was using Clone, currently Bar would also be required to declare Clone even if itself wasn't using it, and Foo is free to change its implementation, so bounds removal, but also new bounds implemented, neither would break Bar, it would automatically inherit the right bounds and missing bounds error messages would also be better by pointing to the correct trait where the bounds is being used.

I don't think I understand exactly what you propose. But although I said "utilizes Clone" for the sake of illustration, the compiler doesn't actually check this. Because the bound exists, it assumes you can utilize it and might as well be utilizing it, because (a) that's less fragile, but also (b) otherwise it would have to check all method bodies, etc, instead of upholding the contract at the API level.

There's a concept called #[refine] that allows one to declare "I'm less constrained" in one's implementations, [1] but I don't think that it's workable for trait bounds themselves. Every supertrait implementation would have to be revisited and recompiled as if there was no Clone bound to see if it qualifies in the example; effectively, it's an entirely different trait.

Speaking of an entirely different trait, sometimes you can do things like:

trait MoreGeneralFoo<T> {}
trait Foo<T: Clone> {}
impl<T: Clone, U: MoreGeneralFoo<T>> Foo<T> for U {}

// No `T: Clone` needed
trait Bar<T>: MoreGeneralFoo<T> {}

I got the impression you were using the bounds you wish you didn't have to repeat.

Adding a bound is a breaking change more generally, though I get the appeal within a single crate.


  1. once implemented and stabilized that is ↩︎

I suspect that It’s not about MutIndex v Index. When using fold, it can take ownership of the acc to accomplish what it needs. You can drop the mut in mut acc. When you do that it’s more an issue of self and acc types not matching. Which is what your design seems to require (trait or not). The issue is that self is not a Submatrix (if my memory serves) as is your acc. Perhaps create a layer between self and the data (matrix), that can operate such that you can both execute and host the transformation. I’m thinking something like Vec where the data is separate from the meta that manages it.

A pattern that may be of interest when dealing with data in different states/forms:

Matrix<T> with separate methods/impl for each Matrix<StateA>, Matrix<StateB> that point to inner values of type StateA, StateB etc..

Finally, traits are cool, but come at a high cost of being able to manage complex transformations. The error messages leave much to be desired here. It might be useful to get a solid understanding of the design without using traits other than what comes with Rust. Making your design generic from that point is much easier. In the end what seemed “the long, circuitous way” may be faster. Also, I’m starting to see way too much generic code in data processing, yes the individual values T, but the hosting structure… fn can be reused by way of FP-style functions with more concrete types, but that’s for another day :))

The Recursive issue I am facing is with the following recursive traits:

Determinant -> Cofactor -> Minor -> Determinant

I am most likely missing something about Rust to make this work, but the fact that each of these trait is dependent on each other the where bounds are essentially duplicates of each other just cause of dependence.

Taking a std example, the Zero trait has an dependency on Add even though it does not need to, but by definition it is. Now lets say I want to impl Zero trait for Point I cannot not unless I also define an incorrect Point + Point Add trait. On the other hand lets say I did so for another struct and created Zero trait with Add trait just to support Zero and maybe the std impl changes and removes the Add bounds on Zero the struct will continue to keep the Add trait even though its no longer needed.

Also maybe I am misunderstanding this line:

the compiler doesn't actually check this

but if I use something in my traits without a bound the compiler definitely doesn't let me.

num::Zero exists to define the additive identity value of a type, i.e. the value y that fulfils the equation x + y == x (for all x). Without a corresponding definition of + this is a nonsensical definition, which is why the Add bound is there.

If you just want an arbitrary placeholder value, that's what Default is for.


By the same logic, if there's no correct way to add points together, there is no additive identity value for a Point and thus no possible correct implementation of Zero.

1 Like

On the other hand, it feels like a lot of your trait bounds are not as semantically relevant, and are only there to support the implementation. You might be better served by writing blanket implementations instead of overridable defaults in many cases, for example:

That is very Neat, had seen this style of implementations but wasn't really sure why do it this way vs doing it straight in trait but your example makes it very clear. Thank you.

One noob question is does this enable the traits for any type which has the same generics params?
Slightly contrived example but lets says a struct table<100,10,String> get the same traits automatically?

Yes, every type that meets the conditions in the impl<T> SomeTrait for T where ... {} block has the trait implemented, even if that type is defined in another crate.

The biggest downside to this approach is that the implementation is not overridable— Every type that meets the listed requirements must use this implementation, and cannot implement a possibly-more-efficient one. Also, coherence rules sometimes make it hard to implement the traits for other types which aren't covered by the blanket implementation.

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.