I was doing a past paper and was very confused by this question:
I tried to research about it, look at threads, watch youtube videos but I still do not understand it and it made me even more confused.
Pairer takes a value of any type and returns a list of that value:
pairer :: a -> [a]
Now the return type of the left pairer takes as input result of first pairer application but this returns a [a]
and pairer expects an a
, this is not compatible as the codomain of first needs to match with domain of second
Can someone please explain how pairer . pairer
is valid?
I tried to follow through and did not understand it as like I said above to my knowledge the return type of first function applied needs to match domain of second function
A polymorphic (or generic) function is actually an infinite family of functions. Your function has the polymorphic type
pairer :: forall a . a -> [a]
Consequently it works as the family of functions
pairer @Int :: Int -> [Int]
pairer @Bool :: Bool -> [Bool]
pairer @[Int] :: [Int] -> [[Int]]
pairer @(Int -> Bool) :: (Int -> Bool) -> [Int -> Bool]
...
where the type variable a
is being specialized to all the possible types. Any type is allowed here to replace a
(well, except for polymorphic types, but that does not matter here).
Because of that, it is possible that the composition
pairer @A . pairer @B
is well-typed: for that it suffices that the codomain of pairer @B
coincides with the comain of pairer @A
, and that is the case when A = [B]
.
Modern Haskell allows one to explicitly specify the wanted instantiation (the @...
in pairer @...
) but also allows the programmer to omit that and ask the compiler to infer it (type inference). Hence, we can also write
pairer . pairer
and the compiler will figure it out, choosing two different specializations that make it type-check. We are not really composing the same function with itself here, since its codomain is not the same as the domain -- we need two compatible specializations.
As an exercise, you can try to make the @...
part explicit (you might need the TypeApplications
and ScopedTypeVariables
extensions depending on your GHC version). Feel free to experiment. If you want another puzzling case, you can play with the identity function and note that id True
, id id True
, id id id True
, etc. are all well-typed and evaluate to True
. Here the types of the id
s are distinct, otherwise we could not apply them in this way.