Powerset function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Powerset function

Shishir Srivastava
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


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Powerset function

Alexey Shmalko
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


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Powerset function

Chaddaï Fouché
In reply to this post by Shishir Srivastava
On Tue, Apr 21, 2015 at 4:56 PM, Shishir Srivastava <[hidden email]> 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ï

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners