title: How to define powerset in Data.Set.Monad?
body: <p>When using <a href="https://hackage.haskell.org/package/set-monad-0.3.0.0/docs/Data-Set-Monad.html" rel="nofollow noreferrer">Data.Set.Monad</a> together with <code>{-# LANGUAGE MonadComprehensions}</code> one can define sets
  almost like we did in high school, where we defined sets using comprehensions like <code>{x ∈ S | φ(x)}</code>. For example: </p>
  
  <pre><code>s' = [x | x &lt;- s, phi(x)]
  </code></pre>
  
  <p>This is <em>not</em> possible using the more widely used <a href="https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Set.html" rel="nofollow noreferrer"><code>Data.Set</code></a> module, as its <code>Set</code> type constructor is not a monad.</p>
  
  <p>When cobbling together a toy example lately I needed the powerset <code>Powerset(S) = {x | x ⊆ S}</code> The problem is that this definition doesn't use a "generator" <code>x &lt;- Y</code>  which is not a problem in set theory, but is required in monad comprehensions:</p>
  
  <pre><code>powerset s = [ x | x `isSubsetOf` s ]
  </code></pre>
  
  <p>just doesn't compile (<code>error: Variable not in scope: x</code>)</p>
  
  <p>It <em>is</em> possible to convert a set to a list, take the list of all of its sublists, convert this list back to a set and then convert all of its elements to sets as well: <code>powerset =  (map fromList) . fromList. subsequences . toList</code>. But this feels like an ugly hack</p>
  
  <pre><code>{-# LANGUAGE MonadComprehensions #-} 
  import Prelude hiding (map)
  import Data.List hiding (map)
  import Data.Set.Monad 
  
  powerset :: Ord a =&gt; Set a -&gt; Set (Set a)
  powerset =  (map fromList) . fromList. subsequences . toList
  
  oneToTen = fromList [1..10]
  smallEvens = [x | x &lt;- oneToTen, even x, x &lt; 6] -- just like in high school!
  
  statement = smallEvens `member` powerset oneToTen
  
  main :: IO()
  main = putStrLn $ if statement == True  then "yes" else "no"
  </code></pre>
  
  <p>... will compile and print "yes", as expected.</p>
  
  <p>Does anyone have a more elegant solution?</p>