I have code that constructs various nested data structures, such as (Vec<Vec<T>>, Vec<T>).
Given a function T -> U, I’d like to map all elements entrywise and obtain a corresponding instance of (Vec<Vec<U>>, Vec<U>). Conceptually, this feels completely straightforward from a functorial perspective, but I’m unsure what the cleanest Rust pattern is for expressing it.
The only approach I can think of is defining a trait like this:
pub trait EntrywiseMapping {
type Inner;
type Output<U>: EntrywiseMapping<Inner = U>;
fn map<U, F>(self, f: F) -> Self::Output<U>
where
F: Fn(Self::Inner) -> U;
}
Then I could implement it for a few specific T, then their Vec<T>, and potentially use a procedural macro to derive it for more complex structs.
However, this feels a bit heavy-handed, and moreover the trait itself does not really enforce entrywise mapping — is there a more idiomatic or lightweight way to achieve entrywise mapping across nested containers or custom structs in Rust?
This will give you a error about overlapping implementations, because Vec<U> is a valid type for the type-variable T to have.
In order to perform this kind of automatically recursive transformation, you need some specific type or bounded set of (possibly generic) types that are considered leaves (i.e. they do not call another EntrywiseMapping implementation). You can’t say “all types without a specific mapping impl are leaves”.
Thus, if you want to be able to map, say, (Vec<Vec<i32>>, Vec<i32>), then you have to either:
Implement EntrywiseMapping for i32 specifically, or
Add a wrapper type struct Leaf<T>(T) (which implements EntrywiseMapping to apply the function to T) and use it like (Vec<Vec<Leaf<i32>>>, Vec<Leaf<i32>>).
There isn’t a simpler way to do this that isn’t also less generic. I think many would say that the more idiomatic approach is “stop trying to be so generic”. Most of the time, we write traits that provide a specific operation, which avoids the overlapping implementation problem by implicitly using a notion of leaf that is applicable to that specific operation — that is, taking the solution “implement EntrywiseMapping for i32 specifically” but with some domain-specific knowledge of why each type is a leaf or nonleaf for the purposes of that operation, and avoiding the need to make the trait work for any types other than the ones that mean something for that specific operation.
Yeah I meant implement it for some specific T, then for Vec<T> such that T implements this, etcetera. (I actually learned this technique from you in a previous question that is quite similar, but not as obvious as entrywise mapping.) I'll update this question for clarity. (I probably only need this for 2 or 3 T.)