Draft RFC: variadic generics

Issue by eddyb
Monday Oct 28, 2013 at 17:39 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/10124

This issue was labelled with: B-RFC in the Rust repository

---

The Problem

• fn types need a reform, and being able to define a trait with a variable number of type parameters would help
• working with functions which have a variable number of arguments is impossible right now (e.g. a generic bind method, f.bind(a, b)(c) == f(a, b, c)) and defining such functions may only be done (in a limited fashion) with macros
• tuples also have similar restrictions right now, there is no way to define a function which takes any tuple and returns the first element, for example

The Solution: Part One

C++11 sets a decent precedent, with its variadic templates, which can be used to define type-safe variadic functions, among other things.
I propose a similar syntax, a trailing ..T in generic formal type parameters:

type Tuple<..T> = (..T); // the parens here are the same as the ones around a tuple.
// use => expansion
Tuple<> => ()
Tuple<int> => (int,)
Tuple<A, B, C> => (A, B, C)

The simple example above only uses ..T, but not T itself.
The question which arises is this: what is T? C++11 has a special case for variadic parameter packs, but we can do better.
We have tuples. We can use them to store the actual variadic generic type parameters:

// Completely equivalent definition:
type Tuple<..T> = T;
// Detailed expansion of (..T) from above:
Tuple<> => (..()) => ()
Tuple<int> => (..(int,)) => (int,)
Tuple<A, B, C> => (..(A, B, C)) => (A, B, C)

The Solution: Part Two

Now that we know the answer is "tuples", everything else is about extending them.
The prefix .. operator would expand a tuple type:

// in another tuple type:
type AppendTuple<T, U> = (..T, U);
type PrependTuple<T, U> = (U, ..T);
AppendTuple<PrependTuple<Tuple<B>, A>, C> => (A, B, C)
// in a fn type's parameter list:
type VoidFn<..Args> = fn(..Args);
VoidFn<A, B, C> => fn(A, B, C);
// in a variadic generic parameter list:
Tuple<..(A, B, C), ..(D, E, F)> => (A, B, C, D, E, F)

Then we can do the same thing with values:

// in another tuple:
(..(true, false), ..(1, "foo"), "bar") => (true, false, 1, "foo", "bar")
// in a function call:
f(..(a, b), ..(c, d, e), f) => f(a, b, c, d, e, f)

There's only one piece missing: we're still not able to define a function which takes a variable number of arguments.
For this, I propose ..x: T (where T is a tuple type) in a pattern, which can be used to "capture" multiple arguments when used in fn formal arguments:

// Destructure a tuple.
let (head, ..tail) = foo;
// This function has the type fn(int, A, B, C), and can be called as such:
fn bar(_: int, ..x: (A, B, C)) -> R {...}

A type bound for ..T (i.e. impl<..T: Trait>) could mean that the tuple T has to satisfy the bound (or each type in T, but that's generally less useful).

Examples:

// The highly anticipated Fn trait.
trait Fn<Ret, ..Args> {
    fn call(self, .._: Args) -> Ret;
}
impl Fn<Ret, ..Args> for fn(..Args) -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}
impl Fn<Ret, ..Args> for |..Args| -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}

// Cloning tuples (all cons-list-like algorithms can be implemented this way).
impl<Head, ..Tail: Clone> Clone for (Head, ..Tail) {
    fn clone(&self @ &(ref head, ..ref tail)) -> (Head, ..Tail) {
        (head.clone(), ..tail.clone())
    }
}
impl Clone for () {
    fn clone(&self) -> () {
        ()
    }
}

// Restricting all types in a variadic tuple to one type.
trait ArrayLikeTuple<T> {
    fn len() -> uint;
}
impl<T> ArrayLikeTuple<T> for () {
    fn len() -> uint {0}
}
impl<T, ..Tail: ArrayLikeTuple<T>> ArrayLikeTuple<T> for (T, ..Tail) {
    fn len() -> uint {
        1 + Tail::len()
    }
}

// And using that trait to write variadic container constructors.
impl<T> Vec<T> {
    fn new<..Args: ArrayLikeTuple<T>>(..args: Args) -> Vec<T> {
        let v: Vec<T> = Vec::with_capacity(Args::len());
        // Use an unsafe move_iter-like pattern to move all the args
        // directly into the newly allocated vector. 
        // Alternatively, implement &move [T] and move_iter on that.
    }
}

// Zipping tuples, using a `Tuple` kind and associated items.
trait TupleZip<Other>: Tuple {
    type Result: Tuple;
    fn zip(self, other: Other) -> Result;
}
impl TupleZip<()> for () {
    type Result = ();
    fn zip(self, _: ()) -> () {}
}
impl<A, ATail: TupleZip<BTail>, B, BTail: Tuple> TupleZip<(B, ..BTail)> for (A, ..ATail) {
    type Result = ((A, B), ..ATail::Result);
    fn zip(self @ (a, ..a_tail), (b, ..b_tail): (B, ..BTail)) -> Result {
        ((a, b), ..a_tail.zip(b_tail))
    }
}

Todo

• better formal descriptions
• figure out the details of pattern matching
• more examples

Start by reading the earlier discussion in issue 10124, then review this proposal's syntax and examples. The draft's stated completion work is to provide better formal descriptions, resolve pattern-matching details, and add more examples; no implementation files or tests are named.