[Haskell-beginners] Powerset function

[Chaddaï Fouché]

On Tue, Apr 21, 2015 at 4:56 PM, Shishir Srivastava <
shishir.srivastava at 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ï
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150421/9c6a8b95/attachment.html>