3

I plan to learn Rust this spring and after reading the book, I picked an algorithmic problem to implement to test myself. Right off the bat, I run into a problem that shows that I don't understand traits at all.

My project will be to compute range minimal queries with various techniques, and because I have multiple implementations of the same thing, I figured a trait was the way to go. What I need are the following operations: get the length of an underlying sequence, get the value at a given index, and find the first index with a minimal value. That is simple enough, but then I thought it would be nice if I could access elements using subscripting syntax, so I wanted the std::ops::Index<> trait as well.

This is what my trait looks like:

/// The type we use for indexing into our arrays.
type Idx = usize;
/// The type our arrays hold. 32-bit are enough for genomic data.
type Val = u32;

/// Range Minimum Query interface.
pub trait RMQArray: std::ops::Index<Idx, Output = Val> {
    /// Get the length of the underlying array.
    fn len(&self) -> Idx;
    /// Get the value at a specific index.
    fn val(&self, index: Idx) -> &Val;
    /// Get the index of the first minimal value in the range [i,j).
    fn rmq(&self, i: Idx, j: Idx) -> Idx;

    // Interface for Index<Idx, Output = Val>
    fn index(&self, index: Idx) -> &Val {
        self.val(index)
    }
}

The first three methods are what concrete implementations should provide, and the index method implements Index<Idx>.

However, I can only get this to work if every concrete implementation re-implements the index method to provide an Index<> implementation.

/// Implements RMQ by running through the [i,j) interval
/// and finding the index with the smallest value.
/// O(1) preprocessing and O(n) access.
pub struct BruteForceRMQ {
    values: Vec<u32>,
}

impl BruteForceRMQ {
    pub fn new(values: Vec<u32>) -> BruteForceRMQ {
        BruteForceRMQ { values }
    }
}

// Implementing the Index<> interface. This is redundant
// if I need it for each implementation of RMQArray.
impl std::ops::Index<Idx> for BruteForceRMQ {
    type Output = Val;
    fn index(&self, index: Idx) -> &Val {
        self.val(index)
    }
}

impl RMQArray for BruteForceRMQ {
    fn len(&self) -> Idx { ... }
    fn val(&self, index: Idx) -> &Val { ... }
    fn rmq(&self, i: Idx, j: Idx) -> Idx {... }
}

All my implementations, without exception, will implement exactly the same Index<> interface. They will all have Output = Val and the index() method will always delegate to val(), so implementing the Index<> trait for each of them is redundant.

I had thought that I could specialise Index<> in RMQArray, but I can't. Someone smarter than me probably can, but I haven't managed to figure it out.

I also tried coming up with something like a mixin, so I could get the functionality into the concrete implementations that way, but none of the tricks I know from other languages worked for me in Rust. It probably isn't the right way to do it anyway, but I don't know what the Rust-way is.

What is the right way to implement a new trait that specialises other traits, so I only have to implement the few methods my own trait needs from the concrete implementations, and it will then adapt those methods to give me the interfacet for the inherited traits?

Update

So, I can get there with a macro:

macro_rules! adapt_index {
    ($t:ident) => {
        impl std::ops::Index<Idx> for $t {
            type Output = Val;
            fn index(&self, index: Idx) -> &Val {
                self.val(index)
            }
        }
    };
}

but it still feels annoying that I have to apply that macro to all implementations of RMQArray, when it is the exact same code and all of them must implement it. It's a better solution than writing the boiler plate code for every instance, but it is still a crappy solution.

Then I thought, if I cannot implement the Index<> trait in RMQArray, maybe I can add generic code for all instances of RMQArray, so I tried this:

impl<T> std::ops::Index<Idx> for T
where
    T: RMQArray,
{
    type Output = Val;
    fn index(&self, index: Idx) -> &Self::Output {
        self.val(index)
    }
}

No go. That runs foul of the orphan rule; I'm not allowed to extend Index<> here for some reason having to do with T potentially coming from another package (I think it is, I can't say I have grokked Rust's type system in any meaningful way).

It seems reasonable to me that it describes how to implement Index for all types that implement RMQArray, and I guess it does, but it also makes sense that this could mess up other packages' implementation of same.

