evan_tech

Oh man is that hard for me to grok, mostly because I haven't internalized the list monad.

avva 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],[1],[2,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.