Эффективность равенства в Haskell

Question

У меня есть функция, которая берет данные и возвращает те же данные или слегка измененную версию.

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

Раньше я возвращал пару (Bool,Object) и использовал fst, чтобы проверить, не изменилось ли оно. В последнее время мне пришло в голову, что я могу упростить код, просто вернув объект и проверив равенство, используя ==.

Но потом я понял, что Хаскелл не проводит различия между проверкой глубокого равенства и «идентичностью объекта» (т. Е. Равенством указателя). Итак, как я могу узнать, будет ли использование == эффективным или нет? Должен ли я избегать этого по соображениям эффективности, или есть случаи, когда я могу зависеть от компилятора, выясняя, что ему не нужно делать глубокую проверку равенства?

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

Answer 1

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

data Changed a = Changed a | Unchanged a 

или

data Changed a = Changed a | Unchanged 

На самом деле мы используем подобный тип внутри Glasgow Haskell Compiler так что мы можем продолжать работать оптимизатор, пока код не перестанет изменяться. Мы также запускаем итеративный анализ потока данных, пока результаты не перестанут меняться.

Мы считаем полезным сделать этот тип монадой, чтобы мы могли написать некоторые простые функции более высокого порядка, используя do нотацию, но не обязательно — просто удобство.

Резюме: Если вы хотите проверки постоянная времени, кода он сам — не полагаться на возможности оптимизации компилятора, который не может быть там — или которые могут измениться в следующем выпуске.

Answer 2

Я все еще родственник haskell noob, так что возьмите мой ответ с солью и, пожалуйста, простите меня, если мой ответ не так прямо, как должен!

В Haskell операторы не являются особыми - это просто функции инфикса.

Вы можете посмотреть на definition of the equality operator самостоятельно в стандартной прелюдии.

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

Возможно, вам будет полезно узнать, что вы можете использовать Hoogle, чтобы найти нужное определение функции. Вот как я нашел определение оператора равенства.

Answer 3

Вывод (==) всегда является глубоким сравнением. Ваш вопрос был discussed на haskell-кафе.