1

I was doing a past paper and was very confused by this question:

enter image description here

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

Improve this question
7
  • a is any type, Int is one of any, but so is [Int] and [[Int]] and so on. Commented May 2, 2024 at 2:16
  • 2
    Does it help if I say the first pairer has type a -> [a] and the second pairer has type b -> [b]? Commented May 2, 2024 at 2:17
  • so a can be a list as well, a can represent anything? @cafce25 Commented May 2, 2024 at 3:22
  • 3
    Yes, a can be any type. Commented May 2, 2024 at 3:23
  • 1
    As cafce25 has said, a can be [a]. I thought this might be confusing to you because it is not obvious that the two as are different type variables. If you change the names a bit, it might be easier to see that a can be [b]. Commented May 2, 2024 at 3:27

1 Answer 1

Reset to default
2

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 ids are distinct, otherwise we could not apply them in this way.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Another interesting/puzzling case: while pairer . pairer is okay, (\f -> f . f) pairer isn't; in fact, the lambda forces us into the regime that OP was originally thinking in, where one type must be chosen once and for all for a (at least locally, inside the lambda).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.