Original-Via: uk.ac.nsf; Fri, 15 Nov 91 20:43:50 GMT Has anyone looked at the complexity of type inference in Haskell (similar to analogous results for ML)? Nipkow and Snelting have shown how to reduce the inference problem to order-sorted unification (FPCA'91) and they point out that such unification for unitary signatures is quasi-linear. This would suggest that the complexity is similar to ML type inference. The only thing that concerns me is that a large number of conjunctive sorts have to be introduced implicitly, and perhaps this may affect the complexity result. Satish
