Классы типов без методов, используемые в качестве ограничений: получают ли они словари? - PullRequest
Новая
       12

Классы типов без методов, используемые в качестве ограничений: получают ли они словари?

4 голосов
/ 26 марта 2019

Если я использую класс типов для перегрузки методов, это реализовано в «стиле передачи словаря».То есть метод получает дополнительный аргумент (который не появляется в поверхностном Haskell);чтобы разрешить перегрузку, метод ищет словарь по типу его «правильного» аргумента (ов);и вытаскивает реализацию метода из словаря. Как описано в этом разделе, например .

Но как быть с классами типов без методов?Их можно использовать как ограничения.Есть ли словарь для них?Что он содержит?

Для конкретного примера: 

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 имеет метод (ы);к ним обращаются по RHS уравнения для f;поэтому требуемый C a кодируется как поиск по словарю для вызова метода.

Дополнительные q: (если кто-то еще слушает)

2a.Для классов типов без методов с ограничениями суперкласса: Куда идут ограничения в словаре? комментарий к заявке от SPJ , кажется, предполагает, что это аргумент для конструктора данных словаря.

2b.Для экземпляров классов типов без методов с ограничениями: Опять же, куда идут ограничения в словаре?

Мотивация

@ Даниэль в комментариях спрашивает мотивировку этих q,Помимо простого понимания внутренних особенностей компилятора ...

GHC переводит поверхностный Haskell во внутреннее представление: система F C , которая имеет явные сигнатуры типов в каждом приложении функции.(Эти приложения должны включать в себя применение к словарям для класса.) Я пытаюсь понять, где все связанные с типом компоненты класса и экземпляров decls находятся внутри словарей;чтобы выяснить, как термин в F C попадает в эквивалентное представление оригинальному Haskell.Тогда я не понимаю, как вписываются [классы типов без методов]. Потому что эти классы не могут отображаться непосредственно как термины в поверхностном Haskell, а только как ограничения.Тогда это должен быть словарь (и) для такого класса, который представляет его на уровне терминов.

Если вы хотите спросить, куда это идет: кажется, есть ограничение в F C что он не может представлять функциональные зависимости.Что-то связанное с неспособностью генерировать доказательства на уровне типа.Тогда я хочу понять, как возникает это ограничение / что насчет FunDeps не может быть (или в настоящее время не представлено)?

1 Ответ

7 голосов
/ 26 марта 2019

Есть ли словарь для [классов типов без методов]?Что он содержит?

Да, есть словарь без полей.

Сравнить: 

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?

Вывод типа используется для определения, какой экземпляр необходим при вызове f;затем GHC ищет этот тип в своей коллекции известных экземпляров (= известных словарей).

Одним из возможных результатов этого процесса является то, что экземпляр, который мы определили как необходимый, является полиморфным, и полностью полиморфного экземпляра не существует.Затем соответствующее ограничение (например, C a или C m или что-либо еще) присоединяется к предполагаемому типу любого термина, вызывающего f, который затем компилируется в функцию, которая принимает словарь для f.имени и передает его.

Для классов типов без методов с ограничениями суперкласса: Куда идут ограничения в словаре?

Где-то.Там нет никакого наблюдения вы можете сделать с поверхности языка, чтобы различать разные места.Например, рассмотрим: 

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)

Что вы могли бы сделать, чтобы определить разницу между ними?Ничего.

Для экземпляров классов типов без методов с ограничениями: Опять же, куда идут ограничения в словаре?

Нигде.Они становятся аргументами, которые вызывающая сторона должна предоставить для получения словаря.Конкретные поля поставляемого словаря могут быть закрыты новым словарем, конечно.Пример: 

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

Следующий комментарий отвечает на старую версию вопроса.

В этом модуле нет экземпляров для C, поэтому компилятор не может выполнить ограничение f s.

В этом нет необходимости.f компилируется в функцию, которая принимает словарь в качестве аргумента;нет необходимости создавать словарь для компиляции f, только для компиляции его вызывающих.

Компилятор не может выполнить ограничение C Char, возникающее из уравнения для y.Что он делает?

Он сообщает, что не может выполнить ограничение C Char и завершается неудачно.(Это вряд ли можно квалифицировать как вопрос - просто попробуйте и убедитесь сами!)

...