Sorting with Bialgebras and Distributive Laws

Abstract

Sorting algorithms are an intrinsic part of functional programming folklore because they exemplify algorithm design using folds and unfolds. This has given rise to an informal notion of duality among sorting algorithms. In this paper, we formalise this notion using bialgebras and distributive laws, within a categorical setting. We use types as a guiding force in exposing the recursive structure of insertion, selection, quick, tree, and heap sort. Moreover, we show how to distill the computational essence of these algorithms down to one-step operations that are expressed as natural transformations. From this vantage point, the duality is clear, and one side of the algorithmic coin will neatly lead us to the other, "for free". As an optimisation, the approach is also extended to paramorphisms and apomorphisms, which allow for more efficient implementations of these algorithms than the corresponding folds and unfolds.