Declan’s focus is on high performance network software, and has been the architect of several products at Zeus Technology, Riverbed Technology and Juniper Networks. He pays his bills through writing low-level networking code in C++, but his main passion is the beauty and simplicity of functional programming. Through his experience and battles with large, ageing, imperative codebases over the past 10 years, he has recognised that FP is the best candidate remedy.
Declan is also a regular speaker at ScalaSyd, Sydney’s Scala User Group.
YOW! Lambda Jam 2014 Brisbane
Quicker Sort? Implementing generic linear time sorting
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.
Academic research can often be intimidating, and bridging the gap between paper and implementation can seem like a big task. In this talk the speaker will share their perspective on this process.
The talk seeks to demonstrate that composition can yield fundamental insights, that research is more accessible than people may think, and to show interesting implementation details of the algorithm by comparing and contrasting Scala and Haskell.
Pre-Requisites: Familiarity with Haskell and/or Scala syntax, and garden variety sorting algorithms.
References: Various papers on the topic are widely available, of which the two most relevant are, 1 Henglein, Fritz. “Generic top-down discrimination for sorting and partitioning in linear time.” Journal of Functional Programming 22.03 (2012): 300-374. 2 Henglein, Fritz, and Ralf Hinze. “Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries.” Programming Languages and Systems: 11th Asian Symposium, APLAS 2013, Melbourne, VIC, Australia, December 9-11, 2013. Proceedings. Springer International Publishing, 2013.