## Tail recursion via universal invariants

**C. Barry Jay**
*Abstract:* The iteration step of a recursion can be
modelled by a loop diagram in a category, with the result of the
recursion given by the colimit of the loop. For tail recursion on
lists this yields the familiar foldleft operation, whose properties
follow from the universal property of the colimit. By contrast, the
initial algebra approach to lists yields foldright, whose
implementation is often the less efficient of the two. Under mild
conditions, however, the two definitions of lists are
equivalent.

*LFCS report ECS-LFCS-91-151*

Previous |

Index |

Next