Haskell - как указать экземпляр класса типов? - PullRequest
Новая
       19

Haskell - как указать экземпляр класса типов?

5 голосов
/ 01 июня 2011

У меня есть (довольно) законный случай, когда есть две реализации экземпляра типа, и я хочу указать стандартную. Отметив, что выполнение модульной арифметики с типами Int привело к множеству коллизий хешей, я хочу попробовать Int64 GHC. У меня есть следующий код: 

class Hashable64 a where
    hash64 :: a -> Int64

instance Hashable64 a => Hashable a where
    hash = fromInteger . toInteger . hash64

instance Hashable64 a => Hashable64 [a] where
    hash64 = foldl1 (\x y -> x + 22636946317 * y) . map hash64

и экземпляр Hashable64 Char, что приводит к двум реализациям для Hashable String, а именно:

  • Тот, который определен в Data.Hashable.
  • Отметив, что это экземпляр Hashable64, затем преобразуется в обычный Int для экземпляра Data.Hashable.

Второй путь кода может быть лучше, потому что он выполняет хеширование с Int64 s. Могу ли я указать использование этого производного экземпляра строки Hashable ?

Редактировать 1

Извините, я забыл добавить, что уже пробовал перекрывающиеся экземпляры; возможно я просто не правильно это реализую? Документация для перекрывающихся экземпляров говорит, что это работает, когда один экземпляр более конкретен. Но когда я пытаюсь добавить конкретный экземпляр для Hashable String, ситуация не улучшается. Полный код в [http://pastebin.com/9fP6LUX2] (извините за лишний заголовок по умолчанию). 

instance Hashable String where
    hash x = hash (hash64 x)

Я получаю 

Matching instances:
  instance (Hashable a) => Hashable [a] -- Defined in Data.Hashable
  instance [overlap ok] Hashable String
    -- Defined at Hashable64.hs:70:9-23

Редактировать 2

Любые другие решения этой конкретной проблемы приветствуются. Хорошее решение может дать представление об этой проблеме перекрывающихся экземпляров.

1 Ответ

6 голосов
/ 01 июня 2011

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

Такая ситуация, когда у вас есть один или несколько специализированных экземпляров и один универсальный instance Foo a в качестве «по умолчанию», обычно работает довольно хорошо.

Основные камни преткновения, о которых следует помнить с перекрывающимися экземплярами:

  • Если что-то вынуждает GHC выбрать экземпляр для полиморфного типа, который неоднозначен, он откажется с потенциально загадочными ошибками компилятора

  • Контекст экземпляра игнорируется до тех пор, пока после не будет выбран, поэтому не пытайтесь различать экземпляры таким образом; Есть обходные пути, но они раздражают.

Последний пункт уместен здесь, если, например, у вас есть список какого-то типа, который не является экземпляром Hashable64; GHC выберет более конкретный второй экземпляр, а затем потерпит неудачу из-за контекста, даже если полный тип (список, а не тип элемента) является экземпляром Hashable64 и, следовательно, будет работать с первым , универсальный экземпляр.

Редактировать : О, я вижу, я немного неверно истолковал ситуацию относительно того, откуда поступают экземпляры. Quoth Руководство пользователя GHC:

Готовность к наложению или непоследовательности является свойством объявления экземпляра (*). Ни один флаг не требуется в модуле, который импортирует и использует объявление экземпляра.

(...)

Эти правила позволяют автору библиотеки проектировать библиотеку, которая опирается на перекрывающиеся экземпляры, без необходимости знать клиент библиотеки.

Если объявление экземпляра скомпилировано без -XOverlappingInstances, то этот экземпляр никогда не может перекрываться. Это может быть неудобно. (...) Нам интересно получать отзывы по этим пунктам.

... другими словами, перекрытие допустимо только в том случае, если конкретный экземпляр less был создан с включенным OverlappingInstances, а экземпляр для Hashable [a] - нет. Таким образом, ваш экземпляр для Hashable a разрешен, но один для Hashable [Char] терпит неудачу, как было отмечено.

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

Вернувшись здесь и сейчас, у вас есть несколько вариантов, которые немного менее удобны, чем вы ожидали. С макушки головы:

  • Альтернативный класс : определите свой эквивалент класса Hashable, напишите нужные вам перекрытые экземпляры и используйте общие контексты с Hashable в контексте, чтобы вернуться к оригиналу как необходимо. Это проблематично, если вы используете другую библиотеку, которая ожидает Hashable экземпляров, а не предварительно хешированные значения или явную хеш-функцию.

  • Тип wrapper : newtype wrappers - это что-то вроде «стандартного» способа устранения неоднозначности экземпляров (см. Monoid). Используя такую ​​оболочку для ваших значений, вы сможете писать любые экземпляры, какие пожелаете, потому что ни один из предварительно определенных экземпляров не будет совпадать. Это становится проблематичным, если у вас есть много функций, которые должны были бы обернуть / развернуть новый тип, хотя имейте в виду, что вы можете легко определить другие экземпляры (например, Num, Show и т. Д.) Для оболочки, и есть нет накладных расходов во время выполнения.

Существуют и другие, более загадочные, обходные пути, но я не могу предложить слишком подробных указаний, потому что это наименее неудобно, как правило, очень зависит от ситуации.

Стоит отметить, что вы определенно выдвигаете границы того, что может быть разумно выражено с помощью классов типов, так что неудивительно, что все не так просто.Это не очень удовлетворительная ситуация, но вы мало что можете сделать, если будете вынуждены добавлять экземпляры для класса, определенного в другом месте.

...