LFCS Seminar: Fritz Henglein
Towards generic distributive sorting and searching
What 


When 
Jun 27, 2013 from 04:00 PM to 05:00 PM 
Where  IF 4.3133 
Add event to calendar 
vCal iCal 
Comparisonbased 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/trielike) 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 userdefinable orders over arbitrary firstorder and recursive types.
Trie building yields a data structure not only asymptotically as efficiently as discrimination (for standard orders worstcase 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.
Biography:
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, typebased program analysis, algorithmic functional programming and domainspecific languages; and the application of programming language technology, presently in enterprise systems (3gERP.org), health care processes (trustcare.eu) and finance (hiperfit.dk).