Two papers about understanding functional dependencies. The former is
a completely-rewritten journal version of the latter.
Functional dependencies are a popular and useful extension to Haskell style type classes.
In this paper, we give a reformulation of functional dependencies in terms of
Constraint Handling Rules (CHRs). In previous work, CHRs have been employed
for describing user-programmable type extensions in the context of Haskell style
type classes. Here, we make use of CHRs to provide for the first time
a concise result that under some sufficient conditions,
functional dependencies allow for sound, complete and decidable type inference.
The sufficient conditions imposed on functional dependencies can be very limiting.
We show how to safely relax these conditions and suggest several sound
extensions of functional dependencies.
Our results allow for a better understanding of functional dependencies
and open up the opportunity for new applications.
Understanding functional dependencies via Constraint Handling Rules,
Martin Sulzmann, Gregory J. Duck, Simon Peyton Jones, and Peter J. Stuckey.
To appear in the Journal of Functional Programming.
- Sound and Decidable Type Inference for Functional Dependencies,
Gregory J. Duck, Simon Peyton Jones, Peter J. Stuckey, and Martin Sulzmann,
European Symposium on Programming 2004 (ESOP'04).