Applicative shortcut fusion

Alberto Pardo

Instituto de Computación
Universidad de la República

Thursday, 2 June 2011, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

Abstract: Applicative functors, introduced by McBride and Paterson, provide a model of computational effects which generalise monads, but they favour an applicative programming style. In this talk we analyse shortcut fusion in the context of applicative computations. We provide a shortcut fusion rule for the elimination of intermediate data structures generated in applicative computations. Our rule exhibits, once more, the relevance and generality of traverse, a datatype-generic operator for defining traversals over data structures where, like a map function, an applicative action is applied to each element of a structure, threading the effects. Associated with the fusion rule, we introduce two combinators, ifold and ibuild, which model the uniform consumption and production of data structures under applicative computations.

(Joint work with German Delbianco and Mauro Jaskelioff, presented at TFP 2011).

Tarmo Uustalu
Last update 4.6.2011