Why is "map (filter fst)" type "[[(Bool, a)]] & # 8594; [[(Bool, a)]]"?

Question

I'm trying to understand why a function

map (filter fst) 

has type

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

How does the “fst filter” work if the filter is to get a function that returns a Bool-Type and fst just returns the first element of the tuple?

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

Can someone explain to me? Thanks;)

Answer 1

How does the “fst filter” work if the filter is to get a function that returns a Bool-Type and fst just returns the first element of the tuple?

In a way, you answered your question! Let me break it:

the filter should get a function that returns a Bool type

Ok, let's see what you pass: fst . fst function? Yes, it is, therefore, we have the first part. Does he return a Bool ? Well, let's see what he does:

fst returns only the first element of the tuple

So, if the first element of the tuple is Bool , then yes, it returns bool! If the first element of the tuple is something other than Bool , it does not execute and will not output typecheck.

Let's take another look at the types that you put. I am going to change the names of type variables to make everything clearer:

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

fst takes (b, c) and returns b , and the filter expects a function that takes a and returns a Bool . We go through fst , so the above should be (b, c) as the first parameter of fst . The return value of the function we pass to filter should be Bool , so b above should be Bool . And c can be anything, because it is not used by the filter at all. Substituting the values ​​for a and b , we get the final type for filter fst of:

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

Finally, the map type:

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

(Again, I renamed the type variables here, just to distinguish them from the ones we used above, but remember that it doesn't really matter what they are called if they are consistent within the scope of the type annotation)

map (filter fst) passes filter fst , which we defined above as the first map parameter. Substituting the parameter for d and the result for e , we can see that this function should be [(Bool, c)] -> [(Bool, c)] , in other words, both d and e are (Bool, c) . Inserting them into the function, we get the final type:

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

Answer 2

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

Answer 3

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

But we could also swap type variables for fst to get:

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

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

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

From this we can conclude that c should be a Bool (since the right side should be equal) and get:

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

From the above it follows that a should be (Bool,b) and get:

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

And we are done.

Answer 4

Since I already wrote this before danielpwright's answer was sent, I will send it anyway. I'm just looking at my thought process for type filter fst here.

First write down the types of signatures (change fst so that the names of its types do not interfere with the filter names):

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

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

b must be Bool , which means a must be (Bool,c)

Specializing in filter with this information, it becomes:

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

that leads to

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

Answer 5

You just need to solve some type equations. Let the beginning:

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

Therefore, filter fst :: [a] -> [a] where a is a solution of the following equation of the type:

  a -> Bool = (b, c) -> b 

whence follows

  a = (b, c) Bool = b 

whence follows

  a = (Bool, c) 

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

Now we have:

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

So, map (filter fst) :: [a] -> [b] , where a and b are given by the following type of equation:

 a -> b = [(Bool, c)] -> [(Bool, c)] 

whence follows

 a = [(Bool, c)] b = [(Bool, c)] 

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

Answer 6

Like others, I want to solve equations like here; but I want to write them more visually, so that the output can be done in a more automatic way. We'll see.

 filter :: ( a -> Bool) -> [a] -> [a] fst :: (c,d) -> c -- always use unique type var names, ------------------------ -- rename freely but consistently filter fst :: [a] -> [a], a -> Bool ~ (c,d) -> c a ~ (c,d) , Bool ~ c a ~ (Bool,d) --------------------------- :: [(Bool,d)] -> [(Bool,d)] 

Purely mechanical material. :) With this,

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

Type variables in the final type can be freely renamed for readability (in agreement, of course).

The only thing my answer adds to what has already been shown in other answers here is advice (which I consider important): if you follow this simple discipline , writing one thing below the other , it is very easy to perform these type unifications very mechanically , automatically (thus reducing the chance of error).

For another example of this, including the actual type-based Prolog program, see Haskell: how to infer the type of an expression manually .