On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson <span dir="ltr">&lt;<a href="mailto:lennart@augustsson.net">lennart@augustsson.net</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
It so happens that you can make a set data type that is a Monad, but it&#39;s not exactly the best possible sets.<div><br></div><div><div>module SetMonad where</div><div><br></div><div>newtype Set a = Set { unSet :: [a] } </div>
</div></blockquote><div><br></div><div>Here is a version that also does not require restricted monads but works with an arbitrary underlying Set data type (e.g. from Data.Set). It uses continuations with a Rank2Type.</div>
<div><br></div><div><div>    import qualified Data.Set as S</div><div>    </div><div>    newtype Set a = Set { (&gt;&gt;-) :: forall b . Ord b =&gt; (a -&gt; S.Set b) -&gt; S.Set b }</div><div>    </div><div>    instance Monad Set where</div>
<div>      return x = Set ($x)</div><div>      a &gt;&gt;= f  = Set (\k -&gt; a &gt;&gt;- \x -&gt; f x &gt;&gt;- k)</div></div><div><br></div><div>Only conversion to the underlying Set type requires an Ord constraint.</div>
<div><br></div><div><div>    getSet :: Ord a =&gt; Set a -&gt; S.Set a</div><div>    getSet a = a &gt;&gt;- S.singleton</div></div><div><br></div><div>A `MonadPlus` instance can lift `empty` and `union`.</div><div><br></div>
<div><div>    instance MonadPlus Set where</div><div>      mzero     = Set (const S.empty)</div><div>      mplus a b = Set (\k -&gt; S.union (a &gt;&gt;- k) (b &gt;&gt;- k))</div></div><div><br></div><div>Maybe, Heinrich Apfelmus&#39;s operational package [1] can be used to do the same without continuations.</div>
<div><br></div><div>[1]: <a href="http://projects.haskell.org/operational/">http://projects.haskell.org/operational/</a></div></div>