[Haskell-cafe] ANNOUNCE: uvector-algorithms 0.1

[Dan Doel]

Hello,

I've been sitting on this for a while, waiting for some changes to uvector to 
go in, but finally decided I should just release it, and fix it up if and when 
said changes go in. So, I'm announcing the first release of uvector-
algorithms.

What it is is a library of algorithms (mostly sorting) for the mutable arrays 
defined in uvector. It has several varieties of sorting, including introsort 
(quicksort which falls back on heapsort in bad cases), heapsort, a simple top-
down merge sort and a radix sort (as well as insertion sort, and optimal 
sorting for length<=4 arrays, which probably won't get much use outside of the 
implementation of the other sorts). All modules attempt to export as uniform 
an interface as possible, so that one can substitute between them freely, say 
when trying to determine which algorithm is best suited for your particular 
datasets.

Also exposed are the operations that allow you to use the arrays as heaps 
(which is the basis for implementing heapsort), and partial sorts and selects 
in heap and intro variety. Lastly, there is a combinator for safely using 
these mutable array algorithms to sort immutable arrays.

All of these algorithms have been painstakingly profiled, and their generated 
core examined to do as little heap allocation and as much unboxing as 
possible, and to inline and specialize for maximum performance (unless, of 
course, I've managed to miss anything). I've been running a relatively simple 
benchmarking suite that tests various kinds of inputs, and in my experience, 
the sorts herein tend to beat glibc's sort, and do relatively well compared to 
GNU's STL sorts over vector<>s (taking 50% or so more time at present, 
although this library may well be better at heapsorting random arrays, if you 
want something to brag about :)).

For future work, I've been working on an implementation of Python's timsort 
(which is a very fancy bottom-up merge sort), but it's not ready yet. I'd also 
like to introduce some combinators for easy Schwartzian transforms, but that 
again requires modifications to uvector. I may also look at moving some of my 
benchmark program into the package.

Suggestions for other algorithms people would like to see are of course 
welcome (especially if accompanied by papers/references on how to implement 
them if they're not well known).

The hackage page is here:
 http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uvector-algorithms

Enjoy, and please let me know of any issues.
-- Dan