Является ли (чисто) функциональное программирование антагонистическим с "классикой алгоритмов"?
Книги классических алгоритмов (TAOCP, CLR) (и не такие классические, как fxtbook) полны императивных алгоритмов. Это наиболее очевидно с алгоритмами, реализация которых в значительной степени основана на массивах, таких как комбинаторная генерация (где в алгоритме используются как индекс массива, так и значение массива) или алгоритм поиска объединения.
Анализ сложности наихудшего случая этих алгоритмов зависит от доступа к массиву, который равен O(1). Если вы заменяете массивы постоянными структурами массива, как это делает Clojure, доступ к массиву больше не является O(1), и анализ сложности этих алгоритмов становится недействительным.
Что приводит меня к следующим вопросам: действительно ли чисто функциональное программирование несовместимо с литературой по классическим алгоритмам?
4 ответа
Вы можете быть заинтересованы в этом связанном вопросе: Эффективность чисто функционального программирования.
Есть ли проблема, для которой самый известный неразрушающий алгоритм асимптотически хуже, чем самый известный разрушающий алгоритм, и если да, то насколько?
Что касается структур данных, то Крис Окасаки провел серьезное исследование по внедрению классических структур данных в чисто функциональную среду, так как многие стандартные структуры данных больше не работают при использовании деструктивных обновлений. Его книга "Чисто функциональные структуры данных" показывает, как некоторые структуры, такие как биномиальные кучи и красные / черные деревья, могут быть достаточно хорошо реализованы в функциональном окружении, в то время как другие базовые структуры, такие как массивы и очереди, должны быть реализованы с использованием более сложных концепций.
Если вы заинтересованы в реализации этой ветви основных алгоритмов, его книга станет отличной отправной точкой.
Короткий ответ таков: если алгоритм не имеет эффектов, которые можно наблюдать после его завершения (кроме того, что он возвращает), он является чистым. Это верно даже тогда, когда вы делаете такие вещи, как деструктивное обновление массива или мутация.
Если у вас был такой алгоритм, как сказать:
function zero(array):
ix <- 0
while(ix < length(array)):
array[ix] <- 0
ix <- ix+1
return array
Предполагая, что наш псевдокод выше имеет лексическую область видимости, пока параметр массива сначала копируется, а возвращаемый массив - совершенно новая вещь, этот алгоритм представляет собой чистую функцию (в данном случае, функцию Haskell fmap (const 0) вероятно, будет работать). Большинство "императивных" алгоритмов, показанных в книгах, являются действительно чистыми функциями, и совершенно нормально написать их таким образом в чисто функциональной обстановке, используя что-то вроде ST.
Я бы порекомендовал взглянуть на Mercury или Disciple Disciplined Compiler, чтобы увидеть чистые языки, которые все еще процветают при разрушении.
Это не. Но это правда, что во многих книгах можно увидеть алгоритмы, которые выглядят так, что их можно использовать только в императивных языках. Основная причина в том, что чисто функциональное программирование долгое время было ограничено академическим использованием. Затем авторы этих алгоритмов настоятельно полагались на императивные особенности, чтобы быть в мейнстриме. Теперь рассмотрим два распространенных алгоритма: быстрая сортировка и сортировка слиянием. Быстрая сортировка является более "обязательной", чем сортировка слиянием; одно из его преимуществ - быть на месте. Сортировка слиянием является более "чистой", чем быстрая сортировка (в некотором роде), поскольку ей необходимо копировать и сохранять свои данные постоянными. На самом деле многие алгоритмы могут быть реализованы в чисто функциональном программировании без потери слишком высокой эффективности. Это верно для многих алгоритмов в знаменитой Книге Дракона, например.