use len_trait::Len; // I employed len-trait = "0.6.1"
pub trait VTest<T:Copy+PartialEq+PartialOrd+Sized>
: Index<usize,Output=T> + IndexMut<usize,Output=T> + Len {
fn add(&mut self, t: T);
fn swap(&mut self, i: usize, j: usize) {
let temp: T = self[i];
self[i] = self[j];
self[j] = temp;
}
fn selection_sort(&mut self) {
for i in 0..self.len() {
let lowest = (i+1..self.len())
.fold(i, |lowest, j|
if self[lowest] < self[j] {lowest} else {j});
self.swap(lowest, i);
}
}
}
Now, in order to implement this trait, we are faced with code duplication for the constraints on the generic variable T:
impl <T:Copy+PartialEq+PartialOrd+Sized> VTest<T> for Vec<T> {
fn add(&mut self, t: T) {
self.push(t);
}
}
impl <T:Copy+PartialEq+PartialOrd+Sized> VTest<T> for VecDeque<T> {
fn add(&mut self, t: T) {
self.push_back(t);
}
}
When coding, the most expedient way forward is to copy-and-paste this sequence of constraints on T. From both an aesthetic and a maintenance perspective, this is a nightmare.
Option 1: Create an empty trait
So, when faced with this, I undertook a search to determine what others had done when faced with this situation. The top search result suggested something like the following:
pub trait SimpleValue : Copy+PartialEq+PartialOrd+Sized {}
Which, in turn, enables me to write the following:
pub trait VTest<T:SimpleValue>
: Index<usize,Output=T> + IndexMut<usize,Output=T> + Len {
// ...
}
impl <T:SimpleValue> VTest<T> for Vec<T> {
// ...
}
impl <T:SimpleValue> VTest<T> for VecDeque<T> {
// ...
}
Now that looks much better! But there is a small wrinkle. Rust won't automatically infer that, say, usize automatically implements the SimpleValue trait. So I do have to declare explicitly that it does:
impl SimpleValue for usize {}
Again, this doesn't seem that much of a price to pay. And within the scope of a single crate, it works perfectly well and solves the problem. Where we run into trouble is if we find that our new VTest trait is so successful that we want to import it from a different crate. We would, of course, import SimpleValue as well.
And actually, this works, most of the time, unless you try something like this:
impl SimpleValue for i64 {}
In response, the compiler will reply with an error message along the following lines:
error[E0117]: only traits defined in the current crate can be implemented for arbitrary types
--> src\lib.rs:21:5
|
21 | impl SimpleValue for i64 {}
| ^^^^^^^^^^^^^^---
| | |
| | `i64` is not defined in the current crate
| impl doesn't use only types from inside the current crate
|
= note: define and implement a trait or new type instead
Something that is extremely cool about the Rust compiler is its inclusion of hyperlinks to explanations of compiler errors. When we follow this particular link, we learn:
This error indicates a violation of one of Rust's orphan rules for trait implementations. The rule prohibits any implementation of a foreign trait (a trait defined in another crate) where
- the type that is implementing the trait is foreign
- all of the parameters being passed to the trait (if there are any) are also foreign.
Orphan rule? What's that? Imagine two crates, each of which implements the same foreign trait for the same foreign datatype. If someone tries to use both crates in a project, we get an ambiguity; that is, it is not clear which trait implementation we should actually use. So the Rust solution is to prohibit the implementation of a foreign trait on a foreign type in all situations, so as to prevent this error from ever occurring. This is actually allowed in the Haskell language, although it triggers a compilation warning and is widely discouraged.
This rule has proven hugely unpopular, as it prevents lots of perfectly correct code (such as the motivating situation in this post) from being compiled. One could imagine expressing a preference for which crate's trait implementation to use, but this runs into trouble when code from the other crate relies on its own version. And simply prohibiting crates from being imported together impedes code reuse. It is clear that there is no straightforward solution.
Option 2: The Trait Alias
This leads to another possible solution, the concept of the trait alias, which is really all we wanted to begin with. With a trait alias, a collection of traits can be given a name, purely local to the crate in which it is embedded. Any qualifying types that match can then implement the trait. Here is what our example looks like with trait aliases:
#![feature(trait_alias)]
pub trait Item = Copy+PartialEq+PartialOrd+Sized;
pub trait VTest<T:Item> : Index<usize, Output="T"> + IndexMut<usize, Output="T"> + Len {
fn add(&mut self, t: T);
fn swap(&mut self, i: usize, j: usize) {
let temp: T = self[i];
self[i] = self[j];
self[j] = temp;
}
fn selection_sort(&mut self) {
for i in 0..self.len() {
let lowest = (i+1..self.len())
.fold(i, |lowest, j|
if self[lowest] < self[j] {lowest} else {j});
self.swap(lowest, i);
}
}
}
impl <T:Item> VTest<t> for Vec<T> {
fn add(&mut self, t: T) {
self.push(t);
}
}
impl <T:Item> VTest<t> for VecDeque<T> {
fn add(&mut self, t: T) {
self.push_back(t);
}
}
Currently, trait aliases are only available in nightly Rust. There is still considerable discussion about how the feature should work and what the syntax should look like, so it is not clear when the feature is going to be stabilized. In the meantime, I think this feature is so essential for ergonomic use of Rust that I am defaulting to the nightly compiler for all of my projects until this feature is stabilized.
No comments:
Post a Comment