I'm trying to write a small library of generic data structures and algorithms in a way I hope to be as high-level/implementation-agnostic as possible. My reasoning: the less I constrain the implementations, the more reusable the code + test-cases, and the less code I need to change if I need to micro-optimize in the future.

I've been trying to use Rust's type system to my advantage here. Some examples of the traits I'm considering:

• Map<K, V>: Maps keys of type K to values of type V (a HashMap<K, V> would trivially implement this trait)
• Set<T>: An unordered collection of values of type T (a HashSet<T> would trivially implement this trait)

The interesting part comes down to references. For example, what should the type signature be for Map::get()? (I'm ignoring the self argument for now.)

• For HashMap<K, V>: Map<K, V> it's usually fn(&K) -> &V
• For Vec<T>: Map<usize, T> it could be fn(&usize) -> &T or fn(usize) -> &T
• For a bitmap type, e.g. BitMap: Map<usize, bool>, it really should be fn(usize) -> bool (fn(&usize) -> bool might work too), but fn(usize) -> &bool is too constraining since an efficient implementation usually uses something like Vec<u32> internally and thus can't return a &bool.

My solution here is to parameterize the reference types. For example the Map trait now becomes:

• Map<K, V, KRef, VRef>: Data structure mapping Ks to Vs whose keys are referenced by KRef and whose values are referenced by VRef.
• Map::get() now has signature fn(KRef) -> VRef and can be used for all scenarios described above. And as a bonus, a single data structure can implement multiple parameterizations of Map depending on the usage context.

Of course, now there's the issue of lifetimes. In the case of Map I arrived at this solution:

• Map<'v, K, V, KRef, VRef> where 'v denotes the lifetime of VRef
• Map::get() has signature fn<'s>(KRef) -> VRef where 's: 'v.
• An implementation requiring VRef=&V would need to implement Map<'v, K, V, KRef, &'v V>.

This approach seems to work most of the time, although it does feel slightly hacky.

Here's my best attempt at implementing a generic unit test to the Set trait (this unfortunately fails with 2 lifetime errors): Rust Playground

Am I going down the right path here? Is there a better way to achieve the generality + flexibility I'm looking for that satisfies the borrow checker? Hoping I'm overlooking something simple here, e.g. perhaps my testing strategy is flawed more than anything else.

2 posts - 2 participants

Read full topic