Haskell aficionados, take note! My library for corecursive queues has now been uploaded to Hackage. You can now cabal-install it.
I also have a substantially revised draft of the associated paper, Lloyd Allison’s Corecursive Queues, available. It has been re-organized so that it is hopefully easier to follow, it includes a careful performance comparison, and a tentative proof that
mapCont cannot be expressed in terms of
The library includes a somewhat crude micro-benchmarking program in the
tests/ directory. Those who have read previous drafts, be warned that the few brief statements about performance were based on past notes, and I found some several issues with the testing methodology contained in the notes. Here the revised results:
|Description||Time (ms)||-H500M||Bytes allocated|
|GHC 6.10.3||mean||σ||mean||σ||per Branch|
|Side Channel _||959||3||1171||7||228.7|
|Side Channel ()||1500||56||2171||7||276.4|
These benchmarks come from performing breadth-first traversals repeatedly on the 34th fibonacci tree, on an Intel Core 2 Duo T9550. The first few data points were discarded, and the mean and standard deviation of the remaining times were computed. Note that
getCPUTime was used to time each run, and this has a resolution of only 10 milliseconds.
If you would like to play with the queue transformer, which doesn’t appear in the library, or other bits of code exactly as they appear in the paper, you can download the source code here.