Define a generic key extraction trait

I want to simplify defining custom comparison traits (PartialEq, Eq, PartialOrd, Ord, Hash, etc.).

This is my idea:

  1. Define a trait Key that extracts a key for comparing.
  2. Define a wrapper structure Keyed that wraps an object that implements the Key trait.
  3. Implement various comparison traits for the Keyed structure base on the extracted key. This indirection is to avoid the orphan rule that prevents me from defining comparison traits on types that define Key traits directly.

The Key trait is defined as follows:

trait Key<'a> {
    type Key;

    fn key(&'a self) -> Self::Key;
}

This trait can handle both and borrowed keys and non-borrowed keys :

struct NonBorrowedKey<K, V> {
    key: K,
    value: V,
}

impl<'a, K: Copy, V> Key<'a> for NonBorrowedKey<K, V> {
    type Key = K;

    fn key(&'a self) -> Self::Key {
        self.key
    }
}

struct BorrowedKey<K, V> {
    key: K,
    value: V,
}

impl<'a, K: 'a, V> Key<'a> for BorrowedKey<K, V> {
    type Key = &'a K;

    fn key(&'a self) -> Self::Key {
        &self.key
    }
}

The Keyed structured is:

struct Keyed<T>(pub T);

Now I can implement various traits for the Keyed structure. For example, PartialEq:

impl<T> PartialEq for Keyed<T>
where
    for<'a> T: Key<'a>,
    for<'a> <T as Key<'a>>::Key: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.0.key(), &other.0.key())
    }
}

But this solution does not seem to work:

fn main() {
    let x: Keyed<NonBorrowedKey<i32, i32>> = Keyed(NonBorrowedKey { key: 3, value: 2 });
    let y: Keyed<NonBorrowedKey<i32, i32>> = Keyed(NonBorrowedKey { key: 3, value: 5 });

    PartialEq::eq(&x, &y);
}

I got the following error from the code above:

can't compare `<NonBorrowedKey<i32, i32> as Key<'a>>::Key` with `<NonBorrowedKey<i32, i32> as Key<'a>>::Key`
the trait `for<'a> std::cmp::PartialEq` is not implemented for `<NonBorrowedKey<i32, i32> as Key<'a>>::Key`
required because of the requirements on the impl of `std::cmp::PartialEq` for `Keyed<NonBorrowedKey<i32, i32>>`
required by `std::cmp::PartialEq::eq`

You can try the codes here.

Why this error happens?

Too tired to debug rn, but I know how I'd implement it. Maybe this is what you want?

struct Key<K, T, F: Fn(&T) -> K> {
    val: T,
    f: F
}

impl<K: PartialEq, T, F: Fn(&T) -> K> PartialEq for Key<K, T, F> {
    fn eq(&self, other: &Self) -> bool {
        (self.f)(&self.val).eq(&(other.f)(&other.val))
    }
}

impl<K, T, F: Fn(&T) -> K> std::ops::Deref for Key<K, T, F> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.val
    }
}

Should be straightforward to make it use a trait on T instead of a function reference if that's more your style.

I think your method does not handle borrowed keys very well. The code below does not compile:

fn borrow(x: &i32) -> &i32 {
    x
}

fn main() {
    let x = Key { val: 4, f: borrow };
    let y = Key { val: 4, f: borrow };

    PartialEq::eq(&x, &y);
}

:confused:

I'll fix it in the morning, it's 4am here

Turns out I misread your question, I thought for some reason that you wanted to use a key function, but now I see that you actually just wanted to put two values in a struct and use one of them as a key. No idea how to solve the problem I initially thought you had, but here's the solution you're actually looking for.

struct Key<K, V> {
    key: K,
    #[allow(dead_code)]
    val: V,
}

impl<K: PartialEq, V> PartialEq for Key<K, V> {
    fn eq(&self, other: &Self) -> bool {
        PartialEq::eq(&self.key, &other.key)
    }
}

fn main() {
    let x = Key{ key: 3, val: 2 };
    let y = Key{ key: 3, val: 5 };

    println!("{}", PartialEq::eq(&x, &y));
}

I want to provide a way to define the comparison traits as a library. The actual data structure is unknown to the library. I want users of the library to define comparison traits for any of their custom data structures, not just a Key<K, V> structure. But this is not very important. Currently, I am more interested in why my codes does not work. I hope someone can provide an explanation about the error I encountered.

Without lifetime, it works, here.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.