"expected type parameter, found struct" when implementing trait

Question

I am trying to create a trait for a directed graph structure and provide one very basic implementatio, but am running into compiler errors:

pub trait DiGraph<'a> {
    type N;
    fn nodes<T>(&'a self) -> T where T: Iterator<Item=&'a Self::N>;
    fn pre<T>(&'a self, node: Self::N) -> T where T: Iterator<Item=&'a Self::N>;
    fn succ<T>(&'a self, node: Self::N) -> T where T: Iterator<Item=&'a Self::N>;
}

struct SimpleNode {
    pre: Vec<usize>,
    succ: Vec<usize>,
}

pub struct SimpleDiGraph {
    pub nodes: Vec<SimpleNode>
}

impl<'a> DiGraph<'a> for SimpleDiGraph {
    type N = usize;

    fn nodes<T=std::ops::Range<usize>>(&'a self) -> T {
        return std::ops::Range { start: 0, end: self.nodes.len() };
    }
    fn pre<T=std::slice::Iter<'a,usize>>(&'a self, node: usize) -> T {
        return self.nodes[node].pre.iter();
    }
    fn succ<T=std::slice::Iter<'a,usize>>(&'a self, node: usize) -> T {
        return self.nodes[node].succ.iter();
    }
}

The error messages are:

error[E0308]: mismatched types
--> digraph.rs:21:16
|
21 |         return std::ops::Range { start: 0, end: self.nodes.len() };
|                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter, found struct `std::ops::Range`
|
= note: expected type `T`
= note:    found type `std::ops::Range<usize>`

error[E0308]: mismatched types
--> digraph.rs:24:16
|
24 |         return self.nodes[node].pre.iter();
|                ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter, found struct `std::slice::Iter`
|
= note: expected type `T`
= note:    found type `std::slice::Iter<'_, usize>`

error[E0308]: mismatched types
--> digraph.rs:27:16
|
27 |         return self.nodes[node].succ.iter();
|                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter, found struct `std::slice::Iter`
|
= note: expected type `T`
= note:    found type `std::slice::Iter<'_, usize>`

The error message is somewhat confusing to me - why would a type parameter be expected as return value? Is this simply a type mismatch (e.g. due to lifetimes) with a misleading error message?

Answer 1

<T=std::ops::Range<usize>> doesn't force T to be std::ops::Range<usize>, it just causes it to default to that if it doesn't know what else to use.

If you only ever want to return a Range<usize>, then use Range<usize> as the return type; there's no reason to have a generic parameter at all. What your code is effectively saying now is something like this:

• "You can pick any return type you want! If you don't care, I'll return a range<usize>."
• "I'd like you to return a String, please."
• "TOUGH you're getting a range<usize>!"
• "... but you said..."
• "I lied! MUAHAHAHAHAHA!"

If you actually want the caller to choose the return type, then you need to be prepared to return any T... which is almost impossible, since it could be anything from () to String to an OpenGL render context.

In that case, what you actually want to do is constrain T to some trait that requires types implement some sort of construction function. Default is an example of one.

Edit: Just to doubly clarify: you don't get to pick the types used in generic parameters, your caller does.

I didn't notice until just now that you're using different definitions in the trait and the implementation (don't do that). I assume that what you're really trying to do is say "this method returns something that's usable as an Iterator, but each impl can pick a different type." You cannot do this with generics.

What you want is an associated type on the trait, like so:

pub trait DiGraph<'a> {
    type Nodes;
    fn nodes(&'a self) -> Self::Nodes;
}

pub struct SimpleNode {
    pre: Vec<usize>,
    succ: Vec<usize>,
}

pub struct SimpleDiGraph {
    pub nodes: Vec<SimpleNode>
}

impl<'a> DiGraph<'a> for SimpleDiGraph {
    type Nodes = std::ops::Range<usize>;

    fn nodes(&'a self) -> Self::Nodes {
        return std::ops::Range { start: 0, end: self.nodes.len() };
    }
}