Почему недетерминированная функция выбора в Curry std lib определяется не просто, а с помощью вспомогательной функции с двумя аргументами?
Рассмотрим функцию choose
на языке программирования Curry со спецификацией, что "(choose xs)
недетерминированно выбирает один элемент из списка xs
".
Я реализовал бы это прямо через два альтернативных недетерминированных правила:
choose :: [a] -> a
choose x:_ = x
choose _:xs = choose xs
Но в /usr/lib/curry-0.9.11/Success.curry из Muenster Curry Compiler он определяется вспомогательной функцией:
choose (x:xs) = choosep x xs
where choosep x [] = x
choosep x (_:_) = x
choosep _ (x:xs) = choosep x xs
Каковы могут быть преимущества (если есть) определения из поставляемого компилятором модуля?
Являются ли эти 2 определения полностью эквивалентными (даже в некоторых сложных случаях с недетерминизмом и неопределенными значениями)?.. Является ли одно из них более эффективным в некоторых случаях?
ДОБАВЛЕНО: более глубокое рассмотрение
cthom06 (спасибо!) правильно указал, что мое определение будет вызывать попадание в неопределенное значение в гораздо большем числе случаев (потому что мы будем пытаться вызывать эту функцию с аргументом пустого списка один раз для каждого нашего вызова "верхнего уровня" с первоначально непустой аргумент списка). (Хм, почему я не заметил это соображение сразу?..) Это менее эффективно.
Но мне интересно: есть ли смысловые различия? Может ли разница быть важной в некоторых сложных ситуациях?
Мы видим, что разница между двумя определениями - в случае непустых списков - в основном сводится к разнице между двумя потенциальными определениями для id
:
мое определение похоже на определение id
как:
id x = x
id _ = undefined
и их определение похоже на определение id
обычным способом:
id x = x
(Итак, здесь прямолинейность обращена вспять.)
В каких контекстах это может быть важно?
Ответы
Ответ 1
Я полагаю, что нет семантических различий, но тот, который имеет вспомогательную функцию, более эффективен, особенно в общем случае (в определенных стилях программирования) списка с одним элементом. В этом случае избегается точка выбора, которую в вашей версии нужно было бы настроить для рекурсивного вызова с [], который затем обречен на неудачу.
Умный оптимизатор может сам в этом разобраться, но обработка всех подобных ситуаций может оказаться сложной задачей - компилятору нужно будет попытаться специализировать приложения для каждого из возможных конструкторов в типе данных, удалить те, где всегда происходит сбой, и удалить точки выбора, когда остается только одна возможность.