On Mon, 15 Oct 2012, Mike Stay wrote:
I'd like to get more computer programmers interested in category theory.
Yes!
There's the obvious connection to type theory and categorical semantics, but programmers are usually far more interested in algorithms. ... Can any readers point me to other algorithms that were discovered by turning to category theory or to reports of problems solved by realizing they were instances of an abstraction of another solved problem?
In http://kolxo3.tiera.ru/M_Mathematics/MA_Algebra/MAct_Category%20theory/Rydeh... , "Computational Category Theory", David Rydeheard and Rod Burstall derive an algorithm for unifying terms (in the sense used in logic programming), treating it as the construction of coequalisers. (Their original paper, "A Categorical Unification Algorithm", is on the Web, but I can only find copies that are locked up behind a Springer paywall.) There are more recent such algorithms, e.g. http://docis.info/docis/lib/goti/rclis/dbl/enitcs/(2002)66%253A5%253C%253AAC... , "A categorical approach to unification of generalised terms" by Eklund, Galán, Medina, Ojeda-Aciego and Valverde. My "Excelsior" spreadsheet-modularisation software, described in http://www.j-paine.org/calco2011/paper.html , "Module Expressions for Modularising Spreadsheets and Sharing Code between Them", was inspired by category theory, specifically by Joseph Goguen's sheaf semantics for interacting objects. Goguen has used colimits and 3/2-colimits to model conceptual blending and the interpretation of metaphors: http://cseweb.ucsd.edu/~goguen/pps/taspm.pdf , "Mathematical Models of Cognitive Space and Time". Michael Healy has used natural transformations and functors as a guide to combining neural networks: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.2635 , "Category Theory Applied to Neural Modeling and Graphical Representations". Michael Healy, Thomas Caudell, and Timothy Goldsmith have proposed that compound concepts could be represented as categorical diagrams, and that concepts could be compared by comparing these diagrams. They say that for some simple test examples, the results of these comparisons are fairly close to human performance, and that this is therefore worth considering as a mathematical model of human concept representation and comparison: http://repository.unm.edu/handle/1928/6724 , "A Model of Human Categorization and Similarity Based Upon Category Theory". Ronnie Brown and Tim Porter suggest that higher-dimensional algebra and colimits might be useful for sensoty integration, though they don't develop any algorithms: http://arxiv.org/PS_cache/math/pdf/0306/0306223v1.pdf , "Category Theory and Higher Dimensional Algebra: potential descriptive tools in neuroscience". Manfred Liebmann has used multicategories and operads as a guide to designing parallel numerical algorithms: http://paralleltoolbox.sourceforge.net/categorytheory.pdf , "Category Theory and the Design of Parallel Numerical Algorithms". There has been a lot of work on merging ontologies by using categorical constructions, usually pushout and colimit. See e.g. Pascal Hitzler, Markus Krötzsch, Marc Ehrig, York Sure in http://knoesis.cs.wright.edu/faculty/pascal/resources/publications/cando05.p..., "What Is Ontology Merging? - A Category-Theoretical Perspective Using Pushouts" and Google "combining ontologies categorically". I once suggested that, via algebraic-specification languages such as CafeOBJ, category theory could be used to guide the construction and modularisation of large Web sites: http://www.j-paine.org/alg_web_spec.html , "Algebraic Web specification". There's quite a lot of other stuff out there. I hope these examples fit the spirit of Mike's question. Quite often, it seems that the authors use category theory as a guide, searching it for constructions that they might instantiate as data structures. They then devise algorithms to build these structures. Usually, they do so informally, rather than by formally deriving the algorithm from a categorical definition. Very often, the categorical construction they use is a pushout or colimit. That's the impression I have, anyway. So what they're doing is along the lines suggested by Goguen in his "A Categorical Manifesto", http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.362 . By the way, in http://www.j-paine.org/dobbs/why_be_interested_in_categories.html , "What Might Category Theory do for Artificial Intelligence and Cognitive Science?", I suggest that these two fields are ripe for the plundering of apparently unrelated concepts that category theory might be able to unify.
Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Jocelyn Ireson-Paine http://www.j-paine.org/index.html Jocelyn's Cartoons http://www.j-paine.org/blog/jocelyns_cartoons/ [For admin and other information see: http://www.mta.ca/~cat-dist/ ]