25

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:

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?

Community
  • 1
  • 1
Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
  • 12
    I'd think with constraint kinds it's as canonical as it gets, they're just a bit too new for it to be the most _common_ solution yet. – leftaroundabout Jul 22 '12 at 11:22

2 Answers2

12

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.

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
  • 1
    Thanks Norman. For anyone who's interested, you can get a copy of the paper from [Josef Svenningson's homepage](http://www.cse.chalmers.se/~josefs/). – Chris Taylor Jul 23 '12 at 14:55
11

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.

Oleg
  • 709
  • 6
  • 6
  • I actually already used the idea behind your efficient Set monad to build an efficient probability distribution monad (see https://github.com/chris-taylor/hs-probability/blob/master/src/Control/Probability/Bayes.hs) .. so thanks! I haven't thought about doing the same thing for other restricted monads, but I can't immediately see a reason why it wouldn't work. – Chris Taylor Jul 26 '13 at 06:39