Haskell explicit forall with "missing" type parameter on lhs

Question

I was reading the source code of haxl-Haxl.Core I came upon the following piece of code

data BlockedFetch r = forall a. BlockedFetch (r a) (ResultVar a)

And realized that I don't fully understand the usage of ExplicitForall/ExistentialQuantification.

In what ways is the snippet above different from

data BlockedFetch r a = BlockedFetch (r a) (ResultVar a)

And why can I "omit" the type parameter on the lhs of the data declaration.

Answer 1

As others have mentioned, the example from the code is an example of an existential quantification, and so is totally different from the final example in the question.

The first thing to note is that nowadays GADT notation is often preferred for this. The type in GADT notation is:

data BlockedFetch r where
    BlockedFetch :: r a -> ResultVar a -> BlockedFetch r

We can explicitly bind a as follows:

data BlockedFetch r where
    BlockedFetch :: forall a. r a -> ResultVar a -> BlockedFetch r

This would be isomorphic to the following if we had free existential quantification:

data BlockedFetch r where
    BlockedFetch :: (exists a. (r a, ResultVar a)) -> BlockedFetch r

This, combined with a desire not to introduce new keywords, is what led to the old ExistentialQuantification syntax. The BlockedFetch data constructor has type

BlockedFetch :: forall r a. r a -> ResultVar a -> BlockedFetch r

and this is what is trying to be communicated with the syntax:

data BlockedFetch r = forall a. BlockedFetch (r a) (ResultVar a)

From this perspective the difference from having BlockedFetch r a is then the a would occur in the result of the data constructor type. Schematically, forall a. F a -> G is logically equivalent to (exists a. F a) -> G, but it is clearly not the case that forall a. F a -> G a is equivalent to (exists a. F a) -> G a as the latter is not even well-scoped.

Returning to

BlockedFetch :: forall r a. r a -> ResultVar a -> BlockedFetch r

if you don't understand existentials, but you do understand universal quantification, then you can understand what's going on in terms of that. Here we see that someone calling BlockedFetch, i.e. building a value with the data constructor, is free to choose whichever type they want for a. Someone consuming, i.e. pattern matching on, a value of type BlockedFetch R is essentially writing a function forall a. R a -> ResultVar a -> X and that function must work for any value of a, i.e. the person calling this function gets to choose a and this function must work with that choice.

Answer 2

Consider a simpler example:

data ShowBox = forall a. Show a => ShowBox a

Read it as

data ShowBox = whatever a. Show a => ShowBox a

and now it's clear that ShowBox can contain a value of any type as long as this type is an instance of Show. E.g.

ex :: [ShowBox]
ex = [ShowBox 'a', ShowBox (), ShowBox [1,2,3]]

So you can read

data BlockedFetch r = forall a. BlockedFetch (r a) (ResultVar a)

as "BlockedFetch contains an r a and ResultVar a for whatever a".

Answer 3

The difference is that you can (and in fact this happens a little further in the code) make a list of type [BlockedFetch request] where individual BlockedFetch have different a types (which you could not do with [BlockedFetch request a] - the a here has to be the same for the whole list). The comment above the snippet of code explains this nicely:

-- We often want to collect together multiple requests, but they return
-- different types, and the type system wouldn't let us put them
-- together in a list because all the elements of the list must have the
-- same type. So we wrap up these types inside the 'BlockedFetch' type,
-- so that they all look the same and we can put them in a list.
--
-- When we unpack the 'BlockedFetch' and get the request and the 'ResultVar'
-- out, the type system knows that the result type of the request
-- matches the type parameter of the 'ResultVar', so it will let us take the
-- result of the request and store it in the 'ResultVar'.

Roughly what happens in Haxl is that you want to have a way of fetching a bunch of values of different types in parallel from some remote store. The way you do this is by making a bunch of MVar which will contain the values you plan on getting. Then, in your code, you freely use these variables. However, and MVar blocks until it is "filled".

However, to fill the MVar, you only need to keep a reference to the MVar and a way of filling it - so at the end of the day you don't even need to know what the type is of the stuff the MVar will contain. That is an existential type - there exists some type a which the BlockedFetch is going to try to fill, but it will vary for different BlockedFetchs.