September 1, 2010
Mikael Vejdemo Johansson (Stanford): Species, derivatives of types and Gröbner bases for operads
Abstract:
Recent work by Dotsenko and Khoroshkin defines a Gröbner basis paradigm for operads,
generalizing both commutative and non-commutative Gröbner bases to a more abstract
framework. In work joint with Dotsenko, we have implemented the algorithms described
by Dotsenko and Khoroshkin in Haskell. The choice of language for the implementation
was supported by the large amount of category theoretical and even combinatorial
species inspired constructions that are not only possible but easy in the language.
I will describe how the Haskell type system fits in a category theoretical framework, with endofunctors playing the role of container types and fixed points of polynomial and formal power series endofunctors defining most of the common container types used. Furthermore, I will describe the work by Conor McBride on formal derivatives of types, implicit differentiation of endofunctors and their interpretation as containers with designated holes. This construction provides an automatic approach to the Zipper datatypes as well as a powerful tool in the implementation work for the operadic Gröbner basis code.
The whole approach parallels Joyal's theory of species closely, and I'll put some emphasis on how these parallel developments interconnect.