# Traits with generic references & associated types

My dream is this: I want to have traits `AlgebraAdd<A,B,Output=C>` etc. that mirror the standard operations, but where `&self` is some carrier/domain/"context" type which performs the algebraic operation with additional information that the "element" types might not have access to. (For example element types might be `rug::Integer` but the "algebra" might have context like a modulus that should be applied to all values).

So I naively set out and define:

``````pub trait AlgebraAdd<T,U> {
type Output;
fn algebra_add(&self, a: T, b: U) -> Self::Output;
}
pub trait AlgebraRem<T,U> {
type Output;
fn algebra_rem(&self, a: T, b: U) -> Self::Output;
}
``````

I might want to start making a naive quotient ring that works over any base ring that has `AlgebraRem`.

``````pub struct NaiveQuotient<A,M> {
domain: A,
modulus: M,
}
``````

(To make this concrete, the base ring might for example be univariate polynomials over the integers -- `Z[X]` -- so `A` might be `UnivariatePolynomials<K>` and `M` might be some specific polynomial in the form of `Vec<K>`.)

Now, basically what I want to have is this super-generic definition of addition on `NaiveQuotient<A,M>`:

``````impl<A,L,R,M,T> // Is it OK to have T only appear on the right-hand side of later type class constraints?
for NaiveQuotient<A,M>
where
A: AlgebraAdd<L,R,Output=T> + AlgebraRem<T,???> // <- I've tried for<'a> AlgebraRem<T,&'a M> but then how do I refer to its ::Output?
{
type Output = ???; // anything like <A as for<'a> ..>::Output doesn't parse.
fn algebra_add(&self, a: L, b: R) -> Self::Output {
self.domain.algebra_rem(r, &self.modulus) // <- most of my problems stem from wanting to pass this as a reference.
}
}
``````

(In general, for most of these types, I want to have at least `AlgebraBinaryOp<T,&T,Output=T>` or something similar.)

The introduction of `&self.modulus` (i.e. `&M`) seems to force me to introduce lifetimes, which is the first thing that confuses me. The `AlgebraRem` trait is defined in terms of generic parameters `<T,U>` (where `U=&M` just "happens" to be a reference here) -- how could there ever be an issue of worrying about the "lifetime" of `U`? What I want to say is that `A` fulfills the trait `AlgebraRem<T,&M>` where `&M` will "obviously" outlive my usage of the trait (i.e. the call to `AlgebraRem::algebra_rem()`) so the compiler shouldn't have to worry about it?

When I try to tell the compiler to not worry about it with `for<'a> AlgebraRem<T,&'a M>` I couldn't figure out how to refer to this type class' associated `Output` type, since now it's a family of types, not just one?

I might just be super confused. Any sort of input on where I'm going wrong or how to implement this would be appreciated.

Or even links to libraries that have already done this sort of stuff before.

The higher-rank trait bound `A: for<'a> AlgebraRem<T, &'a M>` is indeed the way to ask for an implementation that covers some "arbitrarily short" lifetime existing only inside the body of `algebra_add`, but as you've noticed, this doesn't play well with associated types, because there's no way of naming the specific short lifetime used to determine `Output`. The only way I can think of to get around this is to move the borrow into the signature of `algebra_rem`, so the compiler can see that the lifetime of that borrow can't influence `Output`:

``````pub trait AlgebraRem<T, U> {
type Output;
fn algebra_rem(&self, a: T, b: &U) -> Self::Output;
}
``````

I don't know if that conflicts with something else you want to do with `AlgebraRem`.

1 Like

It's fine to add "extra" type parameters like `T` to an `impl`, as long as they are fully determined by the other parameters. This compiles:

``````pub trait AlgebraAdd<T, U> {
type Output;
fn algebra_add(&self, a: T, b: U) -> Self::Output;
}
pub trait AlgebraRem<T, U> {
type Output;
fn algebra_rem(&self, a: T, b: U) -> Self::Output;
}

pub struct NaiveQuotient<A, M> {
domain: A,
modulus: M,
}

impl<A, L, R, M, T, U> AlgebraAdd<L, R> for NaiveQuotient<A, M>
where
for<'a> A: AlgebraAdd<L, R, Output = T> + AlgebraRem<T, &'a M, Output = U>,
{
type Output = U; // anything like <A as for<'a> ..>::Output doesn't parse.
fn algebra_add(&self, a: L, b: R) -> Self::Output {
self.domain.algebra_rem(r, &self.modulus) // <- most of my problems stem from wanting to pass this as a reference.
}
}
``````

However, I wonder if you're writing the code you intend to write, given

There really is no situation in which the compiler will accept "this lifetime works; don't worry about it". The compiler, not you, is the one that actually picks lifetimes, so it has to know what the relationships actually are in order to do that. The borrow of `self.modulus` doesn't "obviously" outlive anything - it doesn't have to have any particular lifetime, unless you want to link it with a lifetime of `Self::Output`, which requires (at least) GATs. I can make that compile, too, but only with a `M: 'static` bound which is... probably? not what you want?

3 Likes

Thanks for the replies!

OK, I think I see my misunderstanding:

