Combining Datatypes and Effects

Alberto Pardo (University de la Republica, Montevideo)

A common approach to modularization in functional programming is to construct complex functions as the composition of simpler ones. The programs so defined used to be easier to understand and maintain, but they are not necessarily efficient. The source of inefficiency is originated by the process of production/consumption of an intermediate data structure that is present in each functional composition. Under certain conditions, the intermediate data structure can be eliminated by the application of a program transformation technique, known as fusion, which transforms the involved functions into a single, more efficient one.

The compositional style of programming still holds in the presence of effects. For example, when the effects are modeled by monads, composition appears in the form of monad composition, which is based in turn on the way monadic computations are combined in sequence (i.e. the bind operator of the monad). However, the fusion techniques for purely functional programs fail in general when used for programs with effects. The reason is that programs with effects possess a pattern of recursion slightly different from that of purely functional programs.

In these lectures we see the development of fusion techniques for programs with effects. We mainly concentrate on effects modeled by monads, but we will also mention briefly other forms of modeling effects. Fusion techniques for purely functional programs are usually obtained from algebraic laws associated with common patterns of computation associated on recursive datatypes, like fold, unfold or the combination of both (called hylomorphism). We show that the same strategy can be used in the context of effects. In fact, we introduce monadic versions of fold, unfold and hylomorphism and derivate new fusion cases from their algebraic laws. The aim of this course is not only to show the theoretical side of the fusion technique, but also to illustrate how this technique may impact in practice. In this sense, we plan to show in action a experimental tool that allows us to apply fusion both to purely functional programs and to programs with effects.

Last Update 12 July 2004