opened
rust-highfive
username_0
Note: Much or all of the feature requested here should be covered by RFC PR #195

----

<a href="https://github.com/username_2"><img src="https://avatars.githubusercontent.com/u/173127?v=2" align="left" width="96" height="96" hspace="10"></img></a> **Issue by [username_2](https://github.com/username_2)**
_Tuesday Feb 19, 2013 at 16:15 GMT_

_For earlier discussion, see https://github.com/rust-lang/rust/issues/5033_

_This issue was labelled with: A-servo, A-traits, A-typesystem, B-RFC, I-enhancement, P-high in the Rust repository_

----

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](http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf), especially section 6.2, 10.2, and 10.3.  Another useful reference is [Chakravarty et al 2005](http://www.cse.unsw.edu.au/~chak/papers/CKP05.html)

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:

```rust
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:

```rust
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](http://www.haskell.org/haskellwiki/GHC/Type_families#Associated_family_declarations), 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?).
RFC: trait-declared associated type synonyms
issue
created
quantheory
username_1
I sort of like this proposal, but I'm puzzled. Shouldn't something like the following be possible under the existing RFC?

```rust
pub enum InputStep<I: InputIterator> {
    Cont(I::Element, I),
    Done(I::Leftovers),
}

pub enum ZipInputLeftovers<L: InputIterator, R: InputIterator> {
    More1(L::Element, L, R::Leftovers),
    More2(L::Leftovers, R::Element, R),
    Neither(L::Leftovers, R::Leftovers),
}
```

Of course this is more verbose than being able to inline these in the trait or impl, and you have to use names like `InputStep` in some cases, but this seems much better than making every used type a generic (input) parameter. Or am I wrong and something prevents this?
comment
created
pnkfelix
username_2
I'm going to close this ticket; at this point, the addition of associated items to the language has addressed the original problem that prompted me to file it back in early 2013, and any suggestions of further changes should be filed as separate tickets rather than appended here.
comment
closed
pnkfelix
username_2
issue