I was thinking of the type variables like this: given a generic trait that only works on a blank type `U`, with no lifetime or constraint (`AsRef`, `Borrow`, `Copy`, etc.), there was no way for that trait to actually extract or store a reference to `U` (barring any unsafe stuff?), thus it will always be "safe" to pass `U=&T` because the trait can only interact with a blank type `U` in a generic way. (Like how in Haskell there's really one possible implementation for `foo :: X->X` and that is `foo x = x`.)

But this is obviously wrong because there's nothing stopping an impl of that trait to say `U: Borrow<X>` and thus extract a reference it can store?

So a follow-up question: is there a way to achieve or express what I was originally thinking in Rust? E.g. `pub trait Foo<X> where X: NoWayForAnyImplToStoreAReferenceToThis { .. }`? To the point where the compiler would see `Foo<&T>` and be OK with it so long as this `T` outlives any call to `Foo`'s associated functions? Or is that an insane question?

Yeah, I ideally want the `AlgebraXXXXX<L,R>` etc traits to be completely generic, because for some types it might be more efficient for the implement to take ownership of both arguments, in other cases both LHS and RHS might be references.

Yes! That's actually what I figured out / ended up doing after a couple of hours. Although I'm getting somewhat worried about the number of type variables and if the trick of adding more of them will continue to work when I start to implement generic algorithms (e.g. part of my dream is a default `GCD(x,y)` that magically works for univariate polynomials, Euclidean domains, element-wise on vectors over such, etc).

That's mostly correct, I think, but I'm going to take issue with some of it because I'm not clear on what you mean by "store" and "extract".

Let's take `std::ops::Add` as a simpler example:

``````trait Add<Rhs> { /* in std, Rhs defaults to Self but that's not relevant */
type Output;
fn add(self, rhs: Rhs) -> Self::Output;
}
``````

We could write a function like this:

``````fn add_ref<'b, A, B>(a: A, b: &'b B) -> <A as Add<&'b B>>::Output
where
{
a + b
}
``````

This signature is in a sense "maximally generic", because it accepts any `'b` from the caller and makes no guarantees about what `Output` is. But this does mean that `Output` can contain `'b`; for instance, someone could implement `Add` like

``````impl<'rhs> Add<&'rhs Foo> for Foo {
type Output = (Foo, &'rhs Foo);
fn add(self, rhs: &'rhs Foo) -> Self::Output {
(self, rhs)
}
}
``````

Note that to write this I didn't need to make any assumptions about `Foo` - it doesn't have any `Borrow` or `AsRef` bounds or anything like that; just the fact that `Rhs` is a reference is enough for an `impl` to make use of that fact in its associated items. An `impl` (post monomorphization) always knows the concrete types of `Self` and all type parameters.

Now, if that's not what you want for `add_ref`, you can hoist the output type to a type parameter, and push the choice of `'b` into `add_ref` itself:

``````fn add_ref2<A, B, O>(a: A, b: &B) -> O
where
for<'b> A: Add<&'b B, Output = O>,
{
a + b
}
``````

This works for the same reason the previous version works: generics are chosen by the caller. So while the original `add_ref` had the caller choosing `'b` and having to deal with whatever `Output` type that gave, with `add_ref2` the caller chooses `O` and `add_ref2` itself has freedom to pick `'b` as long as it satisfies `A: Add<&'b B, Output = O>` (which is all lifetimes `'b`, because of the bound, so the caller's "choice" of `O` is actually fully determined by `A` and `B`).

Note that `add_ref2` is less generic than `add_ref`, because it's "easier" for a type to implement `Add<&'some_specific_lifetime B>` than `for<'any_old_lifetime> Add<&'any_old_lifetime B>`. `add_ref2` can therefore call `add_ref`, but not the other way around. The tradeoff for this lack of genericity is a stronger guarantee: the `Output` (return type) is known not to depend on `add_ref2`'s choice of `'b`.

Both `add_ref` and `add_ref2` are sensible function signatures that have their uses. One is not better than the other; it just depends on what you intend to do with them. There is an inherent tradeoff between genericity and guarantees; if you want to be maximally generic, you have to make do with guaranteeing next to nothing, like `add_ref` has to make do with whatever `Output` type it gets from choosing `'b`, `A` and `B`.

Perhaps I'm rambling a bit. Are we on the same page so far?

Well... yes and no. If you don't want the trait `impl` to know what the type parameter is... just don't parameterize the trait at all:

``````trait Add {
type Output;
fn add<Rhs>(self, rhs: Rhs) -> Self::Output;
}
``````

The obvious problem with this trait is that it's not possible to implement usefully, because no `impl` knows the concrete type of `Rhs` so you can't do anything interesting with it. The best you can do is delegate to another trait:

``````trait Add {
type Output;
}

type Output;
fn add(self, lhs: Lhs) -> Self::Output;
}
``````

Now you can use `Add` as a generic bound with an `Output` that doesn't depend on the choice of `Rhs`, but when you go to write `add_ref3`, well, it doesn't help much.

``````fn add_ref3<'b, A, B>(a: A, b: &'b B) -> A::Output
where
&'b B: AddTo<A, Output = A::Output> // hmm...
{
}
``````

