Почему не всякая часть Eq в Haskell?

Ответ 1

В Python реализация равенства по умолчанию сравнивает идентификатор, а не значение. Это полезно для пользовательских классов, которые по умолчанию являются изменяемыми и не должны иметь четко определенного понятия "значение". Но даже в этой настройке более нормально использовать оператор is для прямого сравнения тождеств для изменяемых объектов.

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

Таким образом, равенство в Haskell всегда равно равенству ценностей; он говорит вам, являются ли два члена одинаковым значением (не обязательно, имеют ли они равную структуру, если вы реализуете набор с неупорядоченным списком, тогда два списка с разной структурой могут представлять один и тот же набор).

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

И, к сожалению, тот факт, что функции не могут быть членами Eq, означает, что многие другие вещи тоже не могут быть; списки целых чисел могут быть сопоставлены для равенства, но списки функций не могут, и то же самое относится ко всем другим типам conatiner-ish, когда он содержит функции. Это также касается ADT, которые вы пишете, если нет разумного понятия равенства, которое вы можете определить для этого типа, который не зависит от равенства содержащихся функций (возможно, функция является просто удобством в реализации и какая функция это не влияет на значение, которое вы представляете с помощью ADT).

Итак, существуют (1) типы, которые уже являются членами типов Eq, (2), которые не могут быть членами типов Eq, (3), которые могут быть членами Eq в очевидном (4) типы, которые могут быть членами Eq, но только неочевидным образом, и (5) типы, которые могут быть членами Eq очевидным образом, но программист предпочел бы альтернативный путь, Я думаю, что способ, которым Haskell справляется с этими случаями, на самом деле правильный путь. (1) и (2) ничего не требуют от вас, и (4) и (5) всегда будут требовать явного объявления экземпляра. Единственный случай, когда компилятор может помочь вам немного больше (3), где он потенциально может спасти вас 12 символов ввода (4, если вы уже deriving что-нибудь еще).

Я думаю, что это будет довольно небольшая победа в цене. Компилятор должен попытаться построить экземпляр всего и предположить, что все, для чего это не удается, не должно иметь экземпляр Eq. На данный момент, если вы хотите получить экземпляр Eq и случайно записать тип, для которого это не работает, компилятор сообщает вам тогда и там, что есть проблема. С предлагаемой "неявно сделать все Eq, что вы можете" стратегии, эта ошибка будет отображаться как необъяснимая ошибка "no Eq" в точке, когда вы переходите к использовать предполагаемый экземпляр, Это также означает, что если я думаю о типе как о представлении значений, для которых разумное отношение равенства не является простым структурным равенством (пример (5) выше, помните множество, представленное неупорядоченным списком?), И я забываю написать мой собственный экземпляр Eq, тогда компилятор может автоматически создать неправильный экземпляр Eq для меня. Мне бы скорее сказали: "Вы еще не написали экземпляр Eq", когда я его использую, чем компилирую программу и запускаю с ошибкой, представленной компилятором!

Ответ 2

Вы не можете представить себе несравненный тип? Ну, классический пример - это функции. Рассмотрим функции [()]->Bool. Две такие функции равны, когда они возвращают одно и то же значение для каждого возможного ввода. Но, к сожалению, таких списков бесконечно много: поскольку Haskell ленив, размер списка даже не связан памятью. Конечно, вы можете сравнить, для каждого ввода списка с длиной меньше фиксированной lMax, но где вы нарисуете линию? Невозможно никогда не быть уверенным, что функции, которые вы сравниваете, не будут, после 1000000000 равных возвратов, внезапно возвращают разные результаты для replicate 1000000001 (). Таким образом, (==) :: ([()]->Bool) -> ([()]->Bool) -> Bool никогда не может вернуть True только один False (если найден вход, для которого отличаются функции) или ⟂ (если функции фактически равны). Но вы не можете оценить ⟂.

Ответ 3

Возможно, вы не захотите получить Eq - вы можете написать свой собственный экземпляр.

Например, представьте данные в структуре данных двоичного дерева:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a

У вас могут быть те же данные в вашем Leaf s, но сбалансированы по-разному. Например:

balanced = Branch (Branch (Leaf 1) 
                          (Leaf 2)) 
                  (Branch (Leaf 3) 
                          (Leaf 4))

unbalanced = Branch (Branch (Branch (Leaf 1) 
                                    (Leaf 2)) 
                            (Leaf 3)) 
                    (Leaf 4)

shuffled = Branch (Branch (Leaf 4) 
                          (Leaf 2)) 
                  (Branch (Leaf 3) 
                          (Leaf 1))

Тот факт, что данные хранятся в дереве, может быть только для эффективности обхода, и в этом случае вы, вероятно, захотите сказать, что balanced == unbalanced. Вы даже можете сказать, что balanced == shuffled.

Ответ 4

Я не могу думать о типах, которые нельзя сравнивать.

let infiniteLoop = infiniteLoop

let iSolvedTheHaltingProblem f = f == infiniteLoop
-- Oops!

Ответ 5

Поскольку способ сравнения этих значений может быть обычным. Например, некоторые "поля" могут быть исключены из сравнения.

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

Ответ 6

Как вы сравниваете функции? Или экзистенциальные типы? Или MVars?

Существуют несравнимые типы.

Изменить: MVar находится в Eq!

instance Eq (MVar a) where
        (MVar mvar1#) == (MVar mvar2#) = sameMVar# mvar1# mvar2#

Но для этого требуется магический примочек.

Ответ 7

Рассмотрим следующий пример Python:

>>> 2 == 2
True
>> {} == {}
True
>>> set() == set()
True
>>> [1,2,3] == [1,2,3]
True
>>> (lambda x: x) == (lambda x: x)
False

False? o_O Это, конечно, имеет смысл, если вы понимаете, что Python == сравнивает значения указателя, за исключением случаев, когда это не так.

>>> f = (lambda x: x)
>>> f == f
True

Haskell рекомендует == всегда представлять структурное равенство (и всегда будет, если вы используете deriving Eq. Так как никто действительно не знает полностью здравого и приемлемого способа, чтобы объявить, независимо от того, структурны ли эти две функции, no Eq для функций. К тому же любая структура данных, в которой хранится функция, не может быть экземпляром Eq.