evan_tech

03:07 pm, 23 Feb 07

powerset

Beautiful Haskell implementation of math's "power set":

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

And powerset [1,2,3] produces [[1,2,3],[1,2],[1,3],,[2,3],,,[]].

Oh man is that hard for me to grok, mostly because I haven't internalized the list monad.
(It helped me to write out the definition of filterM, which has type Monad m => (a -> m Bool) -> [a] -> m [a].)

But roughly, it's saying "for each assignment of true and false over the values of the list, grab the true values".

[via Adam Langley via a private mailing list]

• For those of us who found this somwhat (but not totally) unaccessible, i'd recommend reading [[Schwartzian Transform]] to get into apprximately the right head-space, then [[Monads in functional programming]]. reply to this
• Oh man is that hard for me to grok, mostly because I haven't internalized the list monad. and I were puzzling over it too; here's how we figured it out.First, in terms of types, yes, it agrees:filtermM :: Monad m => (a -> m Bool) -> [a] -> m [a] -- or, concretized with [] for m: filtermM :: => (a -> [Bool]) -> [a] -> [[a]] (const [True, False]) sure has type (a -> [Bool]), so the currying filterM with it certainly does agree with the type of powerset. But why does it agree with the meaning?Here's the source of filterM, from GHC (it's in the source for Control.Monad):filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = do flg <- p x ys <- filterM p xs return (if flg then x:ys else ys) So what's up with (const [True, False]) ? This means a constant function returning [True, False]; same as a \_ -> [True, False]. The first line where flg is mentioned, that simply throws away the x and forces the constant function for a value, and so reduces to: flg <- [True, False]Before grokking the monadic stuff, this looks very weird indeed! For some value of intuitively, <- peels off one layer of monadicity from the right hand expression; what can flg be then? Let's put this on hold for a minute and look at an actual algorithm for computing a powerset:Go over every element in the set, represented as a list; on every element, recursively compute the powerset of the tail of the list (remaining elements to its "right"). Now accumulate into the results both that computed powerset, *and* that poweset with the current element injected into each (sub)set in the powerset. So if you take the result in the order you've shown:[[1,2,3],[1,2],[1,3],,[2,3],,,[]]you'll notice the first half is the same as the second with the element 1 prepended to each list. So now the expression if flg then x:ys else ys makes some sense: we will magically run it twice, once with flg True and the other False.How does the crazy control happen to fork off flg with *both* True and False? The magic's in the monad. The following isn't really in the Haskell libraries, but would have been if lists didn't have special syntax:instance Monad [] where m >>= f = concatMap f m -- (concatMap is spelled "map" in Perl.) return x = [x]Now, "we're in the List monad". This is a mysterious expression I heard many times until I relized all it means is that the bind in question is gets dispatched to List's Monad instance. Remember do-notation: do { flg <- [xs] ; foo } -- is equivalent to [xs] >>= \flg -> foo -- reduced further, with List's particular meaning: concatMap (\flg -> foo) [xs]So this is where the magical forking occurs! "In the List monad", every time you make a monadic bind -- that is, every line in a do expression! -- execution goes off trying every element in the list on the subsequent action, and accumulates all the results in one result list. reply to this
• I'm not sure about this, but I think that this implementation is inefficient because ys has to be computed twice as many times as necessary: ys <- filterM p xs is run once for each value of flg. Maybe the optimizer catches this, maybe not.The reduction of m >>= f => concatMap f m can happen at compile time, though. Higher order functions and classy types aren't necessarily expensive in Haskell. reply to this
•  You could implement filterM in reverse, I guess:rfilterM :: Monad m => (a -> m Bool) -> [a] -> m [a] rfilterM f [] = return [] rfilterM f (x:xs) = do mxs <- rfilterM f xs; pred <- f x if pred then return (x:mxs) else return mxs powerset' = rfilterM (const [True,False]) main = do print \$ powerset' [1,2,3]I wonder if you can implement filterM as a combination of smaller functions? (Like how mapM is sequence . map f.) reply to this
• Note though that the effects are also, uh, effected in reverse here, so this can mean quite a different thing than reverse =<< filterM if you're, say, in IO. reply to this
•  You might find looking over this old post of mine helpful, where I've produced a cheatsheet of what bind does for a bunch of different monads.I find these days I can actually use the list monad when it's applicable... it just took a bit of head-scratching at first. But oftentimes you're better off, for clarity reasons, just using a comprehension. reply to this
• To reply to sorta both your comments: it used to be that comprehensions were generalized for all monads, not just lists, so I guess you could express filterM directly with 'em... reply to this
• Anonymous

Great Explanation

Thanks for your explanation avva! I was struggling to understand this for two days, reading your comment I got it in 10 minutes :-) 