没有方法的类型类，用作约束：他们有字典吗？

Question

如果我使用类型class 来重载方法，那是在 'dictionary passing style' 中实现的。也就是说，该方法获得了一个额外的参数（没有出现在表面 Haskell 中）；为了解决重载问题，该方法按其 'proper' 参数的类型查找字典；并从字典中提取方法实现。 As described in this q, for example.

但是没有方法的 typeclasses 呢？它们可以用作约束。有没有他们的字典？它包含什么？

具体例子：

module M  where

class C a             -- no methods
                      -- no instances in module M
f :: C a => a -> Bool
f x = blah

此模块中没有 C 的实例，因此如果 M 被导入到其他模块（具有 C 个实例），f 的字典如何查找编码？

通常情况是 class C 有方法； f 等式的 RHS 上有对他们的调用；所以想要的 C a 被编码为方法调用的字典查找。

补充问题：（如果有人还在听的话）

2a。对于具有 superclass 约束的无方法类型classes：约束在字典中的什么位置？ comment on a ticket from SPJ 似乎暗示它是字典数据构造函数的参数。

2b。对于具有约束的无方法类型 class 实例：同样，约束在字典中的位置？

动机

@Daniel 在评论中询问这些问题的动机。除了更好地了解编译器内部结构之外...

GHC 将表面 Haskell 转换为内部表示：系统 F_C，它在每个函数应用程序中都有显式类型签名。（这些应用程序必须包括向字典申请 class。）我试图了解 class 的所有类型相关组件和实例声明在字典中的位置；弄清楚 F_C 中的项如何得到与原始 Haskell 等效的表示。然后我不明白 [typeclasses without methods] 如何适应。因为那些 classes 不能直接作为术语出现在表面 Haskell 中，而只能作为约束。那么它必须是这样一个 class 的字典，在术语级别代表它。

如果你想问这是怎么回事：F_C中似乎有一个限制，它不能代表功能依赖。与无法生成类型级证据有关。然后我想了解关于 FunDeps 的限制 arises/what 不能（或目前不能）表示？

Answer 1

Is there a dictionary for [typeclasses without methods]? What does it contain?

是的，有一个没有字段的字典。

比较：

class Monoid a where
    mempty :: a
    mappend :: a -> a -> a
data DictMonoid a = DictMonoid a (a -> a -> a)

class C a
data DictC a = DictC

If M gets imported into some other module (with C instances) how is f's dictionary lookup encoded?

类型推断用于确定调用f时需要什么实例；然后 GHC 在其已知实例集合（=已知字典）中查找该类型。

此过程的一个可能结果是我们确定需要的实例是多态的，并且没有完全多态的实例。然后将适当的约束（例如 C a 或 C m 或其他）附加到调用 f 的任何术语的推断类型 - 然后将其编译为接受字典的函数代表 f 将其传递。

For no-method typeclasses with superclass constraints: Where do the constraints go in the dictionary?

某处。您无法通过表面语言进行观察来区分不同的地方。例如，考虑：

class Semigroup a => Monoid a where mempty :: a
data DictMonoid1 a = DictMonoid1 (DictSemigroup a) a
data DictMonoid2 a = DictMonoid2 a (DictSemigroup a)

这是关于将超类字典放在哪里的仅有的两种选择。但它可能有什么不同呢？

好的，但是你问的是无方法类型类。但答案是一样的。你无法分辨超类字典的存储顺序。

class (A a, B a) => C a
data DictC1 a = DictC1 (DictA a) (DictB a)
data DictC2 a = DictC2 (DictB a) (DictA a)

你能做些什么来区分它们？没有。

For no-method typeclass instances with constraints: Again where do the constraints go in the dictionary?

无处可寻。它们成为调用者必须提供以接收字典的参数。当然，新词典可能会关闭所提供词典的特定字段。示例：

class Ord a where compare :: a -> a -> Ordering
data DictOrd a where DictOrd (a -> a -> Ordering)

instance (Ord a, Ord b) => Ord (a, b) where
    compare (a,b) (a',b') = compare a a' <> compare b b'
instanceOrdTuple :: DictOrd a -> DictOrd b -> DictOrd (a,b)
instanceOrdTuple (DictOrd comparea) (DictOrd compareb)
    = DictOrd $ \(a,b) (a',b') -> comparea a a' <> compareb b b'

好的，但是你问的是无方法类型类。但答案并没有太大的不同。实例的约束字典没有存储在任何地方，就像以前一样；唯一的区别是现在我们也可以确定即使提供的字典的字段也没有关闭。

class A a where whateverA :: a -> Int
class B a where whateverB :: Int -> a
class C a
data DictA a = DictA (a -> Int)
data DictB a = DictB (Int -> a)
data DictC a = DictC

instance (A a, B a) => C [a]
instanceCList :: DictA a -> DictB a -> DictC [a]
instanceCList (DictA whateverAa) (DictB whateverBa) = DictC

以下评论回复旧版问题

There's no instances for C in this module, so the compiler can't discharge fs constraint.

不需要。 f 被编译为一个函数，该函数以字典作为参数；无需创建字典来编译 f，只需编译其调用者即可。

The compiler can't discharge the C Char constraint arising from the equation for y. What does it do?

报告无法解除C Char约束，退出失败。（这甚至算不上是一个问题——自己试试看吧！）

没有方法的类型类，用作约束：他们有字典吗？

typeclasses without methods, used as constraints: do they get dictionaries?

haskell

typeclass