Type inference insufficient around trait parameterized functions

[msullivan]

This is related to #912.

The following code doesn't work:

fn main() {
    for iter::eachi(some({a: 0})) |i, a| { 
        #debug["%u %d", i, a.a];
    }
}

It fails with

nubs/closure-trait-infer.rs:3:27: 3:30 error: the type of this value must be known in this context
nubs/closure-trait-infer.rs:3         #debug["%u %d", i, a.a];

which is really unfortunate.

eachi is declared with the prototype fn eachi<A,IA:base_iter<A>>(vec: IA, blk: fn(uint, A) -> bool). When called in the above code, IA is instantiated with the type option<{a: int}>, and a note is made that option<{a: int}> must implement the trait base_iter<A>. However, without knowing the details of the implementation, there is no way to know that the only A such that option<{a: int}> implements base_iter<A> is {a: int}.

I can think of a couple of possible solutions, varying wildly in feasibility: 1) Do some sort of opportunistic impl search during typechecking, probably in some super ad-hoc place such as during function argument typechecking, after checking the non-closure arguments but before checking closure arguments. This is not particularly principled but might be pretty feasible.

2) Introduce proper higher kinded type variables and traits over them. Then traits wouldn't be parameterized over type variables but would instead be implemented for higher kinds. The signature of eachi would be fn eachi<A,IA:base_iter>(vec: IA<A>, blk: fn(uint, A) -> bool) and IA<A> would be unified with option<{a: int}> right off the bat.

3) Fix issue #912 so that the type isn't needed while typechecking the closure.

[nikomatsakis]

I agree this would be nice to fix. Considering your points in reverse order:

• I think #912 is a non-starter. I closed it.
• It's not obvious to me how higher-kinded types solves this problem. I think the problem has to do with the fact that we do not connect type parameters. That is to say, I don't think that unifying IA<A> with option<{f: int}> would necessarily equate A with {f: int}. I guess it depends on how flexible our system was, but I could imagine a higher-kinded type option<{f: _}> or foo<str, _>. In the latter case, the value would be foo<str, {f: int}> (not option<int>). So how could I unify foo<str, {f: int}> with IA<A> (not knowing what IA is) and extract a value for A?

Moreover, even if we had higher-kinded types, I am not sure that iterable would be a suitable place to use it. Defining iterable that way would rule out a type like BitSet from implementing iterable<int> and no other type.

• That leaves us with determining ifaces earlier rather than later. I would like to experiment with this but I do recall that the last time we talked it through there were complications, though I can't recall what they were. I guess the best thing to do is to read up more carefully on what Haskell does. If memory serves---and I could be wrong, I don't know Haskell very well---this particular problem that we are talking about is also related to functional dependencies: that is, we would like to be able to say that each iterable thing is only iterable over one type, and therefore if we know the value for IA, we can deduce the value for A. I think this relates to overloading: conceivably (in today's system) there could be a type empty_iterable which is defined for all A, for example, which would not help us in deducing the type of A.

[nikomatsakis]

To clarify what I wrote about higher-kinded types and inference: what I meant is that somewhere (the impl, I suppose) we'd have to define how IA<A> is mapped to the concrete self type for this impl. I think implicit in your point was an assumption that, to implement an interface with one type parameter, you must supply a nominal type with one parameter. And maybe this is the right way to do it, but it's not the only way to do it.