Rust: How to return a generic trait within a trait method, where the generic type is different?-CodePudding

I am pretty new to Rust, and I have a question that seems simple on the surface but I think is much more challenging than I thought (this is just for practice). The title might be worded badly, so I'll just explain the exact problem here:

I have a generic trait Sequence that looks something like this:

trait Sequence<T> {

    fn new() -> Self;
    fn singleton(x: T) -> Self;
    fn tabulate<F>(f: F, n: usize) -> Self
    where
        F: Fn(usize) -> T;
    fn nth(&self, i: usize) -> &T;
    fn length(&self) -> usize;
    fn reversed(&self) -> Self; // creates a new sequence that is reversed

    // hmmm... this doesn't compile
    fn map<F, U>(&self, f: F) -> Sequence<U> where F: Fn(&T) -> U;
    //                           ^^^^^^^^^^^ this is where the issue is

}

Ideally, I would like to define this as a wrapper around a Vec<T>, but I have it as a trait because I would also in the future like to wrap this around other generic collections.

So, the issue here that method called map. Ideally in the vector implementation, it would take the vector, apply the map function to every element, and return a new vector. However, I also want the ability to return a vector of a different type.

For example, if I did some_sequence.map(|x| x.to_string()) where some_sequence is a Sequence<i32>, I would expect a Sequence<String> as the return type.

I started looking into trait objects, but I couldn't find an explanation on how to return generic trait objects. I tried something like this:

fn map<F, U>(&self, f: F) -> Box<dyn Sequence<U>> where F: Fn(&T) -> U;

But then I think I would need to change the signatures of the other methods, which I would rather not do.

If there is a quick explanation, that would be much appreciated, but if not, where I can I read more about this type of problem? I am super new to dynamic dispatch as well, so if I just need to look more into that then I would like to know.

CodePudding user response：

This is a classic case for GATs.

Generic Associated Types, or GATs for short, were recently stabilized (in Rust 1.65.0). They allow you to parameterize an associated type with a generic parameter. In this case, you can have a Sequence<T> generic parameter that will allow you to go from a sequence to the same sequence with a different item type:

trait Sequence<T> {
    type Sequence<U>;

    fn new() -> Self;
    fn singleton(x: T) -> Self;
    fn tabulate<F>(f: F, n: usize) -> Self
    where
        F: Fn(usize) -> T;
    fn nth(&self, i: usize) -> &T;
    fn length(&self) -> usize;
    fn reversed(&self) -> Self; // creates a new sequence that is reversed

    fn map<F, U>(&self, f: F) -> Self::Sequence<U>
    where
        F: Fn(&T) -> U;
}

impl<T> Sequence<T> for Vec<T> {
    type Sequence<U> = Vec<U>;
    
    // ...
    
    fn map<F, U>(&self, f: F) -> Vec<U>
    where
        F: Fn(&T) -> U
    {
        self.iter().map(f).collect()
    }
}

If you are pedantic, you can define a SequenceFamily trait, so that you have the abstract concept of a sequence type without a generic parameter:

trait SequenceFamily {
    type Sequence<T>;
}

trait Sequence<T> {
    type Family: SequenceFamily;
    
    fn new() -> Self;
    fn singleton(x: T) -> Self;
    fn tabulate<F>(f: F, n: usize) -> Self
    where
        F: Fn(usize) -> T;
    fn nth(&self, i: usize) -> &T;
    fn length(&self) -> usize;
    fn reversed(&self) -> Self; // creates a new sequence that is reversed

    fn map<F, U>(&self, f: F) -> <Self::Family as SequenceFamily>::Sequence<U>
    where
        F: Fn(&T) -> U;
}

pub struct VecFamily;
impl SequenceFamily for VecFamily {
    type Sequence<T> = Vec<T>;
}

impl<T> Sequence<T> for Vec<T> {
    type Family = VecFamily;
    
    // ...
    
    fn map<F, U>(&self, f: F) -> Vec<U>
    where
        F: Fn(&T) -> U
    {
        self.iter().map(f).collect()
    }
}

CodePudding user response：

You need to make the whole return type a generic parameter:

trait Sequence<T> {

    fn new() -> Self;
    fn singleton(x: T) -> Self;
    fn tabulate<F>(f: F, n: usize) -> Self
    where
        F: Fn(usize) -> T;
    fn nth(&self, i: usize) -> &T;
    fn length(&self) -> usize;
    fn reversed(&self) -> Self; // creates a new sequence that is reversed

    fn map<F, O, U>(&self, f: F) -> O
    where
        F: Fn(&T) -> U,
        O: Sequence<U>;
}

This is essentially a way of achieving "return position impl Trait", which is currently not allowed in traits. In the future, you may be able to do something like this instead:

trait Sequence<T> {

    fn new() -> Self;
    fn singleton(x: T) -> Self;
    fn tabulate<F>(f: F, n: usize) -> Self
    where
        F: Fn(usize) -> T;
    fn nth(&self, i: usize) -> &T;
    fn length(&self) -> usize;
    fn reversed(&self) -> Self; // creates a new sequence that is reversed

    fn map<F, U>(&self, f: F) -> impl Sequence<U>
    where
        F: Fn(&T) -> U;
}