Sound and decidable type inference for functional dependencies

Gregory J. Duck, Simon Peyton-Jones, Peter J. Stuckey, Martin Sulzmann

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

13 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProgramming Languages and Systems
Subtitle of host publication13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings
EditorsDavid Schmidt
Place of PublicationBerlin Germany
Number of pages15
ISBN (Print)3540213139
Publication statusPublished - 1 Dec 2004
Externally publishedYes
EventEuropean Symposium on Programming 2004 - Barcelona, Spain
Duration: 29 Mar 20042 Apr 2004
Conference number: 13th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceEuropean Symposium on Programming 2004
Abbreviated titleESOP 2004
Internet address

Cite this