Sorting with Bialgebras and Distributive Laws

Accepted to the Workshop on Generic programming, Sept. 9, 2012, Copenhagen, Denmark.

PDF | BibTEX | Source

PDF | BibTEX | Source

Abstract

Sorting algorithms are an intrinsic part of functional programming
folklore as they exemplify algorithm design using folds and
unfolds. This has given rise to an informal notion of duality among
sorting algorithms: insertion sorts are dual to selection
sorts. Using bialgebras and distributive laws, we formalise this
notion within a categorical setting. We use types as a guiding force
in exposing the recursive structure of bubble, insertion, selection,
quick, tree, and heap sorts. 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.

Keywords

algorithm design,
sorting,
category theory,
bialgebras,
distributive laws,
paramorphisms,
apomorphisms