You now have a guarantee that `A::Output` doesn't depend on the lifetime chosen for `&B`, but you still have to qualify that in a `where` clause anyway to guarantee that you can actually call `add`. So there is not an apparent advantage to doing this over the regular `Add<Rhs>` trait (that is, in the case where `B` is passed in; if `add_ref3` can choose `B`, this has the same effect for a type parameter as `add_ref2` had for a lifetime parameter).

2 Likes

Thank you so much for the detailed answers!

Right, so if my understanding is correct, a lot of the prickly stuff I'm having issues with stem from the fact that I am using associated types (and returning them)?

As for the `Output` type: the only reason I have it at all is due to a few rare edge cases that can fail, and where `Output=Option<T>` (or `Result`) instead of `Output=T`. Those are the only two types of `Output` I intend to use, either a plain (owned) type `T` or failure-or-`T`. (However (a) for most traits there is no failure condition, so it doesn't make sense to just fix it to `Option<T>`, and (b) all traits might have a failure condition (depending on parameters on `Self`), so I can't simplify by fixing it to `T` for certain traits.)

Is there a way to constrain implementations of associated types, or a way to tell Rust that a given associated type will never require a lifetime?

One thing I am considering is 2x the number of traits, like:

``````pub trait Algebra {
type Element;
}
fn algebra_add(&self, T, U) -> Self::Element;
}
fn algebra_add(&self, T, U) -> Option<Self::Element>;
}
``````

No, it's great. I'm an expert rambler:

If "exceptions" were a thing I would use that, because the only reason I have these associated types is for exceptional situations. (As far as I know catching panics come with very few guarantees in Rust, so it's not the True Way.) For example (trigger warning: math), in the "algebra" (context, `Self`, whatever) of point addition over an elliptic curve (`EllipticCurve<K>`): if the domain (`K`: another algebra) is a proper field, then there's really no need for any `Option` or `Result` in the output type for addition or scalar multiplication; it will always be well-defined. But if the domain is not a field (and this has use cases), even addition here might fail in a disastrous way, which I feel sort of forces my hand for the rest of the design. Or, simpler, how in any field the antisocial `0` ruins the interface for all the good non-zero law-abiding citizen-elements, forcing `inv(x)` and `div(x,y)` to return an `Option` or `Result`.

As for the `&T` vs `T` stuff: In most cares I don't want to concern myself in higher-level traits if types are references or owned (although ideally I'd like "at least one" operand to be owned), most of these traits simply defer down to sub-traits and in the end there's just a few base structs with implementations that cover all (or nearly all) `2^arity` cases of ref-or-owned, like `Add<&Self,Output=Self>, Add<Self,Output=Self>` for both `Self` and `&Self`, as well as a few `Add<i32,Output=Self>` etc for efficiency (`From<i32>::from()` might be expensive).

Perhaps there is a super obvious way to take care of situations like this in Rust already too, I'm pretty green. Because it strikes me like a problem that wouldn't be uncommon? Yet I've seen several libraries use macros to do a billion implementations to cover the combinations. The basic situation is: the types are potentially "big" and not `Copy`-able, so if I have `op(&T,&T)` I need to do at least one `clone()`, but if at least one of the arguments is owned, I can do some operations in-place on that one and avoid creating a temporary.

The constraint `Type: 'static` does that, but doesn't directly solve your problem of how to refer back to it from behind a reference elsewhere. But consider again @trentj's solution, slightly rewritten:

``````impl<A, L, R, M, T, RemOutput> AlgebraAdd<L, R> for NaiveQuotient<A, M>
where
A: AlgebraAdd<L, R, Output = T> +
for<'m> AlgebraRem<T, &'m M, Output = RemOutput>,
//     ^^^^^^^ Over any lifetime,   ^^^^^^^^^^^^^^^^^^ Output must unify
{
type Output = RemOutput; // <--- The unified Output
// Same thing (but more confusing IMO):
// type Output = <A as AlgebraRem<T, &'static M>>::Output;
fn algebra_add(&self, a: L, b: R) -> Self::Output {
self.domain.algebra_rem(r, &self.modulus)
}
}
``````

This... doesn't actually guarantee `Output: 'static`, even. Maybe `T` or `M` has a limited lifetime that infects `RemOutput`, for some selection of concrete types. But it does imply that `'m` doesn't infect `RemOutput`, since any matching type has to unify over all possible `'m`. And as far as I can tell, that's all you actually need. (Edit: Err, ignore my abuse of your traits where I implement div and not rem; the point is it works as intended even when `T` infects `RemOutput` with a lifetime.)

They then asked if you were sure you were writing what you meant, and the conversation has continued. But are you also sure this doesn't do what you want? I could be missing something, but it seems like the solution to your OP to me.

2 Likes

Another possibility:

``````pub trait AlgebraDiv<T,U>: Algebra {
type Error;
fn algebra_div(&self, T, U) -> Result<Self::Element, Self::Error>;
}

See the documentation for some discussion. You do still end up with `unwrap` or the like all over your infallible implementations.