Есть ли обходной путь для отсутствия возврата к типу класса?

В этот разговор вокруг отметки 1:20, Эдвард Кемт упоминает о недостатке "backtracking" типа класса в Haskell. Рассмотрим проблему "установить равенство" (где порядок и кратность не учитываются) реализованы в списках:

equals :: [a] -> [a] -> Bool

По характеру классов типов я не могу обеспечить неэффективное сравнение O (n²), если все, что у нас есть, Eq a, но эффективно сравнить списки в O (n log n), если мы имеем Ord a.

Я понял, почему такой объект будет проблематичным. В то же время Эдвард говорит, что есть "трюки, которые вы могли бы сыграть", например, например, типы семейств.

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

  • предоставляется (неэффективная) реализация по умолчанию
  • Если пользователь может предоставить дополнительную информацию о типе, мы "разблокируем" более эффективную реализацию.

Это обходное решение не обязательно должно использовать классы типов.

Изменить. Некоторые люди предложили просто предоставить equals и efficientEquals как два разных метода. В общем, я согласен, что это тем более хаскел-идиоматический подход. Однако я не уверен, что это всегда возможно. Например, что, если приведенный выше метод equals является частью класса типа:

class SetLike s where
    equals :: Eq a => s a -> s a -> Bool

Предположим, что этот класс был предоставлен кем-то другим, поэтому я не могу просто добавить новую функцию в класс классов. Теперь я хочу определить экземпляр для []. Я знаю, что [] всегда может обеспечить реализацию equals независимо от того, какие ограничения существуют в a, но я не могу сказать, что мой экземпляр использует более эффективную версию, если доступна более подробная информация о a.

Возможно, я мог бы обернуть список в newtype и пометить его дополнительной информацией о типе?

Ответы

Ответ 1

В сценарии из вашего редактирования вы можете использовать GADT как доказательство вашего ограничения Ord:

{-# LANGUAGE GADTs #-}

import Data.List

class SetLike s where
    equals :: Eq a => s a -> s a -> Bool

data OrdList a where
    OrdList :: Ord a=> [a] -> OrdList a

instance SetLike OrdList where
    equals (OrdList a) (OrdList b) = sort a == sort b

И для развлечения здесь используется то, что использует трюк OverlappingInstances, о котором я упоминаю в своем комментарии. Есть много способов сделать такие вещи:

{-# LANGUAGE DefaultSignatures, OverlappingInstances, UndecidableInstances, MultiParamTypeClasses, FlexibleInstances #-}

import Data.List

class Equals a where
    equals :: [a] -> [a] -> Bool

    default equals :: Ord a=> [a] -> [a] -> Bool
    equals as bs = sort as == sort bs

instance Equals Int
instance Equals Integer
instance Equals Char
-- etc.

instance (Eq a)=> Equals a where
    equals = error "slow version"