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], []]. Extending this if the given input list contains two elements [1,2] the predicate would be mapped one by one on each of the elements and the result combined which means the output should be [[1], [], [2], []] But the powerset of [1,2] is definitely not that. Please could someone help me in getting my head around with how filterM is working in this case. Thanks, Shishir
From base-4.6.0.1 [1] the filterM is implemented like this:
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 filterM (\x -> [True, False]) [1,2] is filterM (\x -> [True, False]) (1:[2]) do flg <- (\x -> [True, False]) 1 ys <- filterM (\x -> [True, False]) [2] return (if flg then x:ys else ys) do flg <- [True, False] ys <- [[2], []] return (if flg then 1:ys else ys) You get the idea. You'll end up with [[1,2],[1],[2],[]] Hope this helps, Alexey Shmalko [1] https://hackage.haskell.org/package/base-4.6.0.1/docs/src/Control-Monad.html
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ï
participants (3)
-
Alexey Shmalko -
Chaddaï Fouché -
Shishir Srivastava