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

Question

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

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

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

Answer 1

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

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

Answer 2

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

Если у вас был такой алгоритм, как, скажем:

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чтобы увидеть чистые языки, которые все еще процветают на разрушении.

Answer 3

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

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

Answer 4

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