```
> import Control.Monad
```

The traditional way to generate the powerset of a list of elements is the following

```
> powerset :: [a] -> [[a]]
> powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs
> powerset [] = [[]]
```

```
ghci> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
```

But, I found this little gem of a way hidden in the Haskell wiki.

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

This version runs a filter using the List as the underlying monad. Let’s see why this works on `[1,2,3]`

.

First, here is the definition of filterM

```
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)
```

and it’s expansion for `[1,2,3]`

in `powerset2`

```
powerset2 [1,2,3]
== filterM (const [True,False]) [1,2,3]
== [True,False] >>= \flg ->
filterM (const [True,False]) [2,3] >>= \ys ->
return (if b then (1:ys) else ys)
```

There we have it. Another use of List for computations binding on multiple return values (Bool in this case).

Advertisements