<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Apr 21, 2015 at 4:56 PM, Shishir Srivastava <span dir="ltr"><<a href="mailto:shishir.srivastava@gmail.com" target="_blank">shishir.srivastava@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi, <div><br></div><div>In the 'learnyouahaskell' online book the powerset function is described like this - </div><div><br></div><div>----</div><div><font face="monospace, monospace">powerset :: [a] -> [[a]]<br></font></div><div><font face="monospace, monospace">powerset xs = filterM (\x -> [True, False]) xs</font></div><div>----</div><div><br></div><div>And the filterM function is defined like this </div><div><br></div><div><font face="monospace, monospace">filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]</font><br></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">--</font></div><div><br></div><div><font face="arial, helvetica, sans-serif">The filterM function is said to be an extension of 'filter' function which maps the monadic predicate over the given list. </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Now in powerset function the predicate returns a monad [True,False] for every element of the given list.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">So for e.g. if the input list was only [1] the output of filterM will understandably be the cartesian product of [True, False] x [1] = [[1], []]. <br></font></div></div></blockquote><div><br></div><div>No, this is not a single cartesian product. In a powerset, there's 2^N elements, not 2*N. A better way to imagine it is to come back to the sens of the list monad : it is often said that it encodes computations that may have several results. So here, for each element, either you keep the element (True) or you filter it out (False) and you branch out from that : if you keep it, you'll have this element followed by the filterM applied to the rest of the list (except there will be several result there too), if you filter it, you will only have the result of filterM applied to the tail.<br><br></div><div>A way to visualize that is to do :<br></div><div><br><span style="font-family:monospace,monospace">    sequence . map (\x -> [[x],[]]) $ [1..3]</span><br></div><div><br>you'll get [[1],[]] x [[2],[]] x [[3],[]]<br></div><div>just apply "<span style="font-family:monospace,monospace">map concat</span>" to get the powerset back.<br><br>-- <br></div><div>Jedaï <br></div></div></div></div>