WG211/M15Gibbons

Comprehending Monadic Queries by Jeremy Gibbons

List comprehensions are a widely used programming construct, in languages such as Haskell and Python and in technologies such as Microsoft's Language Integrated Query. They generalize from lists to arbitrary monads, yielding a lightweight idiom of imperative programming in a pure functional language. When the monad has additive structure too, corresponding to empty and union operations, then it can be seen as some kind of collection type, and the comprehension notation can also be extended to incorporate aggregations. Comprehensions for additive monads represent a convenient notation for expressing database queries. The additive monad structure alone does not provide a good explanation or an efficient implementation of relational joins; but by allowing heterogeneous comprehensions, involving both the bag and the indexed table monads, we show how to accommodate these too.