Established generic sorting is based on comparison and is known to have a lower bound of O(n log n). In a recent paper1 Fritz Henglein sets out an approach based on discrimination which has a lower bound of O(n), a fundamental improvement to the state-of-the-art. In this talk Haskell and Scala implementations of generic linear time sorting, based on this paper, will be presented. Performance measurement methodology and the initial, encouraging results will be discussed.

Given Scala’s rich type-system and ability to create powerful abstractions, can we derive generic sorting based on distribution that outperforms generic comparison-based sorting? Based on the work of Fritz Henglein and Ralf Hinze, “Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries” and “Generic Top-down Discrimination for Sorting and Partitioning in Linear Time”.

A look at another composition tool in the functional programmer’s symbol bag.

A small and (possibly) simple example of using type-level programming to create a declarative API for command-line option parsing.

An attempt to get across an intuition for the Zipper and why purely functional datastructures are powerful.