Explicit binds: Effortless efficiency with and without trees

Tarmo Uustalu*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

We demonstrate a simple and robust program transformation technique that can improve asymptotic time complexity of data-manipulating programs (e.g., produce a linear-time list reversal function from the obvious quadratic one). In the version of the present paper, it applies to monadic inductive datatypes and can be stated in two flavors, through a datatype representation, with an explicit ("frozen") bind constructor and a special associated defining clause for the fold function, and in a functional form (generalized Church numerals), with a special definition of the bind function in terms of the build constructor. The technique explicates, systematizes, combines and scales a number of ideas known from the literature, achieving a new level of generality.

Original languageEnglish
Title of host publicationFunctional and Logic Programming - 11th International Symposium, FLOPS 2012, Proceedings
Pages317-331
Number of pages15
DOIs
Publication statusPublished - 2012
Event11th International Symposium onFunctional and Logic Programming, FLOPS 2012 - Kobe, Japan
Duration: 23 May 201225 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7294 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Symposium onFunctional and Logic Programming, FLOPS 2012
Country/TerritoryJapan
CityKobe
Period23/05/1225/05/12

Fingerprint

Dive into the research topics of 'Explicit binds: Effortless efficiency with and without trees'. Together they form a unique fingerprint.

Cite this