Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why can't we define closed data families?

All of the following work:

{-# LANGUAGE TypeFamilies #-}

type family TF a
type instance TF Int = String
type instance TF Bool = Char

data family DF a
data instance DF Int = DFInt String
data instance DF Bool = DFBool Char

type family CTF a where
  CTF Int = String
  CTF Bool = Char
  CTF a = Double     -- Overlap OK!

...but this doesn't (as of GHC-8.2):

data family CDF a where
  CDF Int = CDFInt String
  CDF Bool = CDFBool Char
  CDF a = CDFOther Double
wtmpf-file24527.hs:16:19: error: parse error on input ‘where’
   |
16 | data family CDF a where
   |                   ^^^^^

Is it just that nobody has bothered to implement this yet, or is there a particular reason why it wouldn't make sense for data families to be closed? I have a data family where I'd rather like to keep the injectivity, but also the opportunity to make a disjoint catch-all instance. Right now, the only way I see to make this work is

newtype CDF' a = CDF' (CTF a)
like image 402
leftaroundabout Avatar asked Mar 22 '18 16:03

leftaroundabout


People also ask

What is a closed type family?

A closed type family has all of its equations defined in one place and cannot be extended, whereas an open family can have instances spread across modules. The advantage of a closed family is that its equations are tried in order, similar to a term-level function definition.

What is type family Haskell?

Type families are parametric types that can be assigned specialized representations based on the type parameters they are instantiated with. They are the data type analogue of type classes: families are used to define overloaded data in the same way that classes are used to define overloaded functions.


1 Answers

(Here I am only guessing, but I want to share this thought.)

Assume we can write

data family CDF a where
  CDF Int = CDFInt String
  CDF Bool = CDFBool Char
  CDF a = CDFOther Double

Now, what is the type of the value constructors induced by this definition? I would be tempted to say:

CDFInt   :: String -> CDF Int
CDFBool  :: Char   -> CDF Bool
CDFOther :: Double -> CDF a

... but the last one feels very wrong, since we would get

CDFOther @ Int :: Double -> CDF Int

which should be disallowed, since in a closed data family one would expect that a (non bottom) value of CDF Int must start with the CDFInt constructor.

Perhaps a proper type would be

CDFOther :: (a /~ Int, a /~ Bool) => Double -> CDF a

involving "inequality constraints", but this would require more typing machinery that currently available in GHC. I have no idea if type checking / inference would remain decidable with such extension.

By contrast, type families involve no value constructors, so this issue does not arise there.

like image 73
chi Avatar answered Sep 29 '22 10:09

chi