On Tue, Apr 21, 2015 at 4:56 PM, Shishir Srivastava < shishir.srivastava@gmail.com> wrote:
Hi,
In the 'learnyouahaskell' online book the powerset function is described like this -
---- powerset :: [a] -> [[a]] powerset xs = filterM (\x -> [True, False]) xs ----
And the filterM function is defined like this
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
--
The filterM function is said to be an extension of 'filter' function which maps the monadic predicate over the given list.
Now in powerset function the predicate returns a monad [True,False] for every element of the given list.
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], []].
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. A way to visualize that is to do : sequence . map (\x -> [[x],[]]) $ [1..3] you'll get [[1],[]] x [[2],[]] x [[3],[]] just apply "map concat" to get the powerset back. -- Jedaï