没有方法的类型类，用作约束:它们是否获得字典? [英] typeclasses without methods, used as constraints: do they get dictionaries?

问题描述

如果我使用类型类重载方法，则以字典传递样式"实现.也就是说，该方法有一个额外的参数(在表面Haskell中不会出现)；为了解决重载，该方法按其适当"参数的类型查找字典；并从字典中拉出方法实现.如本q所述，例如.

If I'm using a typeclass to overload methods, that's implemented in 'dictionary passing style'. That is, the method gets an extra argument (that doesn't appear in surface Haskell); to resolve overloading the method looks up the dictionary by type of its 'proper' argument(s); and pulls a method implementation out of the dictionary. As described in this q, for example.

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

But what about typeclasses without methods? They can be used as constraints. Is there a dictionary for them? What does it contain?

例如:

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 的字典查找编码吗?

There's no instances for C in this module, so if M gets imported into some other module (with C instances) how is f's dictionary lookup encoded?

通常的情况是类 C 具有方法.关于Rcode的 f 方程式有呼吁；因此所需的 C a 被编码为方法调用的字典查找.

The usual situation would be that class C has method(s); there's calls to them on RHS of the equation for f; so the wanted C a is encoded as a dictionary lookup for the method call.

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

2a.对于具有超类约束的无方法类型类:约束在字典中的位置在哪里?SPJ机票上的评论似乎表明这是对字典的数据构造函数.

2a. For no-method typeclasses with superclass constraints: Where do the constraints go in the dictionary? A comment on a ticket from SPJ seems to suggest it's an argument to the dictionary's data constructor.

2b.对于具有约束的无方法类型类实例:约束再次在字典中的什么位置?

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

动机

@Daniel在评论中询问这些q的动机.除了仅了解编译器内部知识外，其他方面都更好...

@Daniel in the comments is asking the motivation for these q's. Apart from just understanding compiler internals a bit better ...

GHC将表面Haskell转换为内部表示形式:系统F _C ，该系统在每个函数应用程序中都具有明显的类型签名.(这些应用程序必须包括对类的字典进行申请.)我试图了解类和实例decl的所有与类型相关的组件在字典中的位置.找出F _C 中的术语如何与原始Haskell等效.然后，我不理解[没有方法的类型类]如何适合.因为这些类不能直接作为表面Haskell中的术语出现，而只能作为约束出现.然后，对于这样一个在术语级别代表该类的类，它必须是字典.

GHC translates surface Haskell into an Internal Representation: System F_C, which has aot explicit type signatures at every function application. (Those applications must include applying to the dictionaries for a class.) I'm trying to understand where all the type-related components of class and instance decls go inside the dictionaries; to figure out how a term in F_C gets to an equivalent representation to the original Haskell. Then I don't understand how [typeclasses without methods] fit in. Because those classes cannot appear directly as terms in surface Haskell, but only as constraints. Then it must be dictionar(ies) for such a class that represent it at term level.

如果您想问这是怎么回事:F _C 中似乎存在一个局限性，即它不能表示功能依赖项.与无法生成类型级别的证据有关.然后，我想了解这种限制是如何产生的/关于FunDeps不能(或目前没有)代表什么?

If you want to ask where this is going: there seems to be a limitation in F_C that it can't represent Functional Dependencies. Something to do with being unable to generate type-level evidence. Then I want to understand how that limitation arises/what about FunDeps can't be (or currently isn't) represented?

推荐答案

有没有[没有方法的类型类]的字典吗?它包含什么?

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

是的，有一本没有字段的字典.

Yes, there is a dictionary with no fields.

比较:

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

如果将 M 导入到其他模块(具有 C 实例)中，如何对 f 的字典查找进行编码?

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

类型推断用于确定调用 f 时需要什么实例；然后GHC在其已知实例(=已知词典)的集合中查找该类型.

Type inference is used to determine what instance is needed when f is called; then GHC looks up that type in its collection of known instances (=known dictionaries).

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

One possible outcome of this process is that the instance we determine would be needed is polymorphic, and there is no fully polymorphic instance. Then the appropriate constraint (such as C a or C m or whatever) is attached to the inferred type of whatever term is calling f -- which is then compiled to a function which accepts a dictionary on f's behalf and passes it on.

对于具有超类约束的无方法类型类:约束在字典中的位置在哪里?

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

某处.您无法从表面语言中进行观察来区分不同的地方.例如，考虑:

Somewhere. There's no observation you can make from the surface language to distinguish between different places. For example, consider:

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

这是将超类字典放在何处的仅有的两种选择.但是它可能会产生什么变化?

These are sort of the only two choices one could make for where to put the superclass' dictionary. But what difference could it possibly make?

好的，但是您询问了无方法类型类.但是答案是一样的.您无法说出超类词典的存储顺序.

Okay, but you asked about no-method typeclasses. But the answer is the same. You can't tell the order that superclass dictionaries are stored in.

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

您可能会做什么来区分两者之间的区别?没事.

What could you possibly do to tell the difference between these? Nothing.

对于具有约束的无方法类型类实例:约束再次在字典中的什么位置?

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

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

Nowhere. They become arguments that the caller must supply to receive a dictionary. Particular fields of the supplied dictionary may be closed over by the new dictionary, of course. Example:

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'

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

Okay, but you asked about no-method typeclasses. But the answer is not significantly different. The instance's constraint dictionaries are not stored anywhere, just like before; the only difference is that now we can also be sure that even the fields of the supplied dictionaries are not closed over.

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

以下评论答复了该问题的旧版本.

此模块中没有用于 C 的实例，因此编译器无法释放 f 的约束.

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

不需要. f 被编译为一个函数，该函数以字典为参数.无需创建字典即可编译 f ，而仅用于编译其调用方.

It doesn't need to. f is compiled to a function which takes a dictionary as an argument; there's no need to create a dictionary to compile f, only to compile its callers.

编译器无法释放由 y 的等式引起的 C Char 约束.它是做什么的?

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

它报告无法释放 C Char 约束，并且退出失败.(这甚至不算是一个问题-只需尝试一下，然后自己看看即可！)

It reports that it can't discharge the C Char constraint and exits unsuccessfully. (This hardly even qualifies as a question -- just try it and see for yourself!)

这篇关于没有方法的类型类，用作约束:它们是否获得字典?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！