What's the current status of restricted monads

Question

Going back to at least the late 1990s there have been people wishing for the integration of restricted monads into Haskell in a friendly way.

For example, without restricted monads you can't make an efficient monad out of Set, Map or probability distributions. Here's a SO question from a few years ago where someone else ran afoul of this problem.

There are various workarounds that people have come up with, including:

• Creating a new type class for every possible restriction.

• Using Template Haskell.

• Using Constraint Kinds.

None of these approaches seem to be "canonical" however. I found a comment from Don Stewart on this blog post, in 2007, where he intimated that we were "quite close" to having restricted monads with Indexed types.

What is the current status? Is there now a 'canonical' way to do restricted monads? Or we are still living with workarounds?

Answer 1

Actually it is possible to obtain an efficient Set monad as a regular monad, without any restrictions. In two distinct ways. The following article explains both:

http://okmij.org/ftp/Haskell/set-monad.html

The article also points out that restricted monads are actually quite restricted and preclude many monadic idioms. I conjecture that the implementation methods are general and any restricted monad can be turned into the usual one, without losing efficiency. So, it may seem that we don't need restricted monads at all.

Answer 2

There's a recent paper by Anders Persson, Emil Axelsson, and Josef Svenningson that shows a way to encode restricted monads. I've forgotten the details, but I remember it was a nice paper.

Persson, A. ; Axelsson, E. ; Svenningsson, J. (2011). Generic monadic constructs for embedded languages. IFL 2011, the 23rd Symposium on Implementation and Application of Functional Languages.