Comment by KirinDave | Hacker News Reader

Comment by KirinDave | Hacker News Reader

Parent Full thread

If you check my submission history you'll see me mention it a few times. The library has links[0] to the papers which describe how to use American Flag Sort in functional contexts to get high performance linear time sorts.

Most modern, thorough upper-division computer science programs cover how the sorting itself works. I think MIT Open Courseware has one [1].

Before thinking about how to do it productively, imagine that you sorted a list of objects based off their identity, and their identity was trivially comparable. Once sorted, the algorithm would be simple. You'd iterate the list, and every time you see a new object you didn't just see before (you only need a history of one object), you copy it to the output.

To do this in a productive way, you'd actually need to turn each potential bucket you're sorting into a future and then process all of those asynchronously (and ideally in parallel). Top down sorts like American Flag are uniquely suited to this.

[0]: https://www.cs.ox.ac.uk/projects/utgp/school/henglein2012c.p...

[1]: https://www.youtube.com/watch?v=pOKy3RZbSws

I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)

This library is essentially a generic version of radix sort. For example to sort an array of strings in O(nk), where k is the maximum length all strings: use bucket sort to split the strings into 256 buckets based on the first character. Take O(n) * recursively sort each bucket based on the remaining k-1 characters. Takes O(n(k-1)). concatenate sorted buckets

This is better than the O(nklog(n)) you get with comparison based sort. It turns out that you can implement radix sort for pretty much any type, where instead of a comparison operator for that type you have a 'split into buckets' operator.

The types might look something like this (in Haskell notation):

    class Ord a where
      compare :: a -> a -> Ordering

    class Bucketable a where
      splitIntoBuckets :: (b -> a) -> [b] -> [[b]]

This is the paper. The library, well the library literally discovers a new category theoretic construct that previously no one believed existed in Haskell.

Perfect. That's what I was after. It makes sense.

The first big insight Henglein brings in the first paper is structural: you can map searches sensibly over products and sums. This is actually a profound thing, but most folks outside of Haskell circles don't work with ADTs so they don't understand the universal applicability of this insight.

It means you can map them over any concrete, acyclic structure. Which means you can sort anything with radix sort.

Reply on news.ycombinator.com