Powerset by filterM

powerset.hs

-- http://stackoverflow.com/questions/28872396/haskells-filterm-with-filterm-x-true-false-1-2-3
-- https://byorgey.wordpress.com/2007/06/26/deducing-code-from-types-filterm/

-- filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
-- filter  ::            (a ->   Bool) -> [a] ->   [a]

import Control.Monad  -- for liftM liftM :: Monad m => (a -> r) -> m a -> m r

filterM' :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM' p [] = return []           -- base case
filterM' p (x:xs) =                 -- recursive case
    let rest = filterM' p xs in     -- type of "rest" is m[a]
      do b <- p x
         if b then liftM (x:) rest  -- liftM :: (a -> [b]) -> [a] -> [[b]]
              else            rest

--
--
-- filterM' (const [False, True]) [1,2,3]                 ----  in this case, m is [].
--
-- recursion structure
--
-- filterM' (const [True, False]) (x:xs)
--     let restN = filterM' (const [True, False]) xs   
--      do b <- (const [True, False]) x                    ----  b = True and False
--         if b then liftM (x:) restN                      ----  liftM (x:) [[...],[...],...[...]] = [x:[...],x:[...], ..., x:[...]]            
--              else            restN                      ----  [[...],[...],...[...]] 
--
--      so we have :   [[x,...],[x,...],...,[x,...],[...],[...],...[...]] 
--                       <-----------T------------> <--------F--------->    ~~~  predicate
--       
-- 1st recursion
--   rest1 = filterM' (const [True, False]) (1:[2, 3)]
--     T : lift (2:) rest3
--     F : rest3
--      [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
--        <-------T--------> <------F----------->    ~~~ predicate 
--
-- 2nd recursion
--   rest2 = filterM' (const [True, False]) (2:[3])
--     T : lift (2:) rest3
--     F : rest3
--   so rest2 = [[2,3],[2],[3],[]]
--                <--T---> <-F-->       ~~~ predicate
--
-- 3rd recursion
--   rest3 = filterM' (const [True, False]) (3:[])
--     T : lift (3:) rest4
--     F : rest4
--   so rest3 = [[3]], [[]]
--                T     F                ~~~ predicate
--
-- 4th recursion 
--   rest4 = filterM' (const [True, False]) []
--   we have the base case such that filterM' p [] = return [],
--   so rest4 is [[]] 
--
--