Skip to content

Instantly share code, notes, and snippets.

@ayu-mushi
Last active July 22, 2017 18:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ayu-mushi/87a88863488b4a6cb37cef305fc17114 to your computer and use it in GitHub Desktop.
Save ayu-mushi/87a88863488b4a6cb37cef305fc17114 to your computer and use it in GitHub Desktop.
Explanation of why `filterM (const [True, False])` maps list to its power set(list)
import Control.Monad
import Control.Applicative
-- filterM (const [True, False])
-- filterM :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
-- filterM p = foldr (\x -> liftA2 (\flg -> if flg then (x:) else id) (p x)) (pure [])
-- (<*>) :: [a -> b] -> [a] -> [b]
-- fs <*> xs = [f x | f <- fs, x <- xs]
-- foldr (\x -> (<*>) $ (\flg -> if flg then (x:) else id) <$> [True, False]) (pure []) [1,4,3]
-- diverge :: a -> [[a]] -> [[a]]
-- diverge x as = [f a | f <- map (\flg -> if flg then (x:) else id) [True, False], a <- as]
-- diverge :: a -> [[a]] -> [[a]]
-- diverge x as = [f a | f <- [(x:), id], a <- as]
diverge' :: a -> [[a]] -> [[[a]]]
diverge' x = map (\a -> [x:a, a])
diverge :: a -> [[a]] -> [[a]]
diverge x = concat . (diverge' x)
powerR :: [a] -> [[a]]
powerR xs = foldr diverge [[]] xs
powerL :: [a] -> [[a]]
powerL xs = foldl (flip diverge) [[]] xs
main :: IO ()
main = do
print $ filterM (const [True, False]) [4,3,6]
print $ diverge 6 [[]] -- > [[6],[]]
print $ diverge 3 [[6],[]] -- > [[3,6], [6], [3], []]
print $ diverge 4 [[3,6],[6],[3],[]] -- > [[4,3,6],[3,6],[4,6],[6],[4,3],[3],[4],[]]
print $ powerR [4,3,6] -- > [[4,3,6],[3,6],[4,6],[6],[4,3],[3],[4],[]]
print $ powerL [4,3,6] -- > [[6,3,4],[3,4],[6,4],[4],[6,3],[3],[6],[]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment