Conference item icon

Conference item

Sorting with bialgebras and distributive laws

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...

Expand abstract

Actions


Access Document


Publisher copy:
10.1145/2364394.2364405

Authors


Publisher:
ACM
Publication date:
2012-01-01
DOI:
URN:
uuid:fdf11970-d9d2-4528-a372-7d80d2e91304
Local pid:
cs:8032
ISBN:
978-1-4503-1576-0

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP