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.Monadpowerset :: [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.
I heard about the story of the murder-suicide of wrestler Chris Benoit and his wife recently. I mainly paid interest because my paper included a nice graphic of every pro wrestler who’d died in recent years…and it’s a big number…which made for top quality reading.
Further showing their commitment to addressing the most pressing issues facing Louisiana in the wake of Katrina, the state legislature