Designing and Using Combinators: The Essence of Functional Programming

A graduate course by John Hughes

Combinator libraries, nowadays often called Domain Specific Embedded Languages, offer an easy way to provide a customised programming language for a particular application domain. Such a language can greatly simplify applications. The idea of a DSEL is not specific to Haskell, but Haskell is an excellent "host language" to embed a customised language in, and indeed, this approach to programming has a long history in the functional language community.

DSELs can be a valuable tool for researchers, because they support "exploratory language design". A researcher can identify appropriate abstractions in the problem domain, and rapidly build a DESL that embodies them to experiment with.

This course will explain the combinator library idea, give many examples and applications, and discuss design principles to help you invent your own. We will also discuss research projects in several areas, where a DSEL is a key enabling technology.


This course is worth 1 study credit for PhD students. To be awarded the credit, you should complete the exercises (except perhaps for Part 2 of A Stream Processor Monad Transformer). You may solve the exercises in pairs.

Course Materials

A lightning tour of Haskell Lecture (html, ps, ppt)
Accompanying exercises
Domain specific embedded languages Lecture (html, ps, ppt)
Reading: Modular Domain Specific Languages and Tools
Monads and monad transformers Lecture (html, ps, ppt)
Reading: Monad Transformers and Modular Interpreters
Exercises: Exceptions and Extending the Parsing Library
Resource: Phil Wadler's classic papers on monads
Source code: module MonadTransformers
QuickCheck and Wash/CGI Lecture (html, ps, ppt)
Reading: QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs
Resource: QuickCheck home page
Reading: WASH/CGI: Server-side Web Scripting with Sessions, Compositional Forms, and Graphics
Resource: WASH home page
Deriving combinator implementations Lecture (html, ps, ppt)
Reading:Deriving Backtracking Monad Transformers
Resource: The Design of a Prettyprinting Library
Source code: module Pretty
Exercise: A Stream Processor Monad Transformer
Functional reactive programming Lecture (ps, ppt)
Reading: Functional Reactive Animation
Resource: the Fran home page
Resource: the FRP home page

Things we didn't cover