03:07 pm, 23 Feb 07

### powerset

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

And

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

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]

`import Control.Monad`

powerset :: [a] -> [[a]]

powerset = filterM (const [True, False])

And

`powerset [1,2,3]`

produces `[[1,2,3],[1,2],[1,3],[1],[2,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]

xaosenkosmosgaalOh man is that hard for me to grok, mostly because I haven't internalized the list monad.avvaand I were puzzling over it too; here's how we figured it out.First, in terms of types, yes, it agrees:

`(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): 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: 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: 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: 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: 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.

gaal`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.evanI wonder if you can implement filterM as a combination of smaller functions? (Like how mapM is sequence . map f.)

gaalevanI 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.

gaal## 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 :-)