Abstract
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 and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abdennadher, S.: Operational semantics and confluence of constraint propagation rules. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 252–266. Springer, Heidelberg (1997)
Chen, K., Hudak, P., Odersky, M.: Parametric type classes. In: Proc. of ACM Conference on Lisp and Functional Programming, June 1992, pp. 170–191. ACM Press, New York (1992)
Chakravarty, M., Keller, S.: Classy type analysis (2003)
Duggan, D., Ophel, J.: Type-checking multi-parameter type classes. Journal of Functional Programming 12(2), 133–158 (2002)
Duck, G.J., Peyton-Jones, S., Stuckey, P.J., Sulzmann, M.: Sound and decidable type inference for functional dependencies. Technical report, National University of Singapore (2003); http://www.comp.nus.edu.sg/~sulzmann/chr/download/fd-chr.ps.gz
Frühwirth, T.: Constraint handling rules. In: Podelski, A. (ed.) Constraint Programming: Basics and Trends. LNCS, vol. 910. Springer, Heidelberg (1995)
Frühwirth, T.: Theory and practice of constraint handling rules. Journal of Logic Programming 37(1-3), 95–138 (1998)
Jones, M.P.: Qualified Types: Theory and Practice. PhD thesis, Oxford University (September 1992)
Jones, M.P.: Simplifying and improving qualified types. In: FPCA 1995: Conference on Functional Programming Languages and Computer Architecture. ACM Press, New York (1995)
Jones, M.P.: Type classes with functional dependencies. In: Smolka, G. (ed.) ESOP 2000. LNCS, vol. 1782, p. 230. Springer, Heidelberg (2000)
Karczmarczuk, J.: Structure and interpretation of quantum mechanics – a functional framework. In: Proc. of Haskell Workshop 2003, pp. 50–61. ACM Press, New York (2003)
Peyton Jones, S., et al.: Report on the programming language Haskell 98 (February 1999), http://haskell.org
Stuckey, P.J., Sulzmann, M.: A theory of overloading. In: Proc. of ICFP 2002, pp. 167–178. ACM Press, New York (2002)
Washburn, G., Weirich, S.: Boxes go bananas: encoding higher-order abstract syntax with parametric polymorphism. In: Proc. of ICFP 2003, pp. 249–262. ACM Press, New York (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duck, G.J., Peyton-Jones, S., Stuckey, P.J., Sulzmann, M. (2004). Sound and Decidable Type Inference for Functional Dependencies. In: Schmidt, D. (eds) Programming Languages and Systems. ESOP 2004. Lecture Notes in Computer Science, vol 2986. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24725-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-24725-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21313-0
Online ISBN: 978-3-540-24725-8
eBook Packages: Springer Book Archive