List Monad as Non-deterministic computation

powerset.hs

import Control.Monad.Random

arbitrarySet :: Monad m => m Bool -> [a] -> m [a]
arbitrarySet getBool = flip foldr (return []) $ \x ls -> do
                                                    t <- getBool
                                                    l <- ls
                                                    if t
                                                      then return (x:l)
                                                      else return l

randomSet :: [a] -> IO [a]
randomSet = arbitrarySet (getRandom :: IO Bool)


powerset :: [a] -> [[a]]
powerset = arbitrarySet [True, False]

{-
Computing the powerset is equivalent to non-deterministically computing a subset.

How do you non-deterministically compute a subset?

1. Start with the empty set                                       : `return []`
2. For each element in the given set,                             : `flip foldr`
3.  Nondeterministically choose either True or False.             : `t <- getBool`
4.  If you                                                        : `if t`
5.    chose True, then add the element                            : `then return (x:l)`
6.    otherwise, do not                                           : `else return l`

-}