[Haskell-cafe] Re: how would this be done? type classes?existential types?

Ben Rudiak-Gould Benjamin.Rudiak-Gould at cl.cam.ac.uk
Thu Mar 23 09:51:17 EST 2006


Brian Hulley wrote:
> Is there a reason for using && instead of
> 
>       [exists a. Resource a=>a]
> 
> ?

Only that => looks like a function arrow, && looks like a tuple. I stole 
this notation from an unpublished paper by SimonPJ et al on adding 
existential quantification to Haskell. I'm not especially attached to it. 
Actually I rather like

     forall a | Resource a. a
     exists a | Resource a. a

> a) A value 'v' of type 'exists a. Resource a=>a 'would have to be 
> internally represented as something like (dictResource_t, value_t)

Yes.

> b) Given such a value, there is no syntactic way to distinguish the pair 
> from the value_t stored inside it, unlike the use of 'forall' where the 
> syntax for the constructor conveniently "represents" any dictionaries 
> that have been glued onto the value (ie pattern matching against R x 
> gives us back the dictionaries "R" and the plain value x)?

Yes, but that doesn't necessarily mean you can't work out when to construct 
and deconstruct these implicit tuples. That's exactly what the type 
inference process does with implicit type arguments, and implicit type 
returns are dual to that, so the process should be similar.

It is tricky, though. E.g. given (f (g "z")) where

    f :: forall a. [a] -> Int
    g :: String -> (exists b. [b])

in principle you should be able to call g first, getting a type b and a list 
[b], then instantiate f with the type b, then pass the list to it, 
ultimately getting an Int. But I don't know how to design a type inference 
algorithm that will find this typing. If on the other hand

    f :: (exists a. [a]) -> Int

then it's easy to do the right thing---which is a little odd since these two 
types for f are otherwise indistinguishable.

> Hope I'm not making this more confusing but I'm still trying to get my 
> head around all these invisible happenings regarding dictionaries so I 
> can visualise what's happening in terms of bytes and pointers in the 
> runtime....

Once you understand where the types go in System F, the dictionaries are 
easy: they always follow the types around. Any time you have

     forall a b c. (C1 a b, C2 b c) => ...

in the source, you have five corresponding parameters/arguments in GHC Core, 
one for each type variable and constraint. These are always passed around as 
a unit (at least prior to optimization). In principle you could box them in 
a 5-tuple. The dictionary values are nothing more or less than proofs that 
the corresponding constraints hold.

-- Ben



More information about the Haskell-Cafe mailing list