Need help with generics

I'd like to have an object that takes a vector of items of a generic type D (say, D: Vec<64>) and performs some generic mathematical operation on them, e.g. finds the two closest elements of this vector given some generic metric M. The ability to compute that distance is declared by Distance<D> trait where D is the type of data being compared. Then I implemented that trait for a ManhattanDistance and now I'd like my struct ClosestPair<M> find the two closest points with ManhattanDistance serving as M.

I'd also like the very same ClosestPair<M> to work with String data and some Distance<String>. But rust says:

   Compiling playground v0.0.1 (/playground)
error[E0207]: the type parameter `D` is not constrained by the impl trait, self type, or predicates
  --> src/main.rs:24:6
   |
24 | impl<D: Index<usize>, M> ClosestPair<M> {
   |      ^ unconstrained type parameter

Here is my attempt:

use core::ops::Index;

pub trait Distance<D> {
    fn d(di:&D, dj:&D) -> D;
}

struct ManhattanDistance {}

impl Distance<Vec<f64>> for ManhattanDistance {
    fn d(di: &Vec<f64>, dj: &Vec<f64>) -> f64 {
        let mut out:f64 = 0.0;
        for i in 0..di.len() {
            out += (di[i]-dj[i]).abs();
        }
        return out;
    }
}


struct ClosestPair<M> {
    measure: M
}

impl<D: Index<usize>, M> ClosestPair<M> {

    pub fn find_closest(&self, data: Vec<D>) -> f64{
        self.measure.d(&data[0], &data[1])
    }
}

pub fn main() {
    let p1: Vec<f64> = vec![0.0, 1.0, 2.0];
    let p2: Vec<f64> = vec![4.0, 1.0, 2.0];
    let p3: Vec<f64> = vec![0.0, 2.0, 2.0];

    let data = vec![p1, p2, p3];
    
    let closest: ClosestPair<ManhattanDistance>;
    closest.find_closest(data);
}


(Playground)

There are actually several additional issues with the way you've set things up that that compile error is hiding. The simplest way to fix that error is to use an associated type instead of a type parameter on the trait. That means a single type can only implement the trait for one D, but I don't think that's a problem at least in your simple example.

One of the other problems you have is that you define the trait method as

fn d(di:&D, dj:&D) -> D;

but your impl of the trait has a signature that doesn't match

fn d(di: &Vec<f64>, dj: &Vec<f64>) -> f64

In the impl D is both Vec<f64> and f64, which is a contradiction. So we need another associated type for the output in addition to an associated type to replace D with.

Putting those two things together gets us

pub trait Distance {
    type Value;
    type Output;
    
    fn d(di: &Self::Value, dj: &Self::Value) -> Self::Output;
}

impl Distance for ManhattanDistance {
    type Value = Vec<f64>;
    type Output = f64;

    fn d(di: &Vec<f64>, dj: &Vec<f64>) -> f64 {
        let mut out: f64 = 0.0;
        for i in 0..di.len() {
            out += (di[i] - dj[i]).abs();
        }
        return out;
    }
}

Where we run into another problem. You're trying to call the method d on an instance of Distance, but the method doesn't take a self parameter, so it can only be called on the type.

Fixing that gets us

pub trait Distance {
    type Value;
    type Output;
    
    fn d(&self, di: &Self::Value, dj: &Self::Value) -> Self::Output;
}

Now we need to fix the impl on ClosestPair to use the associated types we added to Distance

impl<M: Distance> ClosestPair<M> {
    pub fn find_closest(&self, data: Vec<M::Value>) -> M::Output {
        self.measure.d(&data[0], &data[1])
    }
}

Finally, we need to actually create an instance of ClosestPair in main.

let closest = ClosestPair {
    measure: ManhattanDistance {},
};

We can actually use a unit struct here for ManhattanDistance instead of an empty record struct

struct ManhattanDistance;

instead of

struct ManhattanDistance {}

but either will work.


Putting it all together we get
Playground

pub trait Distance {
    type Value;
    type Output;

    fn d(&self, di: &Self::Value, dj: &Self::Value) -> Self::Output;
}

struct ManhattanDistance {}

impl Distance for ManhattanDistance {
    type Value = Vec<f64>;
    type Output = f64;

    fn d(&self, di: &Vec<f64>, dj: &Vec<f64>) -> f64 {
        let mut out: f64 = 0.0;
        for i in 0..di.len() {
            out += (di[i] - dj[i]).abs();
        }
        return out;
    }
}

struct ClosestPair<M> {
    measure: M,
}

impl<M: Distance> ClosestPair<M> {
    pub fn find_closest(&self, data: Vec<M::Value>) -> M::Output {
        self.measure.d(&data[0], &data[1])
    }
}

pub fn main() {
    let p1: Vec<f64> = vec![0.0, 1.0, 2.0];
    let p2: Vec<f64> = vec![4.0, 1.0, 2.0];
    let p3: Vec<f64> = vec![0.0, 2.0, 2.0];

    let data = vec![p1, p2, p3];

    let closest = ClosestPair {
        measure: ManhattanDistance {},
    };

    println!("{:?}", closest.find_closest(data));
}

Which I can't guarantee is finding the output you expect, but does at least compile!

3 Likes