Tomas Petricek

Searching for new ways of thinking in programming & working with data

I believe that the most interesting work is not the one solving hard problems, but the one changing how we think about the world. I follow this belief in my work on data science tools, functional programming and F# teaching, in my programming languages research and I try to understand it through philosophy of science.

The Gamma

I'm working on making data-driven storytelling easier, more open and reproducible at the Alan Turing Institute.

Consulting

I'm author of definitive F# books and open-source libraries. I offer my F# training and consulting services as part of fsharpWorks.

Academic

I published papers about theory of context-aware programming languages, type providers, but also philosophy of science.

Tomas Petricek
  • Tomas Petricek
  • Home
  • F# Trainings
  • Talks and books
  • The Gamma
  • Academic

Extending Monads with Pattern Matching (Haskell 2011)

Some time ago, I wrote a paper about joinads and the match! extension 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.

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.

Links to the full paper, source code and additional materials are available below.

Implementation

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 Makefile provided and then executed using the command: joinadsp.exe Sample.jhs > Sample.hs

  • Samples includes numerous examples that use joinads. It includes Joinad instance for the Maybe type 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 Par monad 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 docase notation. 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.

Downloads & source code 

  • Download the complete paper (PDF).
  • Get the implementation of pre-processor and samples from Github.
  • For bibtex, formalized proof, and more see my academic web.

Published: Wednesday, 20 July 2011, 12:19 AM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: parallel, writing, research, haskell, joinads

Contact & about

This site is hosted on GitHub and is generated using F# Formatting and DotLiquid. For more info, see the website source on GitHub.

Please submit issues & corrections on GitHub. Use pull requests for minor corrections only.

  • Twitter: @tomaspetricek
  • GitHub: @tpetricek
  • Email me: tomas@tomasp.net

Blog archives

October 2020 (1),  July 2020 (1),  April 2020 (2),  December 2019 (1),  February 2019 (1),  November 2018 (1),  October 2018 (1),  May 2018 (1),  September 2017 (1),  June 2017 (1),  April 2017 (1),  March 2017 (2),  January 2017 (1),  October 2016 (1),  September 2016 (2),  August 2016 (1),  July 2016 (1),  May 2016 (2),  April 2016 (1),  December 2015 (2),  November 2015 (1),  September 2015 (3),  July 2015 (1),  June 2015 (1),  May 2015 (2),  April 2015 (3),  March 2015 (2),  February 2015 (1),  January 2015 (2),  December 2014 (1),  May 2014 (3),  April 2014 (2),  March 2014 (1),  January 2014 (2),  December 2013 (1),  November 2013 (1),  October 2013 (1),  September 2013 (1),  August 2013 (2),  May 2013 (1),  April 2013 (1),  March 2013 (1),  February 2013 (1),  January 2013 (1),  December 2012 (2),  October 2012 (1),  August 2012 (3),  June 2012 (2),  April 2012 (1),  March 2012 (4),  February 2012 (5),  January 2012 (2),  November 2011 (5),  August 2011 (3),  July 2011 (2),  June 2011 (2),  May 2011 (2),  March 2011 (4),  December 2010 (1),  November 2010 (6),  October 2010 (6),  September 2010 (4),  July 2010 (3),  June 2010 (2),  May 2010 (1),  February 2010 (2),  January 2010 (3),  December 2009 (3),  July 2009 (1),  June 2009 (3),  May 2009 (2),  April 2009 (1),  March 2009 (2),  February 2009 (1),  December 2008 (1),  November 2008 (5),  October 2008 (1),  September 2008 (1),  June 2008 (1),  March 2008 (3),  February 2008 (1),  December 2007 (2),  November 2007 (6),  October 2007 (1),  September 2007 (1),  August 2007 (1),  July 2007 (2),  April 2007 (2),  March 2007 (2),  February 2007 (3),  January 2007 (2),  November 2006 (1),  October 2006 (3),  August 2006 (2),  July 2006 (1),  June 2006 (3),  May 2006 (2),  April 2006 (2),  December 2005 (1),  July 2005 (4),  June 2005 (5),  May 2005 (1),  April 2005 (3),  March 2005 (3),  January 2005 (1),  December 2004 (3),  November 2004 (2), 

License

Unless explicitly mentioned, all articles on this site are licensed under Creative Commons Attribution Share Alike. All source code samples are licensed under the MIT License.

CC License logo