Implementing Higher-Ranked Traits in Rust

Rust's type system allows for powerful abstractions, but sometimes you need to express relationships between types that go beyond simple trait bounds. Higher-ranked traits (HRTs) enable you to specify trait bounds that depend on other types, allowing for more flexible and expressive generic code. This challenge will guide you through implementing a simplified version of HRTs to understand their core concepts.

Problem Description

The goal is to create a system where a trait Lookup can be implemented for a type M that takes a type K (the key type) and a type V (the value type) as parameters. The Lookup trait will require that K implements Eq and V implements Clone. This allows M to act as a lookup table, where you can provide the key type and value type at runtime. You'll need to use associated types and a generic parameter to achieve this.

Key Requirements:

• Define a trait Lookup with associated types Key and Value.
• Require that Key implements Eq and Value implements Clone.
• Implement Lookup for a simple Vec<(Key, Value)> type.
• Provide a function lookup that takes a Lookup and a Key and returns an Option<Value>.

Expected Behavior:

The lookup function should search the lookup table for the given key. If the key is found, it should return Some(Value) where Value is a clone of the value associated with the key. If the key is not found, it should return None.

Edge Cases to Consider:

• Empty lookup table: The function should return None if the lookup table is empty.
• Duplicate keys: The function should return the value associated with the first occurrence of the key.

Examples

Example 1:

Input:
let lookup_table: Vec<(i32, String)> = vec![(1, "one".to_string()), (2, "two".to_string())];
let lookup: VecLookup<i32, String> = lookup_table.into();
let result = lookup.lookup(1);

Output: Some("one".to_string())
Explanation: The key 1 is found in the lookup table, so the associated value "one" is returned as a clone.

Example 2:

Input:
let lookup_table: Vec<(i32, String)> = vec![(1, "one".to_string()), (2, "two".to_string())];
let lookup: VecLookup<i32, String> = lookup_table.into();
let result = lookup.lookup(3);

Output: None
Explanation: The key 3 is not found in the lookup table, so None is returned.

Example 3: (Edge Case - Empty Table)

Input:
let lookup_table: Vec<(i32, String)> = vec![];
let lookup: VecLookup<i32, String> = lookup_table.into();
let result = lookup.lookup(1);

Output: None
Explanation: The lookup table is empty, so None is returned.

Constraints

• The Key type must implement Eq.
• The Value type must implement Clone.
• The lookup function must return Option<Value>.
• The implementation should be reasonably efficient (linear search is acceptable for this simplified example).
• The code should compile without warnings.

Notes

• Think about how to use associated types to represent the key and value types within the Lookup trait.
• Consider how to make the Lookup trait generic over the key and value types.
• The VecLookup implementation should be straightforward, using a linear search.
• The into() method on Vec<(K, V)> should convert it into a VecLookup<K, V>. This is a convenience function to simplify testing.

trait Lookup { type Key; type Value;

fn lookup(&self, key: Self::Key) -> Option<Self::Value>;

}

struct VecLookup<K, V> { data: Vec<(K, V)>, }

impl<K: Eq, V: Clone> Lookup for VecLookup<K, V> { type Key = K; type Value = V;

fn lookup(&self, key: Self::Key) -> Option<Self::Value> {
    for (k, v) in &self.data {
        if *k == key {
            return Some(v.clone());
        }
    }
    None
}

}

impl<K: Eq, V: Clone> From<Vec<(K, V)>> for VecLookup<K, V> { fn from(vec: Vec<(K, V)>) -> Self { VecLookup { data: vec } } }