{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T07:46:37Z","timestamp":1759131997125},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGPLAN Not."],"published-print":{"date-parts":[[2005,5]]},"abstract":"<jats:p>\n            This paper explores some ideas concerning the time-analysis of functional programs defined by instantiating typical recursion patterns such as\n            <jats:italic>folds, unfolds<\/jats:italic>\n            , and\n            <jats:italic>hylomorphisms.<\/jats:italic>\n            The concepts in this paper are illustrated through a rich set of examples in the Haskell programming language. We concentrate on unfolds and folds (also known as anamorphisms and catamorphisms respectively) of recursively defined types, as well as the more general\n            <jats:italic>hylomorphism<\/jats:italic>\n            pattern. For the latter, we use as case-studies two famous sorting algorithms, mergesort and quicksort. Even though time analysis is not compositional, we argue that splitting functions to expose the explicit construction of the recursion tree and its later consumption helps with this analysis.\n          <\/jats:p>","DOI":"10.1145\/1071221.1071226","type":"journal-article","created":{"date-parts":[[2005,11,14]],"date-time":"2005-11-14T18:08:27Z","timestamp":1131991707000},"page":"45-54","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Recursion patterns and time-analysis"],"prefix":"10.1145","volume":"40","author":[{"given":"Manuel","family":"Barbosa","sequence":"first","affiliation":[{"name":"Universidade do Minho, Campus de Gualtar, Portugal"}]},{"given":"Alcino","family":"Cunha","sequence":"additional","affiliation":[{"name":"Universidade do Minho, Campus de Gualtar, Portugal"}]},{"given":"Jorge Sousa","family":"Pinto","sequence":"additional","affiliation":[{"name":"Universidade do Minho, Campus de Gualtar, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2005,5]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"LNCS","first-page":"1","volume-title":"3rd International Summer School on Advanced Functional Programming","author":"Augusteijn Lex","year":"1999"},{"key":"e_1_2_1_2_1","volume-title":"McGraw-Hill Higher Education","author":"Cormen Thomas H.","year":"2001"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 1st Scottish Functional Programming Workshop","author":"Gibbons J.","year":"1999"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/289423.289455"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/232627.232637"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(90)90023-7"},{"key":"e_1_2_1_7_1","volume-title":"Technical Report RUU-CS-90-4","author":"Meertens Lambert","year":"1990"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Erik\n       \n      Meijer Maarten\n       \n      Fokkinga and \n      \n      \n      Ross\n       \n      Paterson\n    .\n      \n  \n   \n  Functional programming with bananas lenses envelopes and barbed wire. In J. Hughes editor Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture (FPCA'91) volume \n  523\n   of \n  LNCS\n  . \n  Springer-Verlag 1991\n  .   Erik Meijer Maarten Fokkinga and Ross Paterson. Functional programming with bananas lenses envelopes and barbed wire. In J. Hughes editor Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture (FPCA'91) volume 523 of LNCS. Springer-Verlag 1991.","DOI":"10.1007\/3540543961_7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/5.4.495"}],"container-title":["ACM SIGPLAN Notices"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071221.1071226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:11:16Z","timestamp":1672243876000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071221.1071226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":9,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["10.1145\/1071221.1071226"],"URL":"https:\/\/doi.org\/10.1145\/1071221.1071226","relation":{},"ISSN":["0362-1340","1558-1160"],"issn-type":[{"value":"0362-1340","type":"print"},{"value":"1558-1160","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]},"assertion":[{"value":"2005-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}