Как ограничения в контексте изменяют разрешение экземпляра в Haskell - PullRequest
Новая
       28

Как ограничения в контексте изменяют разрешение экземпляра в Haskell

0 голосов
/ 27 февраля 2019

Я пытаюсь понять, как добавление ограничения к контексту экземпляра меняет разрешение экземпляра в Haskell.В этом примере: 

class C a where
  f :: a -> [Char]

instance {-# OVERLAPPABLE #-} C a where
  f = const "thing"

instance C Int where
  f = const "int"

instance {-# OVERLAPPING #-} C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

main = do
  putStrLn $ f (1 :: Int)
  putStrLn $ f [(True :: Bool)]
  putStrLn $ f [(1 :: Int)]
  putStrLn $ f [[(1 :: Int)]]

Вывод: 

int
list of thing
list of thing
list of thing

Последние две строки не то, что я хочу.В третьей строке кажется, что компилятор (или среда выполнения?) При запуске f для экземпляра списка не знает, что a равно Int, а просто использует экземпляр C a по умолчанию.Аналогично для последней строки, он не может понять, что a - это другой список.Однако, если я добавлю контекст к экземпляру списка: 

instance {-# OVERLAPPING #-} (C a) => C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

Вывод будет: 

int
list of thing
list of int
list of list of int

... что я и хочу.Может кто-нибудь помочь объяснить, как это ограничение меняет разрешение экземпляра в этом примере?Есть ли общие правила, на которые я могу обратить внимание?

1 Ответ

0 голосов
/ 27 февраля 2019

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

Итак, что происходит в ваших экземплярах?Рассмотрим первый случай: 

instance {-# OVERLAPPING #-} C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

Предположим, что f передан список типа [a0] (давайте для ясности воспользуемся новым именем переменной).Затем нам нужно набрать check f x в последней строке.Переменная x выше имеет тип a0, поэтому GHC необходимо решить C a0.Для этого GHC должен выбрать какой-то экземпляр.Обычно он отказывается выбирать instance C a, поскольку instance C Int также существует, и GHC не знает, является ли a0 = Int, поэтому ни один экземпляр не может быть выбран в качестве "окончательного", имеющего только имеющуюся информацию.

Тем не менее, «перекрывающаяся» прагма предписывает GHC выбрать единственный лучший экземпляр среди тех, которые являются достаточно общими для устранения ограничения.Действительно, это лучшее, что мы можем сделать с имеющейся информацией: единственный разумный вариант - выдать ошибку.

В этом случае, чтобы решить C a0, нам нужно выбрать один из трех экземпляров,и только instance C a обычно соответствует C a0 (в конце концов, a0 может быть не Int, не списочным типом).Таким образом, мы выбираем это.

Вместо этого использование 

instance {-# OVERLAPPING #-} (C a) => C [a] where
  f [] = "empty list"
  f (x : xs) = "list of " ++ f x

открывает четвертый вариант решения C a0, а именно использование контекста C a0, который доступен.Когда вызывается f, ему передается неявный аргумент, содержащий словарь для C a0 (т. Е. f для типа a0).

Итак, теперь GHC имеет две жизнеспособные опции:решение C a0 с использованием контекста C a0 (т.е. с использованием неявного аргумента) или обращение к глобальному instance C a.Первый является более конкретным, поскольку он применяется только к a0, а не к любому типу a, поэтому он считается «лучшим» и выбранным.

...