Comprehensive comprehensions: comprehensions with "Order by" and "Group by"

Phil Wadler and Simon Peyton Jones, submitted to Haskell Workshop 2007.

Abstract

We propose an extension to list comprehensions that makes it easy to express the kind of queries one would write in SQL using ORDER BY, GROUP BY, and LIMIT. Our extension adds expressive power to comprehensions, and generalises the SQL constructs that inspired it. Moreover, it is easy to implement, using simple desugaring rules.

For example, consider this SQL query

SELECT dept, SUM(salary)
FROM employees
GROUP BY dept
ORDER BY SUM(salary) DESCENDING
LIMIT 5
The GROUP BY clause groups records together; the ORDER BY sorts the departments in order of salary bill; and the LIMIT clause picks just the first five records. This support for grouping and sorting is extremely useful in practice, but is not available in list comprehensions.

In this paper we propose an extension to list comprehensions that makes it easy to express the kind of queries one would write in SQL using ORDER BY, GROUP BY, and LIMIT. Here, for example, is how the above SQL query would be rendered in our extension.

[ (the dept, sum salary)
| (name, dept, salary) <- employees
, group by dept
, order by Down (sum salary)
, order using take 5 ]
Moreover, our extensions are significantly more general than SQL's facilities.