haskell - 没有方法的类型类，用作约束 : do they get dictionaries?

Question

如果我使用类型类来重载方法，那是在“字典传递风格”中实现的。也就是说，该方法获得了一个额外的参数(没有出现在表面 Haskell 中)；为了解决重载，该方法按其“正确”参数的类型查找字典；并从字典中提取方法实现。 As described in this q, for example .

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

举一个具体的例子:

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 怎么样？的字典查找编码？

通常的情况是该类 C有方法；在 f 等式的RHS 上有调用他们;所以通缉 C a被编码为方法调用的字典查找。

补充q: (如果有人还在听)

2a.对于具有父类(super class)约束的无方法类型类:约束在字典中的什么位置？一个 comment on a ticket from SPJ似乎表明它是字典数据构造函数的参数。

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

动机

@Daniel 在评论中询问这些 q 的动机。除了更好地理解编译器内部......

GHC 将表面 Haskell 转换为内部表示:系统 FC，它在每个函数应用程序中都有明确的类型签名。 (这些应用程序必须包括应用类的字典。)我试图了解类和实例声明的所有类型相关组件在字典中的位置；弄清楚 FC 中的术语如何获得与原始 Haskell 等效的表示。然后我不明白 [没有方法的类型类] 是如何适应的。因为这些类不能直接作为表面 Haskell 中的术语出现，而只能作为约束出现。然后它必须是在术语级别表示它的此类的字典。

如果你想问这是怎么回事:FC 中似乎有一个限制，它不能表示函数依赖。与无法生成类型级证据有关。然后我想了解这种限制是如何产生的/FunDeps 不能(或目前不)代表什么？

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)

对于将父类(super class)字典放在何处，这是唯一的两种选择。但它可能有什么不同呢？

好的，但是您询问了无方法类型类。但答案是一样的。您无法分辨父类(super class)字典的存储顺序。

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约束并退出失败。 (这甚至算不上一个问题——你自己试试看吧!)