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]
xaosenkosmos
Oh man is that hard for me to grok, mostly because I haven't internalized the list monad.
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 whereflgis mentioned, that simply throws away thexand 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 ysmakes some sense: we will magically run it twice, once withflgTrue 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.ys <- filterM p xsis run once for each value of flg. Maybe the optimizer catches this, maybe not.The reduction of
m >>= f => concatMap f mcan happen at compile time, though. Higher order functions and classy types aren't necessarily expensive in Haskell.rfilterM :: Monad m => (a -> m Bool) -> [a] -> m [a] rfilterM f [] = return [] rfilterM f (x:xs) = do mxs <- rfilterM f xs; pred <- f x if pred then return (x:mxs) else return mxs powerset' = rfilterM (const [True,False]) main = do print $ powerset' [1,2,3]I wonder if you can implement filterM as a combination of smaller functions? (Like how mapM is sequence . map f.)
I 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.