Является ли (чистое) функциональное программирование антагонистическим с "классикой алгоритмов"?

Классические книги алгоритмов (TAOCP, CLR) (и не такие классические, как fxtbook) полны императивных алгоритмов. Это наиболее очевидно с алгоритмами, реализация которых в значительной степени основана на массивах, таких как комбинаторная генерация (где в алгоритме используются как индекс массива, так и значение массива) или алгоритм объединения.

Анализ худшего случая этих алгоритмов зависит от доступа к массиву O (1). Если вы заменяете массивы массивными структурами, такими как Clojure, то обращения к массиву больше не являются O (1), а анализ сложности этих алгоритмов более недействителен.

Это подводит меня к следующим вопросам: чистое функциональное программирование, несовместимое с литературой классических алгоритмов?

Ответ 1

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

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

Ответ 2

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

Если у вас есть алгоритм, например:

function zero(array):
    ix <- 0
    while(ix < length(array)):
       array[ix] <- 0
       ix <- ix+1
    return array

Предполагая, что наш псевдокод выше лексически ограничен, если параметр массива сначала скопирован, а возвращаемый массив является совершенно новой вещью, этот алгоритм представляет собой чистую функцию (в этом случае функция Haskell fmap (const 0), вероятно, Работа). Большинство "императивных" алгоритмов, показанных в книгах, действительно являются чистыми функциями, и совершенно нормально писать их таким образом в чисто функциональной настройке, используя что-то вроде ST.

Я бы рекомендовал посмотреть на Mercury или Disciplined Compiler, чтобы увидеть чистые языки, которые все еще процветают при уничтожении.

Ответ 3

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

Если вы заинтересованы в продолжении этой ветки основных алгоритмов, его книга станет отличной отправной точкой.

Ответ 4

Это не так. Но это правда, что во многих книжных алгоритмах можно видеть, что они используются только на императивных языках. Основная причина заключается в том, что чисто функциональное программирование долгое время было ограничено академическим использованием. Затем авторы этих алгоритмов сильно полагались на императивные функции, которые должны быть в основном. Теперь рассмотрим два широко распространенных алгоритма: быстрая сортировка и сортировка слияния. Быстрая сортировка более "обязательна", чем сортировка слияния; одно из его преимуществ заключается в том, чтобы быть на месте. Сортировка Merge более "чистая", чем быстрая сортировка (в некотором роде), поскольку она должна копировать и сохранять свои данные постоянными. На самом деле многие алгоритмы могут быть реализованы в чисто функциональном программировании, не теряя при этом слишком высокой эффективности. Это справедливо для многих алгоритмов в знаменитой книге Дракона.