Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/2762
Título: | Recursion patterns and time-analysis |
Autor(es): | Barbosa, Manuel Cunha, Alcino Pinto, Jorge Sousa |
Palavras-chave: | Functional programming Time analysis Recursion patterns |
Data: | Mai-2005 |
Editora: | Association for Computing Machinery |
Revista: | ACM SIGPLAN Notices |
Citação: | "ACM Sigplan Notices". ISSN 0362-1340. 40:5 (2005) 45-54. |
Resumo(s): | This paper explores some ideas concerning the time-analysis of functional programs defined by instantiating typical recursion patterns such as folds, unfolds, and hylomorphisms. 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 hylomorphism 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. |
Tipo: | Artigo |
URI: | https://hdl.handle.net/1822/2762 |
DOI: | 10.1145/1071221.1071226 |
ISSN: | 0362-1340 |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: | HASLab - Artigos em revistas internacionais DI/CCTC - Artigos (papers) |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
recpta-final.pdf | 269,34 kB | Adobe PDF | Ver/Abrir |