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 ;)
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)]]