Extending monads with pattern matching

Tomas Petricek, Alan Mycroft and Don Syme

In Proceedings of Haskell Symposium 2011

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.

We introduce 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 docase 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.

Paper and more information

• Download the paper (PDF)
• Download COQ script with some proofs
• See the original implementation (pre-processor and samples) at Github
• See GHC fork and GHC base fork for a proper implementation
• View talk slides from Haskell Symposium

Try Joinads

Try Joinads is a web site, using the open-source release of F#, that implements the joinads extension for F#. It comes with an browser-based F# console where you can experiment with joinads and numerous tutorials that demonstrate the usfulness of joinads. Tutorials include asynchronous, parallel and concurrent programming as well as parsing.

• Visit the Try Joinads web site!

Bibtex

If you want to cite the paper, you can use the following BibTeX information, or get full details from the paper page on ACM.

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 

@inproceedings{joinads-haskell11,
  author    = {Petricek, Tomas and Mycroft, Alan and Syme, Don},
  title     = {Extending {M}onads with {P}attern {M}atching},
  booktitle = {Proceedings of Haskell Symposium},
  series    = {Haskell 2011},
  location  = {Tokyo, Japan},
  year      = {2011}
}

If you have any comments, suggestions or related ideas, I'll be happy to hear from you! Send me an email at tomas@tomasp.net or get in touch via Twitter at @tomaspetricek.