Подтвердить что ты не робот

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

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

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

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

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

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

4b9b3361

Ответ 1

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

data Changed a = Changed a | Unchanged a

или

data Changed a = Changed a | Unchanged

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

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

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

Ответ 2

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

Ответ 3

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

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

Вы можете посмотреть определение оператора равенства в стандартной прелюдии.

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

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