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

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

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

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

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

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

18
задан Don Stewart 18 April 2011 в 18:38
поделиться

3 ответа

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

data Changed a = Changed a | Unchanged a

так и

data Changed a = Changed a | Unchanged

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

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

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

.
34
ответ дан 30 November 2019 в 07:12
поделиться

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

.
4
ответ дан 30 November 2019 в 07:12
поделиться

Я все еще относительный хаскелл-ноб, так что возьмите мой ответ с бабушкой соли, и, пожалуйста, простите меня, если мой ответ не так прямо, как должно быть!

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

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

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

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

1
ответ дан 30 November 2019 в 07:12
поделиться
Другие вопросы по тегам:

Похожие вопросы: