Может ли какая-либо алгоритмическая головоломка быть реализована чисто функциональным способом?

Question

Я размышлял над проектами языков программирования и из определения Декларативного программирования в Википедии :

Это в отличие от императивного программирования, которое требует подробного описания алгоритма для запуска.

и далее вниз:

... Любой стиль программирования, который не является обязательным. ...

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

Однако это заставляет меня задуматься: способны ли чисто функциональные языки программирования решать какие-либо алгоритмические задачи или ограничения основаны на том, какие функции доступны в этом языке?

Меня больше всего интересуют общие мысли по этому вопросу, хотя, если конкретные примеры могут проиллюстрировать это, я, безусловно, приветствую их.

Answer 1

Согласно тезису Церковного Тьюринга ,

три вычислительных процесса (рекурсия, λ-исчисление и машина Тьюринга) были показаны эквивалентными "

где машина Тьюринга может читаться как «процедурная», а лямбда-исчисление - как «функциональная».

Answer 2

Да, Haskell, Erlang и т. Д. Являются полными языками Тьюринга. В принципе, вам не нужно изменяемое состояние для решения проблемы, поскольку вы всегда можете создать новый объект вместо того, чтобы изменить старый. Конечно, Brainfuck также завершен. Другими словами, тот факт, что алгоритм может быть выражен на функциональном языке, не означает, что он не очень неудобен.

Answer 3

ОК, поэтому церковь и Тьюринг при условии, что это возможно , но как мы на самом деле делаем что-то?

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

• Каждая изменяемая переменная становится параметром функции
• Циклы переписываются с использованием рекурсии
• Каждое goto выражается как вызов функции с аргументами

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

Answer 4

Слишком долго, чтобы публиковать комментарий @ SteveB's answer .

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

Но тезис Церковного Тьюринга как таковой не имеет значения. Он утверждает, что любое вычисление может выполняться машиной Тьюринга. Это связывает неформальную идею - вычисление - с формальной - машиной Тьюринга. Никто еще не нашел ничего такого, что мы могли бы признать вычислением, чего не может сделать машина Тьюринга. Найдет ли кто-нибудь такую ​​вещь в будущем? Кто может сказать.

Answer 5

Большая разница с функциональным стилем программирования заключается в том, что он избегает изменяемого состояния. Там, где императивное программирование обычно обновляет переменные, функциональное программирование определяет новые значения только для чтения.

Основное место, где это сказывается на производительности, - это алгоритмы, которые используют обновляемые массивы. Императивная реализация может обновить элемент массива за O (1) времени, в то время как наилучшим, которого может достичь чисто функциональный стиль реализации, является O (log N) (с использованием отсортированного дерева).

Обратите внимание, что функциональные языки обычно имеют некоторый способ использовать обновляемые массивы со временем доступа O (1) (например, Haskell обеспечивает это своей монадой преобразователя состояния). Тем не менее, это, возможно, императивный метод программирования ... в этом нет ничего плохого; в конце концов, вы хотите использовать лучшие инструменты для конкретной работы.

Однако функциональный стиль обновления инкрементного массива O (log N) не так уж и плох, поскольку алгоритмы функционального стиля, похоже, хорошо поддаются распараллеливанию.

Answer 6

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

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

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

На более субъективном замечании утверждение о том, что все полные по Тьюрингу языки эквивалентны, верно только в узком математическом смысле. Пол Грэм исследует проблему в Обгоняя средние значения в разделе «Парадокс рева».

Формальные результаты, такие как полнота по Тьюрингу, могут быть достоверно верными, но они не обязательно полезны. Задача коммивояжера может быть NP-полной, и все же коммивояжер путешествует все время. Кажется, они не чувствуют необходимости следовать «оптимальному» пути, поэтому теорема не имеет значения.

ПРИМЕЧАНИЕ. Я не пытаюсь разбить функциональное программирование, поскольку оно мне действительно нравится. Просто важно помнить, что это не панацея.

Answer 7

Хотя я полностью согласен с ответом, в котором упоминается тезис Черча-Тьюринга, на самом деле возникает интересный вопрос. Если у меня есть проблема параллельных вычислений (которая не является алгоритмической в ​​строгом математическом смысле), такая как множественная очередь производителя / потребителя или некоторый сетевой протокол между несколькими машинами, может ли это быть адекватно смоделировано машиной Тьюринга? Это можно смоделировать, но если мы смоделируем это, мы потеряем цель, почему у нас есть параллелизм в задаче (потому что тогда мы можем найти более простой алгоритм на машине Тьюринга). Так что, если бы мы не потеряли параллелизм, присущий этой проблеме (и, следовательно, причину, по которой мы в ней заинтересованы), мы не смогли бы удалить понятие состояния?

Answer 8

Используя монады состояний, вы можете программировать в Haskell в императивном стиле.

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