Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Powerset function (Shishir Srivastava)
2. Re: Powerset function (Alexey Shmalko)
3. Re: Powerset function (Chadda? Fouch?)
4. filterM function (Shishir Srivastava)
5. Re: filterM function (Magnus Therning)
6. Re: filterM function (Mike Meyer)
----------------------------------------------------------------------
Message: 1
Date: Tue, 21 Apr 2015 15:56:50 +0100
From: Shishir Srivastava <[email protected]>
To: beginners <[email protected]>
Subject: [Haskell-beginners] Powerset function
Message-ID:
<cale5rtvp76km+praxu1b25rbepk271qeophgkvvwxtmtqbu...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150421/fe6622f1/attachment-0001.html>
------------------------------
Message: 2
Date: Tue, 21 Apr 2015 18:23:59 +0300
From: Alexey Shmalko <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Powerset function
Message-ID:
<cafc2pc76mgpzv+cpo5h-863tzj2sg0vph1pubbzr+ys-e4w...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
>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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150421/94477e38/attachment-0001.html>
------------------------------
Message: 3
Date: Tue, 21 Apr 2015 18:41:05 +0200
From: Chadda? Fouch? <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Powerset function
Message-ID:
<canfjzrzgv_sdvh5y4yborfokthr6rjekuurqfp+baujdfo9...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Apr 21, 2015 at 4:56 PM, Shishir Srivastava <
[email protected]> 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-0001.html>
------------------------------
Message: 4
Date: Wed, 22 Apr 2015 09:31:01 +0100
From: Shishir Srivastava <[email protected]>
To: beginners <[email protected]>
Subject: [Haskell-beginners] filterM function
Message-ID:
<CALe5RTtNKiTGaAsW=hur-onypc7nxwjsdrdvlxwdwgu_7ho...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
Continuing on from my previous question about powerset using filterM -
Thanks to Alexey and Chadda?.
filterM is implemented as below -
----
filterM _ [] = return []
filterM p (x:xs) = do
flg <- p x
ys <- filterM p xs
return (if flg then x:ys else ys)
---
I still don't quite understand how 'flg' being a boolean [] is used in the
last 'if statement' of implementation because when I try to do the same
thing outside in GHCi it fails miserably even though I am casting it to
[Int] -
--
return (if [True, False] then "4" else "3")::[Int]
--
Offtopic : Also if someone can explain how do I reply to individual
mails/responses to my queries because I only get a digest on my gmail and
there is no way to isolate and reply to individual mails either this list's
page or from digest.
Thanks,
Shishir
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150422/6fca8b08/attachment-0001.html>
------------------------------
Message: 5
Date: Wed, 22 Apr 2015 10:41:11 +0200
From: Magnus Therning <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filterM function
Message-ID:
<CAAExw5uv6rQ9w2FFhKNAMOT44g4RMd+A+3dJxLBh8RVYEt2=f...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On 22 April 2015 at 10:31, Shishir Srivastava
<[email protected]> wrote:
> Hi,
>
> Continuing on from my previous question about powerset using filterM -
> Thanks to Alexey and Chadda?.
>
> filterM is implemented as below -
>
> ----
>
> filterM _ [] = return []
> filterM p (x:xs) = do
> flg <- p x
> ys <- filterM p xs
> return (if flg then x:ys else ys)
>
> ---
>
> I still don't quite understand how 'flg' being a boolean [] is used in the
> last 'if statement' of implementation because when I try to do the same
> thing outside in GHCi it fails miserably even though I am casting it to
> [Int] -
>
> --
> return (if [True, False] then "4" else "3")::[Int]
> --
`flg` has type `Bool`, not `[Bool]`.
> Offtopic : Also if someone can explain how do I reply to individual
> mails/responses to my queries because I only get a digest on my gmail and
> there is no way to isolate and reply to individual mails either this list's
> page or from digest.
I suspect you'll have to go to the list server and modify your
settings there; it sounds like you have instructed it to send digests,
so you need to change it to send every individual email.
Alternatively you switch to a more capable mail reader, e.g. mutt,
which handles digests better than gmail does.
/M
--
Magnus Therning OpenPGP: 0xAB4DFBA4
email: [email protected] jabber: [email protected]
twitter: magthe http://therning.org/magnus
------------------------------
Message: 6
Date: Wed, 22 Apr 2015 04:15:31 -0500
From: Mike Meyer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] filterM function
Message-ID:
<CAD=7u2cft4utjewspg3bb5ubrmv-zdao1qgaevaa3g4cbnq...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Apr 22, 2015 at 3:31 AM, Shishir Srivastava <
[email protected]> wrote:
> I still don't quite understand how 'flg' being a boolean [] is used in
> the last 'if statement' of implementation because when I try to do the
> same thing outside in GHCi it fails miserably even though I am casting it
> to [Int] -
>
> --
> return (if [True, False] then "4" else "3")::[Int]
>
"cast" is a misnomer in Haskell. When you add a type to an expression, you
aren't changing the type of the expression like a C-style cast, but picking
out a type from the set of possible types for that expression.
Ignoring the if part and and focusing on return, which has a type Monad m
=> a -> m a. [Int] is equivalent to [] Int, so [] would be the Monad, and a
is Int. While 3 can be an Int, "3", can't. So you could do return 3 ::
[Int] or equivalently return 3 :: [] Int to get [3], you can't do return
"3" :: [Int], because "3" can't be an Int. You can do return "3" ::
[String], since "3" is a string. Just to show the range of possibilities,
you can do return 3 :: IO Float, and get back 3.0 as an IO action. The
monad in the type is IO, and 3 can be interpreted as a Float.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150422/07616e99/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 82, Issue 27
*****************************************
