Why has "map (filter fst)" the type "[[(Bool, a)]] -> [[(Bool, a)]]"?

Question

I'm trying to understand why the function

map (filter fst)

has the type

[[(Bool, a)]] -> [[(Bool, a)]]

How can "filter fst" work if filter must receive a function which returns a Bool-Type and fst just returns the first element of a tuple?

filter :: (a -> Bool) -> [a] -> [a]
fst :: (a, b) -> a

Can anyone explains me? Thanks ;)

Answer 1

How can "filter fst" work if filter must receive a function which returns a Bool-Type and fst just returns the first element of a tuple?

In a sense, you've answered your own question! Let's break it down:

filter must receive a function which returns a Bool-Type

OK, so let's look at what you're passing it: fst. Is fst a function? Yes, it is, so we've got the first part down. Does it return a Bool? Well, let's look at what it does:

fst just returns the first element of a tuple

So if the first element of a tuple is a Bool, then yes, it does return a bool! If the first element of a tuple is anything other than a Bool, though, it doesn't and will fail the typecheck.

Let's have another look at the types you put up. I'm going to change the names of the type variables just to make things clearer:

filter :: (a -> Bool) -> [a] -> [a]
fst :: (b, c) -> b

fst takes an (b, c) and returns an b, and filter is expecting a function which takes an a and returns a Bool. We are passing in fst, so the a above must be (b, c) as that's the first parameter of fst. The return value of the function we pass into filter must be a Bool, so b above must therefore be a Bool. And c can be anything, because it's not used by filter at all. Substituting the values for a and b gives us a final type for filter fst of:

filter fst :: [(Bool, c)] -> [(Bool, c)]

Finally, the type of map is:

map :: (d -> e) -> [d] -> [e]

(Again, I've renamed the type variables here, just to differentiate them from the ones we've used above, but remember it doesn't actually matter what they're called so long as they're consistent within the scope of the type annotation)

map (filter fst) passes the filter fst we defined above as the first parameter to map. Substituting the parameter for d and the result for e we can see this function must be [(Bool, c)] -> [(Bool, c)], in other words both d and e are (Bool, c). Plugging those into the function we arrive at the final type:

map (filter fst) :: [[(Bool, c)]] -> [[(Bool, c)]]

Answer 2

fst is a function that returns a boolean as long as you restrict the tuples to have a Boolean as their first element (the second element can be anything, hence the (Bool, a)

Answer 3

:t filter    -- (a -> Bool) -> [a] -> [a]
:t fst       -- (a,b) -> a

But, we could also exchange type variables for fst to get:

:t fst       -- (c,b) -> c

So, the first argument of filter has type a -> Bool, while fst itself is (c,b) -> c. Now we try to combine this (I think this is called unification):

1st arg of filter:  a     -> Bool
fst:                (c,b) -> c

From this, we can infer that c must be Bool (since the right hand side has to be equal) and obtain:

1st arg of filter:  a        -> Bool
fst:                (Bool,b) -> Bool

From the above, we infer that a must be (Bool,b), and obtain:

1st arg of filter:  (Bool,b) -> Bool
fst:                (Bool,b) -> Bool

And we are done.

Answer 4

Since I already wrote this down before danielpwright's answer was posted, I post it anyway. I'm just going through my thought process for the type of filter fst here.

First, write down the type signatures (change fst so that its type variable names don't clash with those of filter):

filter :: (a -> Bool) -> [a] -> [a]
fst :: (b, c) -> b

Match (a -> Bool) with ((b, c) -> b) :

b has to be Bool, which means that a has to be (Bool,c)

By specializing filter with this information it becomes:

filter :: ((Bool,c) -> Bool) -> [(Bool,c)] -> [(Bool,c)]

which leads to

filter fst :: [(Bool, c)] -> [(Bool, c)]