[Haskell-beginners] 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 <shishir.srivastava at gmail.com>:
> 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 <mwm at mired.org>
>> To: The Haskell-Beginners Mailing List - Discussion of primarily
>> beginner-level topics related to Haskell <beginners at haskell.org>
>> 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
>> <shishir.srivastava at gmail.com> 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
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>