On Sun, Jan 9, 2011 at 6:53 AM, Lennart Augustsson <span dir="ltr"><<a href="mailto:lennart@augustsson.net">lennart@augustsson.net</a>></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'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 { (>>-) :: forall b . Ord b => (a -> S.Set b) -> S.Set b }</div><div> </div><div> instance Monad Set where</div>
<div> return x = Set ($x)</div><div> a >>= f = Set (\k -> a >>- \x -> f x >>- 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 => Set a -> S.Set a</div><div> getSet a = a >>- 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 -> S.union (a >>- k) (b >>- k))</div></div><div><br></div><div>Maybe, Heinrich Apfelmus'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>