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.
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.val()
and providing anIndex
impl (which you can't due to coherence), you should require anIndex
impl and (if needed) provideval()
based on that.val
is a single method. I don't really needval
, it was just an attempt at avoidingIndex<>
; if I hadIndex<>
I wouldn't bother withval
at all.