Sort any Traversable container
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

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 properties
  • IndexedPairingHeap: size-indexed pairing heaps
  • HSTrav: the big payoff: heap-sorting anything