{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T14:01:03Z","timestamp":1770040863887,"version":"3.49.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[1999,9,1]],"date-time":"1999-09-01T00:00:00Z","timestamp":936144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[1999,9]]},"abstract":"<jats:title>Abstract.<\/jats:title>\n          <jats:p>Nested datatypes generalise regular datatypes in much the same way that context-free languages generalise regular ones. Although the categorical semantics of nested types turns out to be similar to the regular case, the fold functions are more limited because they can only describe natural transformations. Practical considerations therefore dictate the introduction of a generalised fold function in which this limitation can be overcome. In the paper we show how to construct generalised folds systematically for each nested datatype, and show that they possess a uniqueness property analogous to that of ordinary folds. As a consequence, generalised folds satisfy fusion properties similar to those developed for regular datatypes. Such properties form the core of an effective calculational theory of inductive datatypes.<\/jats:p>","DOI":"10.1007\/s001650050047","type":"journal-article","created":{"date-parts":[[2002,8,25]],"date-time":"2002-08-25T09:25:39Z","timestamp":1030267539000},"page":"200-222","source":"Crossref","is-referenced-by-count":58,"title":["Generalised folds for nested datatypes"],"prefix":"10.1145","volume":"11","author":[{"given":"Richard","family":"Bird","sequence":"first","affiliation":[{"name":"Programming Research Group, Oxford University, Oxford, UK, , , , , , UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ross","family":"Paterson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University, London, UK, , , , , , UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"p_1","volume-title":"Algebra of Programming","author":"Bird R.","year":"1997"},{"key":"p_2","volume-title":"Introduction to Functional Programming using Haskell","author":"Bird R.","year":"1998"},{"key":"p_3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/BFb0054285","volume-title":"Mathematics of Program Construction","author":"Bird R. S.","year":"1998"},{"issue":"1","key":"p_4","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1017\/S0956796899003366","article-title":"De Bruijn notation as a nested datatype","volume":"9","author":"Bird R.","year":"1999","journal-title":"Journal of Functional Programming"},{"issue":"3","key":"p_5","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1017\/S0960129500000803","article-title":"A generalisation of the trie data structure","volume":"5","author":"Connelly R. H.","year":"1995","journal-title":"Mathematical Structures in Computer Science"},{"key":"p_6","volume-title":"ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation","author":"Fegaras L.","year":"1994"},{"key":"p_9","volume-title":"A technical summary of the new features in Hugs 1.3c","author":"Jones M.","year":"1998"},{"key":"p_10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/3-540-56625-2_15","volume-title":"Mathematics of Program Construction","author":"Jones G.","year":"1993"},{"key":"p_11","doi-asserted-by":"crossref","first-page":"337","DOI":"10.4153\/CMB-1970-065-6","volume":"13","author":"Lambek L.","year":"1970","journal-title":"Canadian Mathematical Bulletin"},{"key":"p_12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4962-7","volume-title":"Algebraic Approaches to Program Semantics. Texts and Monographs in Computing Science","author":"Manes E. G.","year":"1986"},{"key":"p_13","volume-title":"Categories for the Working Mathematician","author":"Mac Lane S.","year":"1971"},{"issue":"2","key":"p_15","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 G. R.","year":"1990","journal-title":"Science of Computer Programming"},{"key":"p_16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-13346-1_15","volume-title":"Semantics of Data Types","author":"McCracken N. J.","year":"1984"},{"key":"p_17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511530104","volume-title":"Purely Functional Data Structures","author":"Okasaki C.","year":"1998"},{"key":"p_18","volume-title":"Explicit quantification in Haskell","author":"Peyton Jones S.","year":"1997"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s001650050047.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s001650050047\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s001650050047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:27:36Z","timestamp":1641482856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s001650050047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,9]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1999,9]]}},"alternative-id":["10.1007\/s001650050047"],"URL":"https:\/\/doi.org\/10.1007\/s001650050047","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,9]]}}}