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