Semigroupoid Interfaces for Programming with Relations in Haskell

Wolfram Kahl

pp. 235-250 in R. Schmidt, G. Struth (eds.) Relations and Kleene Algebra in Computer Science, RelMiCS/AKA 2006, Manchester, UK, Aug. 29 - Sept. 2, 2006, LNCS 4136, Springer-Verlag, 2006.

(.bib)

Abstract

We present a Haskell interface for manipulating finite binary relations as data in a point-free relation-algebraic programming style that integrates naturally with the current Haskell collection types. This approach enables seamless integration of relation-algebraic formulations to provide elegant solutions of problems that, with different data organisation, are awkward to tackle.

Perhaps surprisingly, the mathematical foundations for dealing with finite relations in such a context are not well-established, so we provide an appropriate generalisation of relational categories to semigroupoids to serve as specification for our interface.

After having established an appropriate interface for relation-algebraic programming, we also need an efficient implementation; we find this in BDD-based kernel library KURE of recent versions of the Kiel RelView system. We show how this combination enables high-level declarative and efficient relational programming in Haskell.