Disclaimer: Firstly, this is long, because I had trouble properly motivating this question without going into detail. Secondly, multidimensional arrays for numerics are not the only application with the sort of issue described here, but they are what I’m immediately concerned with and have examples for.
Specialized languages and frameworks for numerical work usually have multidimensional arrays, and very often have succint syntax for multidimensional slices/sections in those arrays. Just to pick a few off the top of my head, there’s NumPy, MATLAB, and Fortran 90. In Rust, this might look like one of the following options:
// "arr" is a 4x4 array of elements of type T.
// "foo" receives an object representing a view of the non-contiguous
// 2x2 block in the middle of this array (without copying).
// C-like syntax
foo(arr[1..2][1..2]);
// Less conventional and intuitive, but also less reliant on inlining.
foo(arr[(1, 1)..(2, 2)]);
// Yet another possibility (but all of these have the problem below).
foo(arr[[1, 1]..[2, 2]]);
Before I get further into this, I want to get two things out of the way:
-
Good multi-dimensional arrays need to be implemented by a library right now, since nothing provided by
stdis a good substitute. One reason is that for many (most?) applications it is desirable for array size to be set when an array is constructed (not dynamically varying like Vec, but not fixed at compile time like built-in arrays). Another reason is that multidimensional arrays are not really the same thing as arrays-of-arrays (due to both layout conventions and the operations that it makes sense to implement). -
Most languages with multidimensional array slices also have “strides”, e.g. taking every third element from an array. I’m just going to ignore this for now, because I believe that it’s less commonly used, less performant, and less important to have syntactic sugar for.
Now getting to the point, if it was possible to implement one of the slicing examples above, what type would the result of the “slicing” have? It would be multiple items of type T (so not &T), but not contiguous (so not an actual slice, &[T]). It should really be some new struct, e.g. Slice2D<T>. (Or if you can leverage the type system to encourage optimization or SIMD vectorization for piecewise contiguous slices, it could be something like Slice1Contig2D<T>.) This first iteration works OK for C++, but Rust has lifetimes, which are an additional wrinkle.
Let’s look at a very simple (toy) case where a struct, rather than a reference or (built-in) slice, is returned from an indexing method:
struct MyPtr<'a> {
data: &'a uint
}
struct MySingleInt {
item: uint
}
impl MySingleInt {
fn index<'a>(&'a self, idx: uint) -> MyPtr<'a> {
assert!(idx == 0,
"Out of bounds index; MySingleInt has only a 0th element.");
MyPtr{data: &self.item}
}
}
fn main() {
let x = MySingleInt{item:5};
let y = x.index(0);
println!("{}", y.data);
}
Compare to the trait in RFC 439:
pub trait Index<Idx> for Sized? {
type Sized? Result;
fn index<'a>(&'a self, index: Idx) -> &'a Result;
}
One problem here is that the Index trait requires a reference to be returned. This is troublesome because in this example we want to return a newly constructed wrapper object, not a reference to any pre-existing variable.
However, the bigger problem is that of specifying the lifetime. In the trait, the Result type must be specified separately from the index function. However, we want Result to be parameterized by the lifetime 'a.
This leads me to a three related questions:
-
Is this soluble without changing the definition of
Index, or am I correct in thinking that this is like the long-desired “Iterable” trait, in that a solution requires HKT? -
Is there an acceptable solution to this if we change the definition of
Index, and given HRTB? E.g.:pub trait Index<'a, Idx> for Sized? { type Sized? Result; fn index(&'a self, index: Idx) -> <Self as Index<'a, Idx>>::Result; } -
If neither of the above is possible, is there something else that would work that would be backwards-compatible post-1.0?