girving/duck — Issue #39: polymorphic overload optimization?
Author: dylex
Created: 2011-11-28 13:12:18+00:00
State: open

Consider the overload `length :: [a] -> Int`. This function can be inferred identically (returning Int) for any use that matches this overload.

The overload `head :: [a] -> a` also could be inferred identically, if we allow type variables in the return.

However, the overload `sum :: [a] -> _` cannot be, becuse which overload(s) (of `+`) it uses depends on the type a.

This suggests an optimization for overload resolution. First we need something between TypeVal and TypePat that is TypeVal + variable.

During function inference, we could simply treat argument types in the local environment as lazy somehow, such that whenever we actually use a TypeVal for overload resolution, it gets fully resolved, but any types we end up not needing for resolution we know can stay as type variables.

Then, for overload resolution, we just need some special kind of map in the ptrie that knows that anything can be a type variable when looking up concrete TypeVals.

I'm not sure whether this complicates fixpoint resolution. It might not, but if it does it could always be done as a second pass to "generalize" the overload table.