{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:00:52Z","timestamp":1754193652130},"reference-count":44,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2004,5,1]],"date-time":"2004-05-01T00:00:00Z","timestamp":1083369600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3400,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Science of Computer Programming"],"published-print":{"date-parts":[[2004,5]]},"DOI":"10.1016\/j.scico.2003.07.001","type":"journal-article","created":{"date-parts":[[2004,3,29]],"date-time":"2004-03-29T00:36:12Z","timestamp":1080520572000},"page":"117-151","source":"Crossref","is-referenced-by-count":38,"title":["Type-indexed data types"],"prefix":"10.1016","volume":"51","author":[{"given":"Ralf","family":"Hinze","sequence":"first","affiliation":[]},{"given":"Johan","family":"Jeuring","sequence":"additional","affiliation":[]},{"given":"Andres","family":"L\u00f6h","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.scico.2003.07.001_BIB1","doi-asserted-by":"crossref","unstructured":"M. Abott, T. Altenkirch, N. Ghani, C. McBride, Derivatives of containers, in: Typed Lambda Calculi and Applications, TLCA 2003, Lecture Notes in Computer Science, vol. 2701, Springer, Berlin, 2003, pp. 16\u201330.","DOI":"10.1007\/3-540-44904-3_2"},{"key":"10.1016\/j.scico.2003.07.001_BIB2","unstructured":"L. Augustsson, D. Barton, B. Boutel, W. Burton, S. Fraser, J. Fasel, K. Hammond, R. Hinze, P. Hudak, T. Johnsson, M. Jones, J. Launchbury, E. Meijer, J. Peterson, A. Reid, C. Runciman, P. Wadler, in: S.P. Jones J. Hughes (Eds.), Haskell 98\u2014A Non-Strict, Purely Functional Language (February 1999), available from http:\/\/www.haskell.org\/definition\/."},{"key":"10.1016\/j.scico.2003.07.001_BIB3","series-title":"Advanced Functional Programming","first-page":"28","article-title":"Generic programming: an introduction","volume":"vol. 1608","author":"Backhouse","year":"1999"},{"issue":"1","key":"10.1016\/j.scico.2003.07.001_BIB4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0956796800001556","article-title":"Generic functional programming with types and relations","volume":"6","author":"Bird","year":"1996","journal-title":"J. Funct. Program."},{"key":"10.1016\/j.scico.2003.07.001_BIB5","doi-asserted-by":"crossref","unstructured":"M.M.T. Chakravarty, G. Keller, More types for nested data parallel programming, in: Proc. ICFP 2000: Internat. Conf. on Functional Programming, ACM Press, New York, 2000, pp. 94\u2013105.","DOI":"10.1145\/351240.351249"},{"key":"10.1016\/j.scico.2003.07.001_BIB6","unstructured":"K. Claessen, P. Ljungl\u00f6f, Typed logical variables in Haskell, in: Proc. Haskell Workshop 2000, 2000."},{"key":"10.1016\/j.scico.2003.07.001_BIB7","doi-asserted-by":"crossref","unstructured":"D. Clarke, A. L\u00f6h, Generic Haskell, specifically, in: J. Gibbons, J. Jeuring (Eds.), Generic Programming, IFIP, vol. 243, Kluwer Academic Publishers, Dordrecht, 2003, pp. 21\u201348.","DOI":"10.1007\/978-0-387-35672-3_2"},{"key":"10.1016\/j.scico.2003.07.001_BIB8","doi-asserted-by":"crossref","unstructured":"K. Crary, S. Weirich, Flexible type analysis, in: Proc. ICFP 1999: Internat. Conf. on Functional Programming, ACM Press, New York, 1999, pp. 233\u2013248, URL citeseer.nj.nec.com\/crary99flexible.html","DOI":"10.1145\/317636.317906"},{"key":"10.1016\/j.scico.2003.07.001_BIB9","doi-asserted-by":"crossref","unstructured":"K. Crary, S. Weirich, J.G. Morrisett, Intensional polymorphism in type-erasure semantics, in: Proc. ICFP 1998: Internat. Conf. on Functional Programming, ACM Press, New York, 1998, pp. 301\u2013312.","DOI":"10.1145\/289423.289459"},{"key":"10.1016\/j.scico.2003.07.001_BIB10","doi-asserted-by":"crossref","unstructured":"C. Dubois, F. Rouaix, P. Weis, Extensional polymorphism, in: 22nd Symp. on Principles of Programming Languages, POPL \u201995, 1995, pp. 118\u2013129.","DOI":"10.1145\/199448.199473"},{"key":"10.1016\/j.scico.2003.07.001_BIB11","unstructured":"M. Fokkinga, Law and order in algorithmics, Ph.D. Thesis, Dept. INF, University of Twente, Enschede, The Netherlands, 1992."},{"key":"10.1016\/j.scico.2003.07.001_BIB12","doi-asserted-by":"crossref","unstructured":"J. Gibbons, Polytypic downwards accumulations, in: Proc. of Mathematics of Program Construction, Lecture Notes in Computer Science, vol. 1422, Springer, Berlin, 1998, pp. 207\u2013233.","DOI":"10.1007\/BFb0054292"},{"key":"10.1016\/j.scico.2003.07.001_BIB13","unstructured":"P. Hagg, A framework for developing generic XML Tools, Master's Thesis, Department of Information and Computing Sciences, Utrecht University, 2002."},{"key":"10.1016\/j.scico.2003.07.001_BIB14","doi-asserted-by":"crossref","unstructured":"R. Harper, G. Morrisett, Compiling polymorphism using intensional type analysis, in: 22nd Symp. Principles of Programming Languages, POPL \u201995, 1995, pp. 130\u2013141.","DOI":"10.1145\/199448.199475"},{"key":"10.1016\/j.scico.2003.07.001_BIB15","doi-asserted-by":"crossref","unstructured":"R. Hinze, Generalizing generalized tries, J. Funct. Program. 10(4) (2000) 327\u2013351, URL citeseer.nj.nec.com\/hinze99generalizing.html","DOI":"10.1017\/S0956796800003713"},{"key":"10.1016\/j.scico.2003.07.001_BIB16","doi-asserted-by":"crossref","unstructured":"R. Hinze, A new approach to generic functional programming, in: Conf. Record of POPL \u201900: The 27th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, ACM Press, New York, 2000, pp. 119\u2013132, URL citeseer.nj.nec.com\/hinze99new.html","DOI":"10.1145\/325694.325709"},{"key":"10.1016\/j.scico.2003.07.001_BIB17","series-title":"Mathematics of Program Construction","first-page":"2","article-title":"Polytypic values possess polykinded types","volume":"vol. 1837","author":"Hinze","year":"2000"},{"key":"10.1016\/j.scico.2003.07.001_BIB18","unstructured":"R. Hinze, Generic Programs and Proofs, Habilitationsschrift, Bonn University, 2000."},{"key":"10.1016\/j.scico.2003.07.001_BIB19","doi-asserted-by":"crossref","unstructured":"R. Hinze, J. Jeuring, Generic Haskell: Applications, in: R. Backhouse, J. Gibbons (Eds.), Generic Programming, Lecture Notes in Computer Science, vol. 2793, Springer, Berlin, 2003, pp. 57\u201397.","DOI":"10.1007\/978-3-540-45191-4_2"},{"key":"10.1016\/j.scico.2003.07.001_BIB20","doi-asserted-by":"crossref","unstructured":"R. Hinze, S. P Jones, Derivable type classes, in: G. Hutton (Ed.), Proc. 2000 ACM SIGPLAN Haskell Workshop, Electronic Notes in Theoretical Computer Science, vol. 41.1, Elsevier, Amsterdam, 2001, the preliminary proc. appeared as a University of Nottingham technical report.","DOI":"10.1016\/S1571-0661(05)80542-0"},{"key":"10.1016\/j.scico.2003.07.001_BIB21","doi-asserted-by":"crossref","unstructured":"R. Hinze, J. Jeuring, A. L\u00f6h, Type-indexed data types, in: Proc. 6th Mathematics of Program Construction Conf. MPC\u201902, Lecture Notes in Computer Science, vol. 2386, 2002, pp. 148\u2013174.","DOI":"10.1007\/3-540-45442-X_10"},{"issue":"5","key":"10.1016\/j.scico.2003.07.001_BIB22","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1017\/S0956796897002864","article-title":"The zipper","volume":"7","author":"Huet","year":"1997","journal-title":"J. Funct. Program."},{"key":"10.1016\/j.scico.2003.07.001_BIB23","series-title":"Thirty Five Years of Automating Mathematics","article-title":"Linear contexts and the sharing functor: techniques for symbolic computation","author":"Huet","year":"2003"},{"key":"10.1016\/j.scico.2003.07.001_BIB24","unstructured":"P. Jansson, The WWW home page for polytypic programming, available from http:\/\/www.cs.chalmers.se\/~patrikj\/poly\/ (2001)."},{"key":"10.1016\/j.scico.2003.07.001_BIB25","unstructured":"P. Jansson, J. Jeuring, PolyP\u2014a polytypic programming language extension, in: Conf. Record of POPL\u201997: The 24th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, ACM Press, New York, 1997, pp. 470\u2013482."},{"issue":"5","key":"10.1016\/j.scico.2003.07.001_BIB26","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1017\/S095679689800313X","article-title":"Functional pearl","volume":"8","author":"Jansson","year":"1998","journal-title":"J. Funct. Program."},{"key":"10.1016\/j.scico.2003.07.001_BIB27","unstructured":"P. Jansson, J. Jeuring, A framework for polytypic programming on terms, with an application to rewriting, in: J. Jeuring (Ed.), Workshop on Generic Programming 2000, Ponte de Lima, Portugal, July 2000, 2000, pp. 33\u201345; Utrecht Technical Report UU-CS-2000-19."},{"issue":"6","key":"10.1016\/j.scico.2003.07.001_BIB28","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1017\/S0956796898003128","article-title":"Functorial ML","volume":"8","author":"Jay","year":"1998","journal-title":"J. Funct. Program."},{"key":"10.1016\/j.scico.2003.07.001_BIB29","doi-asserted-by":"crossref","unstructured":"J. Jeuring, Polytypic pattern matching, in: Conference Record of FPCA\u201995, SIGPLAN-SIGARCH-WG2.8 Conf. on Functional Programming Languages and Computer Architecture, ACM Press, New York, 1995, pp. 238\u2013248.","DOI":"10.1145\/224164.224212"},{"key":"10.1016\/j.scico.2003.07.001_BIB30","doi-asserted-by":"crossref","unstructured":"M.P. Jones, Type classes with functional dependencies, in: G. Smolka (Ed.), Proc. 9th European Symp. on Programming, ESOP 2000, Berlin, Germany, Lecture Notes in Computer Science, vol. 1782, Springer, Berlin, 2000, pp. 230\u2013244.","DOI":"10.1007\/3-540-46425-5_15"},{"key":"10.1016\/j.scico.2003.07.001_BIB31","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast pattern matching in strings","volume":"6","author":"Knuth","year":"1978","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.scico.2003.07.001_BIB32","unstructured":"R. L\u00e4mmel, W. Lohmann, Format Evolution, in: J. Kouloumdjian, H. Mayr, A. Erkollar (Eds.), Proc. 7th Internat. Conf. on Reverse Engineering for Information Systems (RETIS 2001), books@ocg.at, vol. 155, OCG, 2001, pp. 113\u2013134."},{"key":"10.1016\/j.scico.2003.07.001_BIB33","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0167-6423(90)90023-7","article-title":"Data structures and program transformation","volume":"14","author":"Malcolm","year":"1990","journal-title":"Sci. Comput. Program."},{"key":"10.1016\/j.scico.2003.07.001_BIB34","unstructured":"C. McBride, The derivative of a regular type is its type of one-hole contexts, 2001, unpublished manuscript."},{"key":"10.1016\/j.scico.2003.07.001_BIB35","unstructured":"N.J. McCracken, An investigation of a programming language with a polymorphic type structure, Ph.D. Thesis, Syracuse University, 1979."},{"issue":"5","key":"10.1016\/j.scico.2003.07.001_BIB36","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01211391","article-title":"Paramorphisms","volume":"4","author":"Meertens","year":"1992","journal-title":"Formal Aspects Comput."},{"key":"10.1016\/j.scico.2003.07.001_BIB37","series-title":"FPCA\u201991: Functional Programming Languages and Computer Architecture","first-page":"124","article-title":"Functional programming with bananas, lenses, envelopes, and barbed wire","volume":"vol. 523","author":"Meijer","year":"1991"},{"key":"10.1016\/j.scico.2003.07.001_BIB38","series-title":"Foundations for Programming Languages","author":"Mitchell","year":"1996"},{"key":"10.1016\/j.scico.2003.07.001_BIB39","doi-asserted-by":"crossref","unstructured":"V. Trifonov, B. Saha, Z. Shao, Fully reflexive intensional type analysis, in: Proc. ICFP 2000: Internat. Conf. on Functional Programming, ACM Press, New York, 2000, pp. 82\u201393, URL citeseer.nj.nec.com\/saha00fully.html","DOI":"10.1145\/351240.351248"},{"key":"10.1016\/j.scico.2003.07.001_BIB40","unstructured":"M. Vestin, Genetic algorithms in Haskell with polytypic programming, Examensarbeten 1997:36, G\u00f6teborg University, Gothenburg, Sweden, available from the Polytypic programming WWW page [23] (1997)."},{"key":"10.1016\/j.scico.2003.07.001_BIB41","doi-asserted-by":"crossref","unstructured":"S. Weirich, Encoding intensional type analysis, in: European Symp. on Programming, Lecture Notes in Computer Science, vol. 2028, Springer, Berlin, 2001, pp. 92\u2013106, URL http:\/\/link.springer.de\/link\/service\/series\/0558\/tocs\/t%2028.htm","DOI":"10.1007\/3-540-45309-1_7"},{"key":"10.1016\/j.scico.2003.07.001_BIB42","doi-asserted-by":"crossref","unstructured":"S. Weirich, Higher-order intensional type analysis, in: D. Le M\u00e9tayer (Ed.), Proc. 11th European Symp. on Programming, ESOP 2002, Lecture Notes in Computer Science, vol. 2305, 2002, pp. 98\u2013114.","DOI":"10.1007\/3-540-45927-8_8"},{"key":"10.1016\/j.scico.2003.07.001_BIB43","unstructured":"J. de Wit, A technical overview of Generic Haskell, Master's Thesis, Department of Information and Computing Sciences, Utrecht University, 2002."},{"key":"10.1016\/j.scico.2003.07.001_BIB44","doi-asserted-by":"crossref","unstructured":"Z. Yang, Encoding types in ML-like languages, in: Proc. ICFP 1998: Internat. Conf. on Functional Programming, ACM Press, New York, 1998, pp. 289\u2013300, URLciteseer.nj.nec.com\/zhe99encoding.html","DOI":"10.1145\/289423.289458"}],"container-title":["Science of Computer Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167642304000152?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167642304000152?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T10:51:35Z","timestamp":1550141495000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167642304000152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,5]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2004,5]]}},"alternative-id":["S0167642304000152"],"URL":"https:\/\/doi.org\/10.1016\/j.scico.2003.07.001","relation":{},"ISSN":["0167-6423"],"issn-type":[{"value":"0167-6423","type":"print"}],"subject":[],"published":{"date-parts":[[2004,5]]}}}