Почему класс Eq существует?

Question

Предположим, я хочу определить тип Mod4 целых чисел по модулю 4. В конце концов, Int is Mod2^64. Один очевидный способ, которым я мог бы это

data Mod4 = ZeroMod4 | OneMod4 | TwoMod4 | ThreeMod4 

Однако я также мог бы сделать это

data Mod4 = Mod4 Integer 

instance Eq Mod4 where 
    (Mod4 x) == (Mod4 y) = (x-y) `mod` 4 == 0 

Но тогда эта функция является проблематичным:

f :: Mod4 -> Mod4 
f (Mod4 x) = if x < 20 then Mod4 0 else Mod4 1 

f (Mod4 16) отличается от f (Mod4 20), в то время как те два Аргументы: ==. Таким образом, я получаю два вида равенства: представление в памяти ( Mod4 16 отличается от Mod4 20) и ==.

Поскольку все функции могут сопоставлять их аргументы, они всегда могут обойти любого оператора ==. Почему Хаскелл просто принял представление в памяти как определение равенства? Таким образом, все типы становятся тривиально равными.

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

Answer 1

Почему Хаскелл не принял представление в памяти как определение равенства? Таким образом, все типы становятся тривиально равными.

Nope. Вы не можете сравнивать значения типа Integer -> Bool. В общем, функции нельзя сравнивать.

Назад к доске. Как разработать равенство на типизированном языке?

Один из вариантов - дать (==) :: a -> a -> Bool и выдать исключение, если a является функцией. См. Ocaml.

Другой вариант заключается в том, чтобы типы разделов в уравновешенном/неравномерном виде. Это eqtype в SML.

Другим, но связанным, вариантом является выражение «eq-способность» как ограничение на полиморфизм. Eq в Haskell.

Теперь, Eq, возможно, было более особенным. Например. вы не можете определить свои экземпляры самостоятельно, и вы должны использовать deriving Eq, как и сейчас, как работает Typeable. Дизайнеры Haskell вместо этого позволяют пользователям определять свою собственную функцию сравнения. Пользователи могут знать некоторые «умные» способы. Например. чтобы сравнить 10-полевую запись, начните с сравнения обычно разных полей и сравните обычно-равных позже, пытаясь повысить эффективность.

Обратите внимание: если мы не экспортируем конструктор типа данных, мы можем сделать равенство эквивалентом и по-прежнему быть полезным. Например. Data.Set.Set приравнивает разные (сбалансированные) деревья, когда они представляют один и тот же набор, но экспортируемый интерфейс никогда не нарушает эквивалентность, поэтому равенство выглядит как равенство извне.

Так что не имеет смысла говорить о функции типа, который не является равнозначным.

Правда, когда «неравнодушный» интерпретируется в математическом смысле. Однако. когда он интерпретируется как «предикат равенства не является вычислимым», он имеет большой смысл. Мы можем говорить о функции, работающей над значениями, тип которых имеет неразрешимое равенство.