CODEWITHSUNDEEP
haskellmonads
Calpau
Calpau

Reputation: 919

What's the monad being used with =<< in this function?

The very first 1-Haskell-a-Day exercise confuses me to a point of no return. The objective is to filter out elements of a list unless it's equal to the one following. E.g.

> filterByPair [1, 2, 2, 2, 3, 3, 4]
[2,2,3]

(I was trying to make two offset lists, zip them into tuples and remove the tuples that didn't have the same number both times, e.g. [(2,2),(2,2),(3,3)], etc.) But the mind-blowingly simple solution uses the =<< binding operator:

filterByPair :: Eq a => [a] -> [a]
filterByPair = (init =<<) . group

I'm having trouble figuring that operator out. I don't get the same results in ghci when I try to use it:

> init =<< [2,3,4]
No instance for (Num [b0]) arising from the literal `2'

I find that in ghci I can use, say, replicate with =<<. It seems to be feeding each element of the list into the function:

> replicate 2 =<< [2,3,4]
[2,2,3,3,4,4]

So the first go-around is equivalent to:

> replicate 2 2
[2,2]

It somehow knows to put the list in the second argument of replicate, not the first, and to output them all in one big list rather than separate ones, like fmap does:

> fmap (replicate 2) [2,3,4]
[[2,2],[3,3],[4,4]]

I've read that the binding operator is defined by the monad being used. It's a monad function isn't it? Where's the monad with filterByPair? Does it have something to do with the Eq typeclass in its signature?

Likewise, if I use =<< on its own in ghci, what monad is being used there?

Upvotes: 4

Views: 191

Answers (1)

cdk
cdk

Reputation: 6778

First, filterPairs rewritten into pointful form for clarity:

filterPairs xs = group xs >>= init

We'll be able to get a good idea what's happening from the types alone.

xs    :: Eq a => [a]
group :: Eq a => [a] -> [[a]]
init  :: [a] -> [a]

(>>=) :: Monad m => m a -> (a -> m b) -> m b

The first argument to (>>=) is group xs :: [[s]], so if we substitute m ~ [] and a ~ [s] in (>>=) we'll get

(>>=) :: [[a]] -> ([a] -> [s]) -> [s]

So we're using the Monad instance of [] here, which is equivalent to concatMap (check the types!). Now we can rewrite filterPairs again

filterPairs xs = concatMap init (group xs)

Now if you figure out how concatMap, init and group work, you should be able to figure how the original filterPairs works.

Upvotes: 5

Related Questions