Concatenate, Reverse and Map Vanish For Free

The paper is available via the ACM DL Author-ize feature:

ACM DL Author-ize service Concatenate, Reverse and Map Vanish For Free

Author: J. Voigtländer
Published: In 7th International Conference on Functional Programming (ICFP'02, acceptance rate 24/76), Pittsburgh, Pennsylvania, Proceedings, volume 37(9) of SIGPLAN Notices, pages 14-25, ACM, October 2002.
DOI: 10.1145/583852.581481
BibTeX: Voi02c.bib
Abstract: We introduce a new transformation method to eliminate intermediate data structures occurring in functional programs due to repeated list concatenations and other data manipulations (additionally exemplified with list reversal and mapping of functions over lists). The general idea is to uniformly abstract from data constructors and manipulating operations by means of rank-2 polymorphic combinators that exploit algebraic properties of these operations to provide an optimized implementation. The correctness of transformations is proved by using the free theorems derivable from parametric polymorphic types.
Download: http://dl.acm.org/authorize?24993 (free)
Slides: Slides of my talk at the conference are here.