title: Constructing efficient monad instances on `Set` (and other containers with constraints) using the continuation monad
body: <p><code>Set</code>, similarly to <code>[]</code> has a perfectly defined monadic operations. The problem is that they require that the values satisfy <code>Ord</code> constraint, and so it's impossible to define <code>return</code> and <code>&gt;&gt;=</code> without any constraints. The same problem applies to many other data structures that require some kind of constraints on possible values.</p>
  
  <p>The standard trick (suggested to me in a <a href="http://www.haskell.org/pipermail/haskell-cafe/2009-November/068761.html">haskell-cafe post</a>) is to wrap <code>Set</code> into the continuation monad. <code>ContT</code> doesn't care if the underlying type functor has any constraints. The constraints become only needed when wrapping/unwrapping <code>Set</code>s into/from continuations:</p>
  
  <pre><code>import Control.Monad.Cont
  import Data.Foldable (foldrM)
  import Data.Set
  
  setReturn :: a -&gt; Set a
  setReturn = singleton
  
  setBind :: (Ord b) =&gt; Set a -&gt; (a -&gt; Set b) -&gt; Set b
  setBind set f = foldl' (\s -&gt; union s . f) empty set
  
  type SetM r a = ContT r Set a
  
  fromSet :: (Ord r) =&gt; Set a -&gt; SetM r a
  fromSet = ContT . setBind
  
  toSet :: SetM r r -&gt; Set r
  toSet c = runContT c setReturn
  </code></pre>
  
  <p>This works as needed. For example, we can simulate a non-deterministic function that either increases its argument by 1 or leaves it intact:</p>
  
  <pre><code>step :: (Ord r) =&gt; Int -&gt; SetM r Int
  step i = fromSet $ fromList [i, i + 1]
  
  -- repeated application of step:
  stepN :: Int -&gt; Int -&gt; Set Int
  stepN times start = toSet $ foldrM ($) start (replicate times step)
  </code></pre>
  
  <p>Indeed, <code>stepN 5 0</code> yields <code>fromList [0,1,2,3,4,5]</code>. If we used <code>[]</code> monad instead, we would get </p>
  
  <pre><code>[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5]
  </code></pre>
  
  <p>instead.</p>
  
  <hr>
  
  <p>The problem is <strong>efficiency</strong>. If we call <code>stepN 20 0</code> the output takes a few seconds and <code>stepN 30 0</code> doesn't finish within a reasonable amount of time. It turns out that all <code>Set.union</code> operations are performed at the end, instead of performing them after each monadic computation. The result is that exponentially many <code>Set</code>s are constructed and <code>union</code>ed only at the end, which is unacceptable for most tasks.</p>
  
  <p>Is there any way around it, to make this construction efficient? I tried but without success.</p>
  
  <p>(I even suspect that there could be some kinds of theoretical limits following from Curry-Howard isomorphism and <a href="https://en.wikipedia.org/wiki/Double-negation_translation#Propositional_logic">Glivenko's theorem</a>. Glivenko's theorem says that for any propositional tautology <em>φ</em> the formula <em>¬¬φ</em> can be proved in intuitionistic logic. However, I suspect that the length of the proof (in normal form) can be exponentially long. So, perhaps, there could be cases when wrapping a computation into the continuation monad will make it exponentially longer?)</p>