Несовместимые результаты для Data.Set и пользовательского экземпляра Ord - PullRequest
Новая
       49

Несовместимые результаты для Data.Set и пользовательского экземпляра Ord

0 голосов
/ 31 декабря 2018

Вот моя структура данных 

data Ex =
  P String
  | (:←) Ex

Она имеет свойство p == ←←p.Мои пользовательские экземпляры Eq и Ord пытаются определить то же самое.Тем не менее, я вижу противоречивые результаты для test3 (набор создан из [p, ← p, ← p]) и test4 (набор создан из [p, ← p, ← указанного p]).Результаты, как показано ниже: 

*Test> test3
fromList [←q,←←q]
*Test> test4
fromList [q,←q,←←q]

Обратите внимание, что test3 и test4 отличаются только в порядке элементов, из которых создается набор.Тем не менее, результаты отличаются.

Я думаю, что порядок создания набора с использованием Data.Set.fromList не должен иметь большого значения.Может ли кто-нибудь помочь мне найти ошибку с моим экземпляром Eq или Ord?Полный код ниже, скомпилированный с GHC 8.4.3. 

module Test where    
import Data.Set as S


data Ex =
  P String
  | (:←) Ex

instance Show Ex where
  show (P s) = s
  show ((:←) e) = "←" ++ (show e)

instance Eq Ex where
  (P s1) == (P s2) = s1 == s2
  (:←) e1 == (:←) e2
    | e1 == e2 = True
    | otherwise = False
  e1 == (:←) e2
    | e1 == e2 = False
    | (:←) e1 == e2 = True
    | otherwise = False
  (:←) e1 == e2
    | e1 == e2 = False
    | e1 == (:←) e2 = True
    | otherwise = False

elength :: Ex   -> Int
elength (P s) = length s
elength ((:←) e) = elength e + 1

instance Ord Ex where
  compare e1 e2
    | e1 == e2 = EQ
    | otherwise = if (elength e1) <= (elength e2) then LT
      else GT

-- Check that ←q == ←←q                                                                                               
test2 = S.fromList [(:←) ((:←) (P "q")), P "q"]
-- output should be : {←←q, ←q}                                                                                       
test3 = S.fromList [P "q",  (:←) ((:←) (P "q")), (:←) (P "q")]  
-- output should be same as that of test3 : {←←q, ←q}                                                                 
test4 = S.fromList [P "q", (:←) (P "q"), (:←) ((:←) (P "q"))]

РЕДАКТИРОВАТЬ:

  1. Обратите внимание, что если я изменю определение elength для обработки случая,несоответствие исчезло.

    elength ((:←) ((:←) e)) = elength e

  2. Возможно, мои elength метрические и == определения имеют разногласия в случае q и ←←q,Я все еще хотел бы знать, где именно они идут не так

1 Ответ

0 голосов
/ 31 декабря 2018

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

instance Eq Ex where
  (P s1) == (P s2)     = s1 == s2
  ((:←) e1) == (:←) e2 = e1 == e2
  e1 == (:←) ((:←) e2) = e1 == e2
  (:←) ((:←) e1) == e2 = e1 == e2
  _ == _ = False

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

Ваш экземпляр Ord также является проблемой, потому что вы не определяете согласованное упорядочение.Для любого набора элементов x y z, где x < y && y < z, должно быть, что x < z.Тем не менее, существуют простые контрпримеры по вашим правилам: 

x = P "a"
y = (P "b" :←)
z = ((P "a" :←) :←)

Здесь x == z несмотря на то, что между ними находится y.

Один из способов решения обеих проблем - написать simplify функция, которая удаляет все пары конструкторов отмены и использует ее как в экземплярах Eq, так и Ord.Упростите каждый аргумент, чтобы вы знали, что каждый из них имеет либо 0, либо 1 уровень отрицания.Оттуда Eq легко, и все, что вам нужно сделать, прежде чем вы сможете определить Ord, это решить, должно ли отрицательное значение быть меньше или больше, чем неотрицательное значение.Вы не можете выбрать, чтобы они были равны, потому что это снова нарушает транзитивность.

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

...