TY - JOUR
T1 - Type-checking multi-parameter type classes
AU - Duggan, Dominic
AU - Ophel, John
PY - 2002
Y1 - 2002
N2 - Type classes are a novel combination of parametric polymorphism and constrained types. Although most implementations restrict type classes to be single-parameter, the generalization to multi-parameter type classes has gained increasing attention. A problem with multiparameter type classes is the increased possibilities they introduce for ambiguity in inferred types, impacting their usefulness in many practical situations. A new type-checking strategy, domain-driven unifying resolution, is identified as an approach to solve these problems. Domaindriven unifying resolution is simple, efficient, and practically useful. However, even with severe restrictions on instance definitions, it is not possible to guarantee that type-checking with unifying resolution terminates. This is in contrast with the naive generalization of single parameter resolution strategies. Domain-driven unifying resolution is guaranteed to terminate if the type class constraints are satisfiable; however satisfiability is undecidable even with severe restrictions on instance definitions. These results shed some light on ambiguity problems with multi-parameter type classes.
AB - Type classes are a novel combination of parametric polymorphism and constrained types. Although most implementations restrict type classes to be single-parameter, the generalization to multi-parameter type classes has gained increasing attention. A problem with multiparameter type classes is the increased possibilities they introduce for ambiguity in inferred types, impacting their usefulness in many practical situations. A new type-checking strategy, domain-driven unifying resolution, is identified as an approach to solve these problems. Domaindriven unifying resolution is simple, efficient, and practically useful. However, even with severe restrictions on instance definitions, it is not possible to guarantee that type-checking with unifying resolution terminates. This is in contrast with the naive generalization of single parameter resolution strategies. Domain-driven unifying resolution is guaranteed to terminate if the type class constraints are satisfiable; however satisfiability is undecidable even with severe restrictions on instance definitions. These results shed some light on ambiguity problems with multi-parameter type classes.
UR - http://www.scopus.com/inward/record.url?scp=0035994624&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035994624&partnerID=8YFLogxK
U2 - 10.1017/s0956796801004233
DO - 10.1017/s0956796801004233
M3 - Article
AN - SCOPUS:0035994624
SN - 0956-7968
VL - 12
SP - 133
EP - 158
JO - Journal of Functional Programming
JF - Journal of Functional Programming
IS - 2
ER -