Rust won't narrow down types? Or did I make a mistake

Question

Trying to write something similar to Haskell's HList, with the ability to search by type. With the below code, in play.rust-lang.org version rustc 0.13.0-dev (567b90ff0 2014-12-13 20:02:15 +0000) I get an error:

<anon>:35:26: 35:31 error: unable to infer enough type information to locate the impl of the trait `ContainsRel<int, _>` for the type `HCons<int, HNil>`; type annotations required
<anon>:35     let foo: &int = list.get();
                                   ^~~~~

I'm not sure why it can't infer the proper type, HNil has no ContainsRel impls.

trait HList {}

struct HNil;
struct HCons<H, T: HList>(H, T);

impl HList for HNil {}
impl<H, T: HList> HList for HCons<H, T> {}


trait Peano {}

struct Zero;
struct Succ<N: Peano>(N);

impl Peano for Zero {}
impl<N: Peano> Peano for Succ<N> {}

trait ContainsRel<E, P: Peano> {
    fn get(&self) -> &E;
}

impl<E, L: HList> ContainsRel<E, Zero> for HCons<E, L> {
    fn get(&self) -> &E {
        &self.0
    }
}
impl<E, X, L: ContainsRel<E, P>+HList, P: Peano> ContainsRel<E, Succ<P>> for HCons<X, L> {
    fn get(&self) -> &E {
        self.1.get()
    }
}

fn main() {
    let list: HCons<uint, HCons<int, HNil>> = HCons(5u, HCons(6i, HNil));
    let foo: &int = list.get();
}

Answer 1

Someone could impl the Peano trait for another type, even in another crate, and then the list.get() in main would become ambiguous. If you try to substitute types manually in the impl, you get:

impl <E=int, X=uint , L=HCons<int, HNil>, P=?> ContainsRel<int, Succ<P=?>> for HCons<uint, HCons<int,HNil>>

With the types defined so far, P must be Zero (as it's the only implementation of Peano in scope), but anyone would be allowed to define another struct that implements P in another module, so Rust forces you to be explicit. For instance, adding this would be valid:

struct Foo;
impl Peano for Foo {}
impl<E, L: HList> ContainsRel<E, Foo> for HCons<E, L> {
    fn get(&self) -> &E {
        &self.0
    }
}

Specifying the type of P works:

let foo: &int = ContainsRel::<_, Succ<Zero>>::get(&list);

...but yes, it does not look great.