TP

# 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.

Published: Wednesday, 20 July 2011, 12:19 AM
Read the complete article

This article is a re-publication of an article that I wrote some time ago for The Monad.Reader magazine, which is an online magazine about functional programming and Haskell. You can also read the article in the original PDF format as part of the Issue 18 (together with two other interesting articles). The samples from the article can be found on Github.

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.

Published: Tuesday, 19 July 2011, 11:28 PM
Tags: haskell, research, parallel
Read the complete article

# All blog posts by tag

f# (112), functional (66), research (48), c# (37), asynchronous (27), academic (26), parallel (23), programming languages (21), functional programming (20), universe (20), meta-programming (18), philosophy (16), links (15), presentations (14), data science (12), writing (12), joinads (12), web (11), thegamma (11), talks (9), data journalism (9), math and numerics (9), random thoughts (9), phalanger (8), haskell (7), mono (7), webcast (7), design (5), fslab (5), open source (5), architecture (4), visualization (4), fun (4), accelerator (4), type providers (3), linq (3), f# data (3), .net (3), training (2), coeffects (2), deedle (2), monads (2), art (2), fractals (2), funscript (2), new york (2), manning (2), books (2)