Take the 2-minute tour ×

Is it possible in (GHC) Haskell to define an existentially-quantified newtype? I understand that if type classes are involved it can't be done in a dictionary-passing implementation, but for my purposes type-classes are not needed. What I'd really like to define is this:

newtype Key t where Key :: t a -> Key t

But GHC does not seem to like it. Currently I'm using data Key t where Key :: !(t a) -> Key t. Is there any way (perhaps just using -funbox-strict-fields?) to define a type with the same semantics and overhead as the newtype version above? My understanding is that even with strict fields unboxed there will still be an extra tag word, though I could be totally wrong there.

This is not something that's causing me any noticeable performance issues. It just surprised me that the newtype was not allowed. I'm a naturally curious person, so I can't help wondering whether the version I have is being compiled to the same representation or whether any equivalent type could be defined which would be.

share|improve this question
I'm actually somewhat surprised that there are any sensible examples of existentials without a context, but you have found one that looks somewhat useful. –  augustss May 4 '11 at 22:47
Surprisingly, it's not even the only GADT I've found myself wanting which could be a newtype. At one point I tried to define one that applies a type constructor to a phantom type parameter, e.g. newtype F f t a where F :: t a -> F f t (f a). It's hard to explain why it's useful in such a short space here, but I actually did find myself wanting such a beast. –  mokus May 4 '11 at 23:02

2 Answers 2

No, according to GHC:

A newtype constructor cannot have an existential context

However, data is just fine:

{-# LANGUAGE ExistentialQuantification #-}

data E = forall a. Show a => E a

test = [ E "foo"
       , E (7 :: Int)
       , E 'x'

main = mapM_ (\(E e) -> print e) test


*Main> main

Logically, you do need the dictionary (or tag) allocated somewhere. And that doesn't make sense if you erase the constructor.

Note: You can't unbox functions though, as you seem to be hinting at, nor polymorphic fields.


Removing the -XGADTs helps me think about this:

{-# LANGUAGE ExistentialQuantification #-}

data Key t = forall a. Key !(t a)

As in, Key (Just 'x') :: Key Maybe

enter image description here

So you want to guarantee the Key constructor is erased.

Here's the code in GHC for type checking the constraints on newtype:

-- Checks for the data constructor of a newtype
checkNewDataCon con
  = do  { checkTc (isSingleton arg_tys) (newtypeFieldErr con (length arg_tys))
        -- One argument
    ; checkTc (null eq_spec) (newtypePredError con)
        -- Return type is (T a b c)
    ; checkTc (null ex_tvs && null eq_theta && null dict_theta) (newtypeExError con)
        -- No existentials
    ; checkTc (not (any isBanged (dataConStrictMarks con)))
          (newtypeStrictError con)
        -- No strictness

We can see why ! won't have any effect on the representation, since it contains polymorphic components, so needs to use the universal representation. And unlifted newtype doesn't make sense, nor non-singleton constructors.

The only thing I can think of is that, like for record accessors for existentials, the opaque type variable will escape if the newtype is exposed.

share|improve this answer
I know that it's not allowed, what I'm getting at is why it couldn't be allowed in the specific example I gave, or whether any workaround exists to get a similarly efficient runtime representation. What dictionary does my example need? There is no typeclass. The sole function of this type is to "forget" a phantom type parameter. –  mokus May 4 '11 at 21:47
Updated to talk more about the representation issues the newtype would encounter. –  Don Stewart May 4 '11 at 22:00
Wouldn't that argument apply equally well to newtype Identity a = Identity a? Or to 'newtype Key f a = Key (f a)'? –  mokus May 4 '11 at 22:07
Hmm. Yes, that's a good point! It is why you can't have unlifted newtypes, though. I think the issue then is related to the similar problem for accessors for records of existential type, which would cause the opaque context to escape. Unwrapping the newtype would have a similar effect (though you can imagine this working, as long as the constructor wasn't erased too early). –  Don Stewart May 4 '11 at 22:11
Hmm. It would make sense from a practical perspective if matching on newtypes is handled differently from data types at some point inside the compiler, which I know to some extent it is since newtypes don't get wrapper functions. In that case it sounds to me more of a "we just don't do that because it's extra work and nobody but mokus has ever even wanted it" ;). –  mokus May 4 '11 at 22:18

I don't see any reason it couldn't be made to work, but perhaps ghc has some internal representation issues with it.

share|improve this answer
Yeah, I think that's the only thing that makes sense. The newtype can't be erased too early, since the existential type would be made visible in GHC's typed translation. Otherwise, it does seem a legit thing to do. –  Don Stewart May 4 '11 at 22:14
I suspected it probably comes down to something like this. If nothing else, doesn't GHC pass type equality witnesses and such in Core? I presume those would appear as dictionaries carried in the record and unpacked by pattern matching. Even though they don't exist at runtime, the fact they exist in Core would mean that newtypes have to have a "no extra fields except ~ dictionaries rule, which seems rather ad-hoc. –  mokus May 4 '11 at 22:21
What ghc does now and what it should do are two different things. The current treatment of newtype is unsound. Perhaps you should put in an enhancement request on trac, and maybe Simon will make it work. –  augustss May 4 '11 at 22:44
Interesting. Are you referring to hackage.haskell.org/trac/ghc/ticket/1496 or some other unsoundness? I knew the existing GeneralizedNewtypeDeriving implementation could be used to break hidden invariants, but I didn't realize it could actually be used to implement unsafeCoerce! –  mokus May 5 '11 at 13:53
Also, the curious fact that Core apparently contains type-equality assertions for newtypes is probably a big reason newtypes can't have existential types. As I understand it, System F doesn't have existential types, so there's nothing for it to be equal to. –  mokus May 5 '11 at 14:01

Your Answer


