3 ms·
I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
by viraptor 8y ago
I feel like there's some reasonably simple idea trying to get out of those pages of literate Haskell ;-)
- twanvl 8y agoThis 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]]
- KirinDave 8y agoThe 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.