filterM function

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

filterM function

Shishir Srivastava
Hi, 

Continuing on from my previous question about powerset using filterM - Thanks to Alexey anChaddaï. 

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 

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

Re: filterM function

Magnus Therning
On 22 April 2015 at 10:31, Shishir Srivastava
<[hidden email]> 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: [hidden email]   jabber: [hidden email]
twitter: magthe               http://therning.org/magnus
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: filterM function

Mike Meyer
In reply to this post by Shishir Srivastava
On Wed, Apr 22, 2015 at 3:31 AM, Shishir Srivastava <[hidden email]> 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.

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

Re: filterM function

Shishir Srivastava
In reply to this post by Shishir Srivastava
Hi Mike, 

Thanks for your response. I was aware that 'casting' doesn't really fit in Haskell vocab but for the lack of better word used it.

My question was however more towards the usage of [Bool] in the 'if' statement of the filterM function.

More precisely - How does 'if [True, False] then x else y' work , because when I do this in GHCi it throws up the following error ?

>>Couldn't match expected type `Bool' with actual type `[Bool]'

Clearly the 'if' construct does not take a list of Boolean but a single Boolean value so how does filterM use it in it's implementation.

Hope have made myself clear this time.

Thanks,
Shishir

 
From: Mike Meyer <[hidden email]>
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell <[hidden email]>
Cc: 
Date: Wed, 22 Apr 2015 04:15:31 -0500
Subject: Re: [Haskell-beginners] filterM function
On Wed, Apr 22, 2015 at 3:31 AM, Shishir Srivastava <[hidden email]> 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.

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



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

Re: filterM function

Sylvain HENRY
You need to understand:
1) do-notation
2) Monad instance for List

1) do-notation is just syntactic sugar around (>>=) Monad operator. So:

filterM p (x:xs) = p x >>= \flg -> filterM p xs >>= \ys -> if flg then
x:ys else ys

2) Monad instance for List:
http://hackage.haskell.org/package/base-4.8.0.0/docs/src/GHC-Base.html#line-726

In particular: xs >>= f = [y | x <- xs, y <- f x]
or the equivalent: xs >>= f = concatMap f xs

-- filterM specialized for []
filterM :: (a -> [Bool]) -> [a] -> [[a]]
filterM _ [] = [[]]
filterM p (x:xs) = concatMap (\flg -> concatMap (\ys -> [if flg then
x:ys else ys]) (filterM p xs)) (p x)

powerset :: [a] -> [[a]]
powerset xs  = filterM (\x -> [True, False]) xs

i.e.
powerset [] = [[]]
powerset (x:xs)  = concatMap (\flg -> concatMap (\ys -> [if flg then
x:ys else ys]) (powerset xs)) [True,False]

i.e.
powerset [] = [[]]
powerset (x:xs)  = concatMap (\flg -> fmap (\ys -> if flg then x:ys
else ys) (powerset xs)) [True,False]

i.e.
powerset [] = [[]]
powerset (x:xs)  = let ys = powerset xs in fmap (x:) ys ++ ys


I would directly use the latter form instead of using filterM to
implement powerset.

Sylvain

2015-04-22 11:22 GMT+02:00 Shishir Srivastava <[hidden email]>:

> Hi Mike,
>
> Thanks for your response. I was aware that 'casting' doesn't really fit in
> Haskell vocab but for the lack of better word used it.
>
> My question was however more towards the usage of [Bool] in the 'if'
> statement of the filterM function.
>
> More precisely - How does 'if [True, False] then x else y' work , because
> when I do this in GHCi it throws up the following error ?
>
>>>Couldn't match expected type `Bool' with actual type `[Bool]'
>
> Clearly the 'if' construct does not take a list of Boolean but a single
> Boolean value so how does filterM use it in it's implementation.
>
> Hope have made myself clear this time.
>
> Thanks,
> Shishir
>
>
>>
>> From: Mike Meyer <[hidden email]>
>> To: The Haskell-Beginners Mailing List - Discussion of primarily
>> beginner-level topics related to Haskell <[hidden email]>
>> Cc:
>> Date: Wed, 22 Apr 2015 04:15:31 -0500
>> Subject: Re: [Haskell-beginners] filterM function
>>
>> On Wed, Apr 22, 2015 at 3:31 AM, Shishir Srivastava
>> <[hidden email]> 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.
>>
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: filterM function

Alexey Shmalko
In reply to this post by Shishir Srivastava
I see misunderstand comes from

flg <- p x

In fact in the following code flg has type Bool:

flg <- [True, False]

For lists, >>= (and therefore <-) assigns every value out of list to
flg and tries to proceed. The final `return` returns only a single
element out of result, and all the results are concatenated together.


On Wed, Apr 22, 2015 at 12:22 PM, Shishir Srivastava
<[hidden email]> wrote:

> Hi Mike,
>
> Thanks for your response. I was aware that 'casting' doesn't really fit in
> Haskell vocab but for the lack of better word used it.
>
> My question was however more towards the usage of [Bool] in the 'if'
> statement of the filterM function.
>
> More precisely - How does 'if [True, False] then x else y' work , because
> when I do this in GHCi it throws up the following error ?
>
>>>Couldn't match expected type `Bool' with actual type `[Bool]'
>
> Clearly the 'if' construct does not take a list of Boolean but a single
> Boolean value so how does filterM use it in it's implementation.
>
> Hope have made myself clear this time.
>
> Thanks,
> Shishir
>
>
>>
>> From: Mike Meyer <[hidden email]>
>> To: The Haskell-Beginners Mailing List - Discussion of primarily
>> beginner-level topics related to Haskell <[hidden email]>
>> Cc:
>> Date: Wed, 22 Apr 2015 04:15:31 -0500
>> Subject: Re: [Haskell-beginners] filterM function
>>
>> On Wed, Apr 22, 2015 at 3:31 AM, Shishir Srivastava
>> <[hidden email]> 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.
>>
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners