Является ли автоматически производный экземпляр `Eq` GHC * O (N) *? - PullRequest
Новая
       5

Является ли автоматически производный экземпляр `Eq` GHC * O (N) *?

12 голосов
/ 02 июня 2011

Я только что заметил, пытаясь научиться читать GHC Core, что автоматически получаемый экземпляр Eq для типов данных в стиле enum, таких как 

data EType = ETypeA | ETypeB | ETypeC | ETypeD
           | ETypeE | ETypeF | ETypeG | ETypeH
           deriving (Eq)

кажется преобразованным в O (N) -подобный поиск при просмотре основного представления GHC: 

$fEqEType_$c== =
  \ (a_ahZ :: EType) (b_ai0 :: EType) ->
    case a_ahZ of _ {
      ETypeA ->
        case b_ai0 of _ {
          ETypeA -> True;
          ETypeB -> False;
          ETypeC -> False;
          ETypeD -> False;
          ETypeE -> False;
          ETypeF -> False;
          ETypeG -> False;
          ETypeH -> False
        };
      ETypeB -> case b_ai0 of _ {__DEFAULT -> False; ETypeB -> True};
      ETypeC -> case b_ai0 of _ {__DEFAULT -> False; ETypeC -> True};
      ETypeD -> case b_ai0 of _ {__DEFAULT -> False; ETypeD -> True};
      ETypeE -> case b_ai0 of _ {__DEFAULT -> False; ETypeE -> True};
      ETypeF -> case b_ai0 of _ {__DEFAULT -> False; ETypeF -> True};
      ETypeG -> case b_ai0 of _ {__DEFAULT -> False; ETypeG -> True};
      ETypeH -> case b_ai0 of _ {__DEFAULT -> False; ETypeH -> True}
    }

Я неправильно истолковал вывод ядра GHC? Разве алгебраические типы данных не должны предоставлять целочисленный идентификатор для каждого конструктора, который затем можно сравнивать непосредственно в O (1) ? Кроме того, почему первое предложение case для ETypeA не использует __DEFAULT, как другие предложения?

Обновление:

По предложению Саймона Марлоу я добавляю 9-й конструктор ETypeI, а затем GHC переключается на использование dataToOtag#: 

$fEqEType_$c/= =
  \ (a_ahS :: EType) (b_ahT :: EType) ->
    case dataToTag# @ EType a_ahS of a#_ahQ {
      __DEFAULT ->
        case dataToTag# @ EType b_ahT of b#_ahR {
          __DEFAULT ->
            case ==# a#_ahQ b#_ahR of _ {
              False -> True; True -> False
            }
        }
    }

Для меня это добавляет вопрос о том, каковы компромиссы между ядром GHC case и использованием dataToTag#, и почему это конкретное ограничение 9 конструкторов для использования dataToTag# реализовано в GHC .

1 Ответ

13 голосов
/ 02 июня 2011

Сравнение равенства EType - это O (1), потому что конструкция case - это O (1).

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

Понятия не имею, почему ETypeA получает другое лечение. Похоже, ошибка.

...