Function returning result of any constructor of a

Question

I'm currently having a fight with the typechecker when I try to create a function returning Thing a (where Thing is a GADT). A minimal contrived example:

{-#LANGUAGE GADTs, EmptyDataDecls #-}
module Main where

-- Define a contrived GADT
data TFoo
data TBar
data Thing a where
  Foo :: Int -> Thing TFoo
  Bar :: String -> Thing TBar

combine :: [Thing a]
combine = [Foo 1, Bar "abc"]

main :: IO ()
main = undefined

The typechecker gets unhappy that a doesn't match TBar. Presumably this is because it has already inferred that a is TFoo. But, this is surprising, because with regular sum types you can do:

data Thing = Foo Int | Bar String

combine :: [Thing]
combine = [Foo 1, Bar "abc"]

Is there anyway to return a type parametric over the GADT parameter?

Outside of the context of the contrived examples, I need GADTs so I can type certain functions to only take a Foo, but before that I need to also be able to just return a list of Things.

Answer 1

You've got your quantifiers mixed up.

combine :: [Thing a]

means (the forall is implicit in the syntax)

combine :: forall a. [Thing a]

Essentially, combine needs to be a [Thing a] no matter what a is, because a is chosen by the code that calls combine. Or, in another sense,

-- psuedo-Haskell
combine :: (a :: *) -> [Thing a]

combine is a function that takes a type as argument and promises to construct a list of Things of that type. The only possible definition of combine with this type signature is combine = [], plus a bunch of dumb ones like [undefined], etc. E.g. combine = [Foo 1] would not work either, because a is not being inferred, because it's not combine that sets a; it's the user.

You want

-- psuedo-Haskell
combine :: [exists a. Thing a]

which means "combine is a list of things, and each thing is a Thing of some unknown type" (and every Thing can be of a different type). The exists quantifier is the flipside of forall. It means the definition of combine can set whatever type it wants and the user will have to deal with it. Haskell doesn't support exists out-of-the-box, so you need to define an intermediate data type:

data SomeThing = forall a. SomeThing (Thing a)

The syntax is a bit backwards for using the universal quantifier to create existential quantification, but the idea is that you get

SomeThing :: forall a. Thing a -> SomeThing

which essentially erases the knowledge of what a is.

You can then have

combine :: [SomeThing]
combine = [SomeThing $ Foo 1, SomeThing $ Bar "abc"]