Will Fancher recently wrote a blog post
(see also the Reddit thread)
about sorting arbitrary Traversable containers without any of the ugly incomplete pattern matches that
accompany the well-known technique of dumping all the entries into a list and then sucking them back out
in State. Fancher used a custom applicative based on the usual
free applicative.
Unfortunately, this type is rather hard to work with, and Fancher was not immediately able to find a
way to use anything better than insertion sort. This repository demonstrates an asymptotically optimal heap
sort using a heap-merging applicative.
The three modules:
BasicNat: unary natural numbers, singletons, and propertiesIndexedPairingHeap: size-indexed pairing heapsHSTrav: the big payoff: heap-sorting anything