Minimizing Monad Comprehensions

Abstract

Monad comprehensions are by now a mainstay of functional programming languages. In this paper we develop a theory of semantic optimization for monad comprehensions that goes beyond rewriting using the monad laws. A monad-with-zero comprehension do x ← X; y ← Y ; if P(x, y) then return F(x, y) else zero can be rewritten, so as to minimize the number of ← bindings, using constraints that are known to hold of X and Y . The soundness of this technique varies from monad to monad, and we characterize its soundness for monads expressible in functional programming languages by generalizing classical results from relational database theory. This technique allows the optimization of a wide class of languages, ranging from large-scale data-parallel languages such as DryadLINQ and Data Parallel Haskell to robabilistic languages such as IBAL and functional-logical languages like Curry.