On 15 Oct 2012, at 17:42, Mike Stay wrote:
Can any readers point me to other algorithms that were discovered by turning to category theory
My colleague Ralf Hinze and some others in my group just published a paper at WGP 2012 relating different sorting algorithms using bi-algebras: http://dx.doi.org/10.1145/2364394.2364405 (also available through their webpages). For example, naive insertion sort and naive bubblesort are "essentially" the same algorithm, with dual presentations. The same duality technique can be used to obtain some new sorting algorithms from existing ones; in particular, they come up with a "minglesort" as a dual to heapsort. (I'm not claiming that's a world-changing discovery, but it's elegant work.) Jeremy Jeremy.Gibbons@cs.ox.ac.uk Oxford University Department of Computer Science, Wolfson Building, Parks Road, Oxford OX1 3QD, UK. +44 1865 283521 http://www.cs.ox.ac.uk/people/jeremy.gibbons/ [For admin and other information see: http://www.mta.ca/~cat-dist/ ]