"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?

DK. · Accepted Answer · 2016-11-21 04:24:18Z

8

<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() };
    }
}

answered Nov 21, 2016 at 4:24

DK.

59.7k7 gold badges209 silver badges171 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Henning Koehler Over a year ago

Thanks, good explanation, you guessed my intend correctly. However, in your case Nodes can be anything, which means any function operating on DiGraphs isn't going to be able to do much since it can't make any assumptions about Nodes. So what I'd like to do is restrict Nodes to get an iterator over N (usize in my example, but defined by the caller). I'm happy for SimpleDiGraph to always return a Range<N> object, but other structs implementing DiGraph should be able to return other Iterators over N. Any way to achieve that?

Henning Koehler Over a year ago

Think I figured it out, seem you can actually restrict trait types, such as type NodeIterator: Iterator<Item=&'a Self::Node>; which should do the trick. Now just to figure out lifetime issues.

Collectives™ on Stack Overflow

"expected type parameter, found struct" when implementing trait

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related