Extending Monads with Pattern Matching (Haskell 2011)
Some time ago, I wrote a paper about joinads and the
of the F# language. The paper was quite practically oriented and didn't go into much details about
the theory behind joinads. Many of the examples from the F# version relied on some
imperative features of F#. I believe that this is useful for parctical programming, but I
also wanted to show that the same idea can work in the purely functional context.
To show that joinads work in the pure setting, I created a Haskell version of the idea. The implementation (available below) is quite simple and consists of a pre-processor for Haskell source files and numerous examples. However, more important part of the recent work of joinads is a more detailed theoretical background.
The theory of joinads, together with the language design of Haskell extension that implements it is discussed in a paper Extending Monads with Pattern Matching, which was accepted for publication at the Haskell Symposium 2011. Here is the abstract of the paper:
Sequencing of effectful computations can be neatly captured using monads and elegantly written using
do notation. In practice such monads often allow additional ways of composing computations,
which have to be written explicitly using combinators.
We identify joinads, an abstract notion of computation that is stronger than monads and captures
many such ad-hoc extensions. In particular, joinads are monads with three additional operations:
one of type
m a -> m b -> m (a, b) captures various forms of parallel composition,
one of type
m a -> m a -> m a that is inspired by choice and one of type
m a -> m (m a)
that captures aliasing of computations. Algebraically, the first two operations form a
near-semiring with commutative multiplication.
docase notation that can be viewed as a monadic version of
case. Joinad laws
make it possible to prove various syntactic equivalences of programs written using
that are analogous to equivalences about
case. Examples of joinads that benefit from the notation
include speculative parallelism, waiting for a combination of user interface events, but also
encoding of validation rules using the intersection of parsers.
Links to the full paper, source code and additional materials are available below.
The paper doesn't discuss the implementation of the Haskell language extension and the samples
in details, so I'll add a few additional information to this blog post. At the moment, the
extension is implemented using a simple pre-processor that translates Haskell'98 with the
docase extension into pure Haskell'98. The pre-processor is based on Ross Paterson's
pre-processor for the arrow notation.
The Github repository contains the following directories:
Preprocessor directory contains the implementation of the pre-processor. It can be compiled using the
Makefileprovided and then executed using the command:
joinadsp.exe Sample.jhs > Sample.hs
Samples includes numerous examples that use joinads. It includes
Joinadinstance for the
Maybetype and types mentioned in the paper (parsers that can be used for input validation, parallelsim monad used above and simple cooperative parallelism monad using resumptions).
ParMonad includes core parts of the
Parmonad that is used in the parallel programming samples. The implementation is extended to support speculative parallelism (see a separate a blog post). a complete modified implementation is available in a separate project
Comprehensions shows several examples that use generalized monad comprehensions to write similar examples as those that use
docasenotation. Parallel monad comprehensions are a generalization of parallel list comprehensions and overlap with joinads in an interesting way. For more information see my article Fun with Parallel Monad Comprehensions.