Associated *new* types

[eduardoleon]

I am interested in using Rust’s new associated types feature to reduce the amount of boilerplate in some old code of mine that has generic traits and implementations with very scary parameter lists. Consider the following example, which does not use associated types:

// The result of trying to read an element from an iterator
pub enum GetResult<Iterator, Element, Leftovers> {
    GetCont(Element, Iterator),  // Element successfully read
    GetDone(Leftovers)           // End of iterator
}

// We encode an ML-like signature for iterators as a trait
// Every type member of the signature is a generic parameter
/*  module type INPUT_ITERATOR = sig
 *    type iterator
 *    type element
 *    type leftovers
 *    val get : iterator -> (iterator, element, leftovers) get_result
 *  end
 */
pub trait InputIterator<Iterator, Element, Leftovers> {
    fn get(self, Iterator) -> GetResult<Iterator, Element, Leftovers>;
}

It is natural to want to be able to zip iterators:

pub struct Zip<L, R> { left: L, right: R }

pub enum ZipInputLeftovers<LI, LE, LL, RI, RE, RL> {
    MoreL(LE, LI, RL),  // Left iterator stopped first
    MoreR(LL, RE, RI),  // Right iterator stopped first
    Neither(LL, RL)     // Both iterators stopped at the same time
}

impl< LI, LE, LL, L: InputIterator<LI, LE, LL>,
      RI, RE, RL, R: InputIterator<RI, RE, RL> >
    
    Iterator< (LI, RI), (LE, RE),
        ZipInputLeftovers<LI, LE, LL, RI, RE, RL> >
    
    for Zip<L, R> {
    
    fn get(self, (li, ri): (LI, RI)) -> GetResult< (LI, RI), (LE, RE),
        ZipLeftovers<LI, LE, LL, RI, RE, RL> > {
        
        match (self.left.get(li), self.right.get(ri)) {
            (GetCont(le, li), GetCont(re, ri)) => GetCont( (le, re), (li, ri) ),
            (GetCont(le, li), GetDone(rl)) => GetDone( MoreL(le, li, rl) ),
            (GetDone(ll), GetCont(re, ri)) => GetDone( MoreR(ll, re, ri) ),
            (GetDone(ll), GetDone(rl)) => GetDone( Neither(ll, rl) )
        }
    }
}

With associated types, as documented in the RFC, some of the boilerplate can be reduced:

pub trait InputIterator {
    type Iterator;
    type Element;
    type Leftovers;
    
    fn get(self, Iterator) -> GetResult<Iterator, Element, Leftovers>;
}

impl<L: InputIterator, R: InputIterator> InputIterator for Zip<L, R> {
    type Iterator = (L::Iterator, R::Iterator);
    type Element = (L::Element, R::Element);
    type Leftovers = ZipInputLeftovers<
        L::Iterator, L::Element, L::Leftovers,
        R::Iterator, R::Element, R::Leftovers >;
    
    fn get(self, (li, ri): Iterator) -> Get<Iterator, Element, Leftovers> {
        // ...
    }
}

However, some of the annoyances remain:

1. We still need generic types with long type parameter lists. GetResult has 3 type parameters. ZipInputLeftovers has 6 type parameters. Some of the scariest iterators in my library have associated types with more than 10 (!) type parameters.

2. It is possible to instantiate GetResult with nonsensical types, for instance GetCont("hello", 1) has type GetResult<int, &'static str, T>. How does it make sense for int to be an iterator type? Things get even worse with ZipInputLeftovers and the other bigger generic types.

I propose that these issues can be avoided by allowing traits and implementations to contain not just associated type synonyms, but also new type definitions (that is, structs and enums):

// The ML analogue is allowing translucent signatures....
/*  module type INPUT_ITERATOR = sig
 *    type iterator
 *    type element
 *    type leftovers
 *    type result = CONT of element * iterator | DONE of leftovers
 *    val get : iterator -> result
 *  end
 */
pub trait InputIterator {
    type Iterator;
    type Element;
    type Leftovers;
    
    enum Result {
        Cont(Element, Iterator),
        Done(Leftovers)
    }
    
    fn get(self, Iterator) -> Result;
}

impl<L: InputIterator, R: InputIterator> InputIterator for Zip<L, R> {
    type Iterator = (L::Iterator, R::Iterator);
    type Element = (L::Element, R::Element);
    enum Leftovers {
        MoreL(L::Element, L::Iterator, R::Leftovers),
        MoreR(L::Leftovers, R::Element, R::Iterator),
        Neither(L::Leftovers, R::Leftovers)
    }
    
    fn get(self, (li, ri): Iterator) -> Result {
        match (self.left.get(li), self.right.get(ri)) {
            (L::Cont(le, li), R::Cont(re, ri)) => Cont( (le, re), (li, ri) ),
            (L::Cont(le, li), R::Done(rl)) => Done( MoreL(le, li, rl) ),
            (L::Done(ll), R::Cont(re, ri)) => Done( MoreR(ll, re, ri) ),
            (L::Done(ll), R::Done(rl)) => Done( Neither(ll, rl) )
        }
    }
}

To my taste, this code is more pleasant for the following reasons:

1. Gone are the long generic parameter lists. Because Zip<L,R>::Leftovers is defined in a context in which L and R are both known to implement InputIterator, we have direct access to all six types {L, R}::{Iterator, Element, Leftovers}.

2. It is no longer possible to construct Zip<L, R>::Leftovers values from things that are not legitimately iterators, elements and leftovers. The type system now checks more of the program’s correctness for us.

An important observation is that this design breaks if we allow the type member InputIterator::Result to be overriden in implementations. Notice that the implementation of InputIterator for Zip<L, R> pattern-matches on the constructors of L::Result and R::Result.

Summarizing, my proposal consists of two things:

1. Adding associated new types (structs and enums).
2. Preventing associated new types being overriden (unlike associated type synonyms).

Do you guys think this proposal could make it as an extension to the associated types RFC?

[comex]

Any reason you can’t do this (other than it being somewhat syntactically heavy)?

enum Result<II:InputIterator> {
	Cont(<II as InputIterator>::Element, <II as InputIterator>::Iterator),
	Done(<II as InputIterator>::Leftovers)
}

[eduardoleon]

To the best of my knowledge, you cannot add trait bounds to generic type definitions. If I am wrong, please correct me.

EDIT 1: I was wrong. Thanks for the suggestion!

EDIT 2: Your code does not compile. Here is the exact thing I tried.