CODEWITHSUNDEEP
haskelltypes
SavannahGemp
SavannahGemp

Reputation: 405

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

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

Upvotes: 2

Views: 122

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

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].

Upvotes: 4

Related Questions