Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Fritz Henglein

LFCS Seminar: Fritz Henglein

— filed under:

Towards generic distributive sorting and searching

  • LFCS Seminar
When Jun 27, 2013
from 04:00 PM to 05:00 PM
Where IF 4.31-33
Add event to calendar vCal

Comparison-based sorting algorithms and search trees are easily made generic by abstraction over the comparison function used. This has arguably contributed to their popularity even though distributive (radix/trie-like) and hashing techniques often have superior performance for special datatypes, such as for machine integers and character strings.
In this talk we show how to construct generic comparison, sorting, discrimination and trie building functions by structural recursion over a class of order representations, which includes constructions such as lexicographic ordering and the order on the domain of a function induced by the order on its codomain.   Sorting can be thought of as LSD radix sorting, discrimination as MSD radix sorting, and trie building as radix tree (trie) construction, but generalized to user-definable orders over arbitrary first-order and recursive types.

Trie building yields a data structure not only asymptotically as efficiently as discrimination (for standard orders worst-case linear time), but also supports efficient (linear in the size of the key) random access to all values associated with any key.

We identify strong naturality—commutativity with filtering—as as a powerful property of stable sorting and show discrimination to commute with any strongly natural transformation.  This facilities equational correctness proofs relating the four functions to each other.

Joint work with Ralf Hinze.



Fritz Henglein is professor of programming languages and systems at DIKU, the Department of Computer Science at the University of Copenhagen.  His  research interests are in semantic, logical and algorithmic aspects of programming languages, specifically type inference, type-based program analysis, algorithmic functional programming and domain-specific languages; and the application of programming language technology, presently in enterprise systems (, health care processes ( and finance (

Document Actions