Rust's type system reflects many advances in the state of the art.

However, there is one feature (offered by C++ and ML) that is not present in Rust: The ability to declare within a trait a named type (and then each impl item would be obligated to bind that name to an appropriate type for the implementation).

Related work: See Garcia et al. 2003, especially section 6.2, 10.2, and 10.3. Another useful reference is Chakravarty et al 2005

The Haskell community calls such a construct an "associated type synonym."

Here is an small example to illustrate the idea.

First, the easy part: how such a feature would look at the level of trait and impl items:

trait Graph {
  pub type Node;   // Graphs are composed of vertices
  pub type Edge;   // and arcs between the vertices.
  pub fn src(&self, edge: Edge) -> Node;
  pub fn tgt(&self, edge: Edge) -> Node;
}


// A vector of (source,target) pairs is a graph where the edges
// indices into the vector
impl<T : Copy> &[(T,T)] : Graph {
  pub type Node = T;    // Here we satisfy the obligation to provide Node
  pub type Edge = uint;  // and Edge implementation types.
  pub fn src(&self, edge: Edge) -> Node { let (s,_) = self[edge]; s }
  pub fn tgt(&self, edge: Edge) -> Node { let (_,t) = self[edge]; t }
}

Ideally one would extract the type from a trait by using a path, using a type parameter as a path component. So for example:

trait IncidenceGraph : Graph {
  pub fn out_degree(&self, node: self::Node) -> uint;
  pub fn out_edges(&self, node: self::Node, it: fn(self::Edge) -> bool);
}

fn children<G:IncidenceGraph>(&g:G, &n: G::Node) -> ~[G::Node] {
  let result = ~[];
  for g.out_edges(n) |e| {
    ret.push(g.tgt(n))
  }
  ret
}

Note: I am aware that one can express currently express type synonyms in much the same way that one does in Java (or C#, or Eiffel; see Garcia et al paper): by making them a type-parameter of the trait itself. Rust's type-inference system does make that workaround more palatable, but it seems natural to enable the developer to express what they mean more directly: These types are obligations of the implementation, much like the functions declared in the trait, and thus it makes sense to express them the same way.

There are various issues to consider: e.g.:

• Do we allow bounds on the type declarations in the trait,
• Is there is any potential ambiguity with module names introduced by allowing traits (or rather, type parameters implementing a trait) to appear as path components in paths that are used in a type-expression context.
• Are there any gotcha's or generalizations that have been uncovered by the broader PL community that we would want to address. (For example, GHC has indexed data families, with which I am not familiar but seem to be a generalization with some potential gotchas. Caveat: I am not a Haskell programmer.)

Despite the above issues, this seems like a relatively straightforward change to the language (especially since one can already encode the pattern, so adding it should not inject e..g any type soundness bugs, right?).