Publications about joinads

We first implemented joinads as an extension for F# and wrote a preliminary report about the work, which appeared in PADL 2011. More recently, joinads have been added to Haskell and refined slightly to make the algebraic structure simple and better defined. The extended paper appeared in Haskell Symposium 2011.

There are numerous differences between the two versions - the original version didn't require joinad to be a monad and had a more complex operation corresponding to choice and aliasing. The revised version simplifies the set of operations and provides better formal background. The implementation on this page is mostly based on the newer (Haskell) version.

Additionally, the page below also contains information about PADL 2014 paper that discusses F# computation expressions in a broader perspective and uses an extension (implemented in the editor here) for writing applicative functors.

The F# Computation Expression Zoo

Tomas Petricek and Don Syme
Proceedings of PADL 2014

The abstract of the paper:

Many computations can be structured using abstract computation types such as monoids, monad transformers or applicative functors. Functional programmers use those abstractions directly while main-stream languages often integrate concrete instances as language features - e.g. generators in Python or asynchronous computations in C# 5.0. The question is, is there a sweet spot between convenient, hardwired language features, and an inconvenient but flexible libraries?

F# computation expressions answer this question in the affirmative. Unlike the do notation in Haskell, computation expressions are not tied to a single kind of abstraction. They support a wide range of computations, depending on what operations are available. They also provide greater syntactic flexibility leading to a more intuitive syntax, without resorting to full macro-based meta-programming.

We show that computation expressions can structure well-known computations including monoidal list comprehensions, monadic parsers, applicative formlets and asynchronous sequences based on the list monad transformer. We also present typing rules for computation expressions that are capable of capturing all these applications.

The paper can be downloaded from the author's academic page.

Extending Monads with Pattern Matching

Tomas Petricek, Alan Mycroft and Don Syme
Proceedings of Haskell Symposium 2011

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.

The paper can be downloaded from the author's academic page.

Evaluation strategies for monadic computations

Tomas Petricek
Proceedings of MSFP 2012

Monads have become a powerful tool for structuring effectful computations in functional programming, because they make the order of effects explicit. When translating pure code to a monadic version, we need to specify evaluation order explicitly. This requires us to choose between call-by-value or call-by-name style. The two translations give programs with different semantics, structure and also different types.

In this paper, we translate pure code to monadic using an additional operation malias that abstracts out the evaluation strategy. The malias operation is based on computational comonads; we use a categorical framework to specify the laws that are required to hold about the operation.

We show two implementations of malias for any monad that give call-by-value and call-by-name semantics. Although we do not give call-by-need semantics for any monad, we show how to turn any monad into an extended monad with call-by-need semantics, which partly answers a standing open question. Moreover, using our unified translation, it is possible to change the evaluation strategy of functional code translated to the monadic form without changing its structure or types.

The paper can be downloaded from the author's academic page.

Fun with Parallel Monad Comprehensions

Tomas Petricek
The Monad.Reader, Issue 18 (Unreviewed article)

Monad comprehensions have an interesting history. They were the first syntactic extension for programming with monads. They were implemented in Haskell, but later replaced with plain list comprehensions and monadic do notation. Now, monad comprehensions are back in Haskell, more powerful than ever before!

Redesigned monad comprehensions generalize the syntax for working with lists. Quite interestingly, they also generalize syntax for zipping, grouping and ordering of lists. This article shows how to use some of the new expressive power when working with well-known monads. You'll learn what "parallel composition" means for parsers, a poor man's concurrency monad and an evaluation order monad.

The article can be downloaded from the author's academic page.

Joinads: a retargetable control-flow construct
for reactive, parallel and concurrent programming

Tomas Petricek and Don Syme
Proceedings of PADL 2011

The abstract of the paper:

Modern challenges led to a design of a wide range of programming models for reactive, parallel and concurrent programming, but these are often difficult to encode in general purpose languages. We present an abstract type of computations called joinads together with a syntactic language extension that aims to make it easier to use joinads in modern functional languages.

Our extension generalizes pattern matching to work on abstract computations. It keeps a familiar syntax and semantics of pattern matching making it easy to reason about code, even in a non-standard programming model. We demonstrate our extension using three important programming models – a reactive model based on events; a concurrent model based on join calculus and a parallel model using futures. All three models are implemented as libraries that benefit from our syntactic extension. This makes them easier to use and also opens space for exploring new useful programming models.

The paper can be downloaded from the author's academic page.