Recursion patterns and time-analysis

• Tipo: Artigo em Revista Científica Internacional
• Data: 2005

Autores

Barbosa, A (Autor) Outra; Cunha, A (Autor) Outra; Pinto, JS (Autor) Outra

Revista

Título: SIGPLAN Notices (ACM Special Interest Group on Programming Languages)

Vol. 40

Páginas: 45-54

ISSN: 0362-1340

Editora: Special Interest Group on Computer Graphics, Association for Computing Machinery

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-000-3DM

DOI: 10.1145/1071221.1071226

Abstract (EN): This paper explores sonic 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 10