{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:02Z","timestamp":1750308602433,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1704041, CNS-1422979"],"award-info":[{"award-number":["CCF-1704041, CNS-1422979"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>Functional programming languages assume that type constructors are total. Yet functional programmers know better: counterexamples range from container types that make limiting assumptions about their contents (e.g., requiring computable equality or ordering functions) to type families with defining equations only over certain choices of arguments. We present a language design and formal theory of partial type constructors, capturing the domains of type constructors using qualified types. Our design is both simple and expressive: we support partial datatypes as first-class citizens (including as instances of parametric abstractions, such as the Haskell Functor and Monad classes), and show a simple type elaboration algorithm that avoids placing undue annotation burden on programmers. We show that our type system rejects ill-defined types and can be compiled to a semantic model based on System F. Finally, we have conducted an experimental analysis of a body of Haskell code, using a proof-of-concept implementation of our system; while there are cases where our system requires additional annotations, these cases are rarely encountered in practical Haskell code.<\/jats:p>","DOI":"10.1145\/3371108","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T19:45:25Z","timestamp":1576871125000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Partial type constructors: or, making ad hoc datatypes less ad hoc"],"prefix":"10.1145","volume":"4","author":[{"given":"Mark P.","family":"Jones","sequence":"first","affiliation":[{"name":"Portland State University, USA"}]},{"given":"J. Garrett","family":"Morris","sequence":"additional","affiliation":[{"name":"University of Kansas, USA"}]},{"given":"Richard A.","family":"Eisenberg","sequence":"additional","affiliation":[{"name":"Bryn Mawr College, USA \/ Tweag I\/O, UK"}]}],"member":"320","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122955.3122967"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129514000115"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/286936.286957"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/6041.6042"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040306"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2266170"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u201906)","author":"Reis Gabriel Dos","year":"2006","unstructured":"Gabriel Dos Reis and Bjarne Stroustrup . 2006 . Specifying C++ Concepts . In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u201906) . ACM, New York, NY, USA, 295\u2013308. Gabriel Dos Reis and Bjarne Stroustrup. 2006. Specifying C++ Concepts. In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL \u201906). ACM, New York, NY, USA, 295\u2013308."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331545.3342594"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190216.1190229"},{"key":"e_1_2_2_11_1","volume-title":"Jones","author":"Gaster Benedict R.","year":"1996","unstructured":"Benedict R. Gaster and Mark P . Jones . 1996 . A Polymorphic Type System for Extensible Records and Variants. Technical Report NOT TCS-TR-96-3. University of Nottingham . Benedict R. Gaster and Mark P. Jones. 1996. A Polymorphic Type System for Extensible Records and Variants. Technical Report NOT TCS-TR-96-3. University of Nottingham."},{"key":"e_1_2_2_12_1","unstructured":"GHC Team. 2017. GHC User\u2019s Guide Documentation. http:\/\/www.haskell.org\/ghc\/docs\/latest\/users_guide.pdf .  GHC Team. 2017. GHC User\u2019s Guide Documentation. http:\/\/www.haskell.org\/ghc\/docs\/latest\/users_guide.pdf ."},{"key":"e_1_2_2_13_1","volume-title":"Simon Peyton Jones","author":"Hudak Paul","year":"1991","unstructured":"Paul Hudak , Simon Peyton Jones , and Philip Wadler (Eds.). 1991 . Report on the Programming Language Haskell, Version 1.1. Available from http:\/\/haskell.org\/definition\/haskell- report- 1.1.tar.gz . Paul Hudak, Simon Peyton Jones, and Philip Wadler (Eds.). 1991. Report on the Programming Language Haskell, Version 1.1. Available from http:\/\/haskell.org\/definition\/haskell- report- 1.1.tar.gz ."},{"key":"e_1_2_2_14_1","unstructured":"Paul Hudak and Philip Wadler (Eds.). 1990. Report on the Programming Language Haskell Version 1.0. Available from http:\/\/haskell.org\/definition\/haskell- report- 1.0.ps.gz .  Paul Hudak and Philip Wadler (Eds.). 1990. Report on the Programming Language Haskell Version 1.0. Available from http:\/\/haskell.org\/definition\/haskell- report- 1.0.ps.gz ."},{"key":"e_1_2_2_16_1","volume-title":"Proceedings of the 1999 Haskell Workshop","author":"Hughes John","year":"1999","unstructured":"John Hughes . 1999 . Restricted Data Types in Haskell . In Proceedings of the 1999 Haskell Workshop . University of Utrecht, Technical Report UU-CS- 1999-28, Paris, France, 83\u2013100. John Hughes. 1999. Restricted Data Types in Haskell. In Proceedings of the 1999 Haskell Workshop. University of Utrecht, Technical Report UU-CS-1999-28, Paris, France, 83\u2013100."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165190"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511663086"},{"volume-title":"First International Spring School on Advanced Functional Programming Techniques (Lecture Notes in Computer Science)","author":"Jones Mark P.","key":"e_1_2_2_20_1","unstructured":"Mark P. Jones . 1995a. Functional Programming with Overloading and Higher-Order Polymorphism . In First International Spring School on Advanced Functional Programming Techniques (Lecture Notes in Computer Science) , Vol. 925 . Springer , Berlin Heidelberg , 97\u2013136. Mark P. Jones. 1995a. Functional Programming with Overloading and Higher-Order Polymorphism. In First International Spring School on Advanced Functional Programming Techniques (Lecture Notes in Computer Science), Vol. 925. Springer, Berlin Heidelberg, 97\u2013136."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/224164.224198"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46425-5_15"},{"key":"e_1_2_2_23_1","unstructured":"Oleg Kiselyov. 2007. Haskell with only one type class. http:\/\/okmij.org\/ftp\/Haskell\/Haskell1\/Haskell1.txt .  Oleg Kiselyov. 2007. Haskell with only one type class. http:\/\/okmij.org\/ftp\/Haskell\/Haskell1\/Haskell1.txt ."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341706"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61055-3_38"},{"key":"e_1_2_2_26_1","unstructured":"Simon Marlow (Ed.). 2010. Haskell 2010 Language Report. Available online in HTML and pdf formats from https: \/\/www.haskell.org\/documentation .  Simon Marlow (Ed.). 2010. Haskell 2010 Language Report. Available online in HTML and pdf formats from https: \/\/www.haskell.org\/documentation ."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449798"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110286"},{"key":"e_1_2_2_29_1","volume-title":"POPL","author":"Garrett Morris J.","year":"2019","unstructured":"J. Garrett Morris and James McKinna . 2019. Abstracting extensible data types: or, rows by any other name. PACMPL 3 , POPL ( 2019 ), 12:1\u201312:28. https:\/\/dl.acm.org\/citation.cfm?id=3290325 J. Garrett Morris and James McKinna. 2019. Abstracting extensible data types: or, rows by any other name. PACMPL 3, POPL (2019), 12:1\u201312:28. https:\/\/dl.acm.org\/citation.cfm?id=3290325"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12251-4_6"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34407-7_6"},{"key":"e_1_2_2_32_1","unstructured":"Simon Peyton Jones. 1991. Contexts in data and type. http:\/\/code.haskell.org\/~dons\/haskell- 1990- 2000\/msg00072.html .  Simon Peyton Jones. 1991. Contexts in data and type. http:\/\/code.haskell.org\/~dons\/haskell- 1990- 2000\/msg00072.html ."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411215"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596550.1596599"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0061839"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500602"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2804302.2804314"},{"volume-title":"The Design and Evolution of C++","author":"Stroustrup Bjarne","key":"e_1_2_2_38_1","unstructured":"Bjarne Stroustrup . 1994. The Design and Evolution of C++ . Addison-Wesley , Boston, MA . Bjarne Stroustrup. 1994. The Design and Evolution of C++. Addison-Wesley, Boston, MA."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1190315.1190324"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500611"},{"volume-title":"Practical Aspects of Declarative Languages","author":"Winant Thomas","key":"e_1_2_2_42_1","unstructured":"Thomas Winant , Dominique Devriese , Frank Piessens , and Tom Schrijvers . 2014. Partial Type Signatures for Haskell . In Practical Aspects of Declarative Languages , Vol. 8324 . Springer International Publishing , 17\u201332. Thomas Winant, Dominique Devriese, Frank Piessens, and Tom Schrijvers. 2014. Partial Type Signatures for Haskell. In Practical Aspects of Declarative Languages, Vol. 8324. Springer International Publishing, 17\u201332."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1093"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604150"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371108","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:43Z","timestamp":1750273543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":40,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1145\/3371108"],"URL":"https:\/\/doi.org\/10.1145\/3371108","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"2019-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}