oleg at okmij.org oleg at okmij.org
Thu Apr 11 09:44:06 CEST 2013

```The question of Set monad comes up quite regularly, most recently at
http://www.ittc.ku.edu/csdlblog/?p=134

Indeed, we cannot make Data.Set.Set to be the instance of Monad type
class -- not immediately, that it. That does not mean that there is no
rather than a list. I mean genuine *monad*, rather than a restricted,

It is surprising that the question of the Set monad still comes up
given how simple it is to implement it. Footnote 4 in the ICFP
2009 paper on ``Purely Functional Lazy Non-deterministic Programming''
described the idea, which is probably folklore. Just in case, here is
the elaboration, a Set monad transformer.

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

import qualified Data.Set as S

-- Since ContT is a bona fide monad transformer, so is SetMonadT r.
type SetMonadT r = ContT (S.Set r)

-- These are the only two places the Ord constraint shows up

mzero = ContT \$ \k -> return S.empty
mplus m1 m2 = ContT \$ \k -> liftM2 S.union (runContT m1 k) (runContT m2 k)

runSet :: (Monad m, Ord r) => SetMonadT r m r -> m (S.Set r)
runSet m = runContT m (return . S.singleton)

choose :: MonadPlus m => [a] -> m a
choose = msum . map return

test1 = print =<< runSet (do
n1 <- choose [1..5]
n2 <- choose [1..5]
let n = n1 + n2
guard \$ n < 7
return n)
-- fromList [2,3,4,5,6]

-- Values to choose from might be higher-order or actions
test1' = print =<< runSet (do
n1 <- choose . map return \$ [1..5]
n2 <- choose . map return \$ [1..5]
n  <- liftM2 (+) n1 n2
guard \$ n < 7
return n)
-- fromList [2,3,4,5,6]

test2 = print =<< runSet (do
i <- choose [1..10]
j <- choose [1..10]
k <- choose [1..10]
guard \$ i*i + j*j == k * k
return (i,j,k))
-- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

test3 = print =<< runSet (do
i <- choose [1..10]
j <- choose [1..10]
k <- choose [1..10]
guard \$ i*i + j*j == k * k
return k)
-- fromList [5,10]

```