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.
Previous | Index | Next An error occured whilst processing this directive