A shortcut fusion rule for circular program calculation

João Paulo Fernandes, Alberto Pardo, João Saraiva

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Circular programs are a powerful technique to express multiple traversal algorithms as a single traversal function in a lazy setting. In this paper, we present a shortcut deforestation technique to calculate circular programs. The technique we propose takes as input the composition of two functions, such that the first builds an intermediate structure and some additional context information which are then processed by the second one, to produce the final result. Our transformation into circular programs achieves intermediate structure deforestation and multiple traversal elimination. Furthermore, the calculated programs preserve the termination properties of the original ones.

Original languageEnglish (US)
Title of host publicationHaskell'07
Subtitle of host publicationProceedings of the ACM SIGPLAN 2007 Haskell Workshop
Number of pages12
StatePublished - 2007
EventHaskell'07: 11th ACM SIGPLAN Haskell Workshop - Freiburg, Germany
Duration: Sep 30 2007Sep 30 2007

Publication series

NameHaskell'07: Proceedings of the ACM SIGPLAN 2007 Haskell Workshop


ConferenceHaskell'07: 11th ACM SIGPLAN Haskell Workshop


  • Circular programming
  • Deforestation
  • Program calculation
  • Shortcut fusion

ASJC Scopus subject areas

  • Signal Processing
  • Software
  • Theoretical Computer Science


Dive into the research topics of 'A shortcut fusion rule for circular program calculation'. Together they form a unique fingerprint.

Cite this