I tried hacking my way around this, but kept going back to needing dynamic dispatch and solutions that do not work with generics, so no luck with this approach either.

I can get it to work for my own traits, but that is useless if it is Index<> I need for the subscript syntactic sugar. I can't help thinking that there must be a standard Rust solution to what is essentially a trivial delegate/adaptor pattern, but it is possible that I am thinking about this in an entirely incorrect way, and I should fundamentally redesign this.

6
  • 1
    I think what you could do is to implement Index for your trait, to use it tho you will have to operate on a trait object (Box<dyn RMQArray>). Playground example play.rust-lang.org/… I am not 100% sure if that is what you are looking for tho.
    – Szymig
    Jan 25, 2022 at 9:56
  • That seems to work for dynamic dispatch. Not for generics, though, there I still have to duplicate the implementation for all concrete types. I could get around it with a macro, but that still feels like a pretty bad solution. But perhaps Rust just can't adapt traits in this way, and there is some other approach I'm supposed to use... don't know... Jan 25, 2022 at 11:18
  • 1
    The way to go is the opposite: instead of requiring val() and providing an Index impl (which you can't due to coherence), you should require an Index impl and (if needed) provide val() based on that. Jan 25, 2022 at 22:10
  • @ChayimFriedman the reason I wanted to go the other way is that there is a lot of boiler plate code in implementing Index, while val is a single method. I don't really need val, it was just an attempt at avoiding Index<>; if I had Index<> I wouldn't bother with val at all. Jan 26, 2022 at 4:26
  • Then you can use macros, but aside from that, I don't think there is something you can do. See How do I implement a trait I don't own for a type I don't own? Jan 26, 2022 at 22:19

2 Answers 2

0

Maybe you don't need RMQArray at all.

Is it better to just use macros directly like this?

1
  • I'm not sure if I need the trait--I can't say that I am fully understanding the Rust approach to generic types yet--but I just have a bunch of algorithms where I want to check the performance of different implementations of range minimum queries. It was my impression that I need a trait to specify what a generic parameter implements. I can't implement the RMQArray methods in the macro, though; they are different for different implementation. I just want all of them to support indexing, in their own specific way. Jan 27, 2022 at 5:20
0

Based on some of the suggestions, I hacked up a solution. I am not sure if it is a good solution, but I get what I want without a macro. Instead I have to wrap my types, so I have the same amount of boiler plate as with the macro, but at least it is different...

I have an interface that concrete types have to implement, just as before:

type Idx = usize;
type Val = u32;

/// To make a RMQArray, you should implement this and then wrap the type
/// in RMQArray_<>.
pub trait RMQArrayImpl {
    fn new(values: Vec<Val>) -> Self;
    fn len(&self) -> Idx;
    fn val(&self, index: Idx) -> &Val;
    fn rmq(&self, i: Idx, j: Idx) -> Idx;
}

It doesn't have the Index<> trait as prerequisite, because I don't want to implement that in the concrete types, but I add another type that requires RMQArrayImpl and std::ops::Index<Idx>:

/// Range Minimum Query interface.
/// We are just telling the type system that RMQArray implements RMQArrayImpl
/// and Index<Idx>.
pub trait RMQArray: RMQArrayImpl + std::ops::Index<Idx, Output = Val> {}

This isn't so different from before, but now I add a wrapper type. Its job is to give me a local type that I can extend, instead of trying to extend the Index<> interface, which Rust didn't allow.

/// Wrapper type to extend RMQArrayImpl.
pub struct RMQArray_<Impl: RMQArrayImpl>(Impl);

The idea is that all my concrete implementations will be RMQArrayImpl and I will then wrap them to make them RMQArray_<>, and the latter I can extend in generic implementations.

I need the wrapper type to implement RMQArrayImpl, and I couldn't find any better way than to wrap the entire interface. If there is one, please let me know.

/// A delegate that pulls the interface from T into RMQArray_<T>.
impl<T> RMQArrayImpl for RMQArray_<T>
where
    T: RMQArrayImpl,
{
    fn new(values: Vec<Val>) -> Self     { RMQArray_::<T>(T::new(values)) }
    fn len(&self) -> Idx                 { self.0.len() }
    fn val(&self, i: Idx) -> &Val        { self.0.val(i) }
    fn rmq(&self, i: Idx, j: Idx) -> Idx { self.0.rmq(i, j) }
}

I also want the wrapper type to implement RMQArray, but there is nothing to do here. It already implements RMQArrayImpl and it will implement Index<Idx> in a second, so it is just:

/// Make sure that an RMQArray_<T> implements RMQArray.
/// There is nothing to implement, we get it all from RMQArrayImpl,
/// but we still need to tell the type system.
impl<T> RMQArray for RMQArray_<T> where T: RMQArrayImpl {}

Then there is the generic code for implementing the Index<Idx> interface. This is what I couldn't do before, where I tried to implement it for all types T that implements RMQArray, but I can do it for all types RMQArray_<T> if T implements RMQArrayImpl:

/// Index for RMQArray_<>. It gives us the Index<> interface for all
/// RMQArrayImpl wrapped in RMQArray_<>.
impl<T> std::ops::Index<Idx> for RMQArray_<T>
where
    T: RMQArrayImpl,
{
    type Output = Val;
    fn index(&self, index: Idx) -> &Val {
        self.0.val(index)
    }
}

I also added Deref and DerefMut so I can access the wrapped type without indexing. I only really need that for testing, but now it is here anyway...

// Deref gives us access to the inner workings of T without
// going through the zero'th index in the wrapper.
impl<T> std::ops::Deref for RMQArray_<T>
where
    T: RMQArrayImpl,
{
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T> std::ops::DerefMut for RMQArray_<T>
where
    T: RMQArrayImpl,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

From here on, it is just implementing RMQArrayImpl for some type TImpl and then wrapping the type to type T = RMQArray_<TImpl>:

/// Implements RMQ by running through the [i,j) interval
/// and finding the index with the smallest value.
/// O(1) preprocessing and O(n) access.
pub struct BruteForceRMQImpl {
    values: Vec<u32>,
}

impl RMQArrayImpl for BruteForceRMQImpl {
    fn new(values: Vec<Val>) -> BruteForceRMQImpl { ... }
    fn len(&self) -> Idx                          { ... }
    fn val(&self, index: Idx) -> &Val             { ... }
    fn rmq(&self, i: Idx, j: Idx) -> Idx          { ... }
}

// This is the BruteForceRMQ type that gets the index from the wrapper
// type...
pub type BruteForceRMQ = RMQArray_<BruteForceRMQImpl>;


/// Implements RMQ by table lookup. Has a complete table of all [i,j),
/// so uses O(n²) memory, takes O(n²) time preprocessing, but then
/// does RMQ in O(1).
pub struct FullTabulateRMQImpl {
    values: Vec<u32>,
    rmq: InterTable,
}
pub type FullTabulateRMQ = RMQArray_<FullTabulateRMQImpl>;

impl RMQArrayImpl for FullTabulateRMQImpl {
    fn new(values: Vec<Val>) -> FullTabulateRMQImpl { ... }
    fn len(&self) -> Idx                            { ... }
    fn val(&self, index: Idx) -> &Val               { ... }
    fn rmq(&self, i: Idx, j: Idx) -> Idx            { ... }
}

/// RMQ table that tabulates all [i,i+2^k] ranges (there are O(n log n)),
/// form which we can get the RMQ from the table by splitting [i,j) into
/// two, [i,2^k) and [j-2^k,j) (where k is the largest such k). We can get
/// the RMQ from those two intervals with a table lookup in O(1) and then
/// pick the one of those with the smallest value.
/// The result is O(n log n) preprocessing and O(1) lookup.
pub struct PowerRMQImpl {
    lcp: Vec<Val>,
    tbl: TwoD,
}

impl RMQArrayImpl for PowerRMQImpl {
    fn new(lcp: Vec<u32>) -> PowerRMQImpl { ... }
    fn len(&self) -> Idx                  { ... }
    fn val(&self, index: Idx) -> &Val     { ... }
    fn rmq(&self, i: Idx, j: Idx) -> Idx  { ... }
}

pub type PowerRMQ = RMQArray_<PowerRMQImpl>;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.