CODEWITHSUNDEEP
haskellsetmonadsset-comprehension
Hans Lub
Hans Lub

Reputation: 5678

How to define powerset in Data.Set.Monad?

When using Data.Set.Monad together with {-# LANGUAGE MonadComprehensions} one can define sets almost like we did in high school, where we defined sets using comprehensions like {x ∈ S | φ(x)}. For example: 

s' = [x | x <- s, phi(x)]

This is not possible using the more widely used Data.Set module, as its Set type constructor is not a monad.

When cobbling together a toy example lately I needed the powerset Powerset(S) = {x | x ⊆ S} The problem is that this definition doesn't use a "generator" x <- Y which is not a problem in set theory, but is required in monad comprehensions:

powerset s = [ x | x `isSubsetOf` s ]

just doesn't compile (error: Variable not in scope: x)

It is 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: powerset = (map fromList) . fromList. subsequences . toList. But this feels like an ugly hack

{-# LANGUAGE MonadComprehensions #-} 
import Prelude hiding (map)
import Data.List hiding (map)
import Data.Set.Monad 

powerset :: Ord a => Set a -> Set (Set a)
powerset =  (map fromList) . fromList. subsequences . toList

oneToTen = fromList [1..10]
smallEvens = [x | x <- oneToTen, even x, x < 6] -- just like in high school!

statement = smallEvens `member` powerset oneToTen

main :: IO()
main = putStrLn $ if statement == True  then "yes" else "no"

... will compile and print "yes", as expected.

Does anyone have a more elegant solution?

Upvotes: 1

Views: 308

Answers (1)

Aplet123
Aplet123

Reputation: 35482

Here is a simple recursive solution that leverages monad comprehensions:

powerset :: Ord a => Set a -> Set (Set a)
powerset s = insert s [x | elem <- s, let rest = delete elem s, x <- powerset rest]

Upvotes: 1

Related Questions