数据族与单射类型族

Question

现在我们有了单射类型族，是否还有使用数据族而不是类型族的用例？

查看过去关于数据族的 Whosebug 问题，有 this question from a couple years ago discussing the difference between type families and data families, and this answer 关于数据族的用例。都说数据族的内射性是他们最大的优势

正在查看 docs on data families, I see reason not to rewrite all uses of data families using injective type families。

例如，假设我有一个数据族（我已经合并了文档中的一些示例以尝试压缩数据族的所有功能）

data family G a b
data instance G Int Bool = G11 Int | G12 Bool deriving (Eq)
newtype instance G () a = G21 a
data instance G [a] b where
   G31 :: c -> G [Int] b
   G32 :: G [a] Bool

我不妨重写为

type family G a b = g | g -> a b
type instance G Int Bool = G_Int_Bool
type instance G () a = G_Unit_a a
type instance G [a] b = G_lal_b a b

data G_Int_Bool = G11 Int | G12 Bool  deriving (Eq)
newtype G_Unit_a a = G21 a
data G_lal_b a b where
   G31 :: c -> G_lal_b [Int] b
   G32 :: G_lal_b [a] Bool

不言而喻，数据族的关联实例与类型族的关联实例以相同的方式对应。那么唯一剩下的区别是我们在类型命名空间中的东西更少了吗？

作为后续，在类型命名空间中减少内容有什么好处吗？我能想到的是，对于在 ghci 上玩这个的人来说，这将成为调试地狱 - 构造函数的类型似乎都表明构造函数都在一个 GADT 下......

Answer 1

您还遗漏了另一个细节 - 数据族创建新类型。类型族只能引用其他类型。特别是，数据族的每个实例都声明了新的构造函数。而且它非常通用。如果需要新类型语义，可以使用 newtype instance 创建数据实例。您的实例可以是一个记录。它可以有多个构造函数。如果你愿意，它甚至可以是 GADT。

正是type和data/newtype关键字的区别。单射类型族不会给你新的类型，在你需要的情况下使它们变得无用。

我知道你来自哪里。最初我遇到了同样的问题。然后我终于运行进入了一个有用的用例，即使没有类型 class 参与。

我想写一个 api 来处理几个不同上下文中的可变单元格，而不使用 classes。我知道我想用 IO、ST 中带有解释器的免费 monad 来做这件事，也许 unsafeCoerce 会进行一些可怕的黑客攻击，甚至把它塞进 State ].当然，这不是出于任何实际目的 - 我只是在探索 API 设计。

所以我有这样的事情：

data MutableEnv (s :: k) a ...

newRef :: a -> MutableEnv s (Ref s a)
readRef :: Ref s a -> MutableEnv s a
writeRef :: Ref s a -> a -> MutableEnv s ()

MutableEnv 的定义并不重要。只是标准的 free/operational monad 东西，其构造函数与 api.

中的三个函数相匹配

但我对将 Ref 定义为什么感到困惑。我不想要某种 class，就类型系统而言，我希望它是一个具体的类型。

然后一天深夜我出去散步，它击中了我 - 我本质上想要的是一种类型，其构造函数由参数类型索引。但它必须是开放的，不像 GADT - 可以随意添加新的口译员。然后它就撞到了我。这正是数据族的含义。一个开放的、类型索引的数据值系列。我可以用以下内容完成 api：

data family Ref (s :: k) :: * -> *

然后，处理 Ref 的基础表示就没什么大不了的了。每当定义 MutableEnv 的解释器时，只需创建一个数据实例（或更有可能是新类型实例）。

这个确切的例子并不是很有用。但它清楚地说明了数据族可以做单射类型族不能做的事情。

Answer 2

type family T a = r | r -> a
data family D a

单射类型族T满足单射公理

if T a ~ T b then a ~ b

但是数据族满足更强的生成性公理

if D a ~ g b then D ~ g and a ~ b

（如果您愿意：因为 D 的实例定义了不同于任何现有类型的新类型。）

事实上D本身是类型系统中的合法类型，不像T这样的类型族，它只能出现在像T a这样完全饱和的应用程序中。这意味着

D 可以是另一个类型构造函数的参数，例如 MaybeT D。（MaybeT T 是非法的。）
您可以为 D 定义实例，例如 instance Functor D。（您不能为类型族 Functor T 定义实例，并且无论如何它都将无法使用，因为实例选择 map :: Functor f => (a -> b) -> f a -> f b 依赖于这样一个事实，即您可以从类型 f a确定 f 和 a；为了使它起作用，f 不允许随类型族变化，即使是单射族。）

Answer 3

关于向 Haskell 添加依赖类型的 explains the distinction between my two examples perfectly. It has reminded me of something I read in Richard Eisenberg's thesis 我认为由于这个问题的核心是内射性和生成性，所以值得一提的是 DependentHaskell 将如何处理这个（当它最终被实施时，如果现在提出的量词最终被实施）。

以下内容基于上述thesis的第56页和第57页（4.3.4匹配性）：

Definition (Generativity). If f and g are generative, then f a ~ g b implies f ~ g

Definition (Injectivity). If f is injective, then f a ~ f b implies a ~ b

Definition (Matchability). A function f is matchable iff it is generative and injective

在我们现在所知的 Haskell (8.0.1) 中，可匹配（类型级）函数完全由新类型、数据和数据族类型构造函数组成。将来，在 DependentHaskell 下，我们将获得的新量词之一将是 '->，这将用于表示可匹配的函数。换句话说，将有一种方法通知编译器类型级函数是生成的（目前只能通过确保该函数是类型构造函数来完成）。

数据族与单射类型族

Data families vs Injective type families

haskell

ghc

type-families