What is the type of (==) with only one argument in Haskell

user_10484793 0
Viewed 116

I am given the following function and I have to give the most general type.

\x y -> (==)(map x y)

My approach is on the picture attached. The solution is different tho, it is

Eq b=> (a->b)->[a]->[b]->Bool

I do no understand where the [b] is coming from.

Update: I found out that the type of 

\x y z -> (==)(map x y) z

Is the same as the type of my original function. So basically you can drop one of the arguments in the lambda function but it's still kinda there, as we know that (==) takes 2 arguments? But why?

enter image description here

haskell types
1 Answers

Short answer: it originates from the fact that the two operands of the (==) should have the same type.

Let us derive the type for \x y -> (==) (map x y). We can look up the types for (==) :: Eq c => c -> c -> Bool and map :: (a -> b) -> [a] -> [b].

Since we apply x :: d and y :: e to map, that thus means that:

map :: (a -> b) -> [a] -> [b]
x   ::    d
y   ::              e
-----------------------------
d ~ a -> b, e ~ [a]

So x has type a -> b, and y has type [a].

Now we know that map x y has type map x y :: [b]. This is the parameter in a function application with (==). We thus can derive the type for (==) (map x y) as:

(==)    :: Eq c =>  c -> c -> Bool
map x y ::         [b]
----------------------------------
c ~ [b]

So since c ~ [b], this thus means that the type of (==) (map x y) :: Eq [b] => [b] -> Bool, and thus that \x y -> (==) (map x y) has type \x y -> (==) (map x y) :: Eq [b] => (a -> b) -> [a] -> [b] -> [b].

Since it holds that:

instance Eq a => Eq [a]

We can thus change the type constraint from Eq [b] to just Eq b.

Update: I found out that the type of

\x y z -> (==)(map x y) z

Since (==) (map x y) is a function, the above indeed holds, since this is the opposite of η-reduction [Haskell-wiki].

user_675790
Related