I’m currently working through the project euler puzzles as a way to learn the Haskell programming language. For one problem I needed to generate the power set of a list (the set containing all subsets). I figured it might be in the standard library, which I don’t know well, so I googled it.

What I found on evan_tech was this mind-blowing code snippet:

import Control.Monad

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

Yikes! Seems short…and the first two lines are just the includes and the prototype. The entire meat of the function is in the last line. But does it work?

*Main> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Of course it does .. but how. Check out Evan’s site for details. The short form is that it makes ingenious use of the List monad…which is the most confusing monad (IMHO) because lists seem so cuddly and familiar…lulls one into a false sense of security. Basically, the [True, False] says that for each element in the original list, I’m gonna want lists in the output which both do — and don’t include the original element. Makes sense at a high level…but where’s the looping? Well, turns out the List monad defines its >>= operator (bind) internally as concatMap (which is the only way you could do it…if you think about it). So the “Map” in concatMap generates the iteration.

Beautiful.

One Response to “Haskell Power”

I know it’s been ages since you posted this, but I just stumbled across it, and that’s just fantastic. Inefficient as hell, but fantastic none-the-less.

Something to say?