Какие алгоритмы трудно реализовать на функциональных языках?

Ответ 1

Прежде всего, как вы можете или не знаете, некоторые языки, в том числе Haskell, реализуют совместное использование, что облегчает некоторые проблемы, о которых вы можете подумать.

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

Простой ответ на этот вопрос: все, что связано с указателями.

Нет функционального эквивалента указателям при переходе на уровень машины, есть карта, и вы можете безопасно скомпилировать определенные структуры данных до массивов или вещей, реализованных в качестве указателей, но на высоком уровне вы можете просто " t выражать вещи, используя структуры данных на основе указателей так же легко, как вы можете в императивных языках.

Чтобы обойти это, было сделано несколько вещей:

• Так как указатели составляют основу хэш-таблицы, а так как хэш-таблицы действительно просто реализуют карту, эффективные функциональные карты изучены всесторонне. На самом деле у Криса Окасаки есть книга ( "Чисто функциональные структуры данных" ), в которой представлены многие, многие способы реализации функциональных карт, двое и т.д.
• Поскольку указатели могут использоваться для представления узлов внутри обхода некоторой более крупной структуры данных, в этой области также есть работа. Продукт представляет собой застежку-молнию, эффективную структуру, которая лаконично представляет функциональный эквивалент техники "указатель внутри более глубокой структуры".
• Так как указатели могут использоваться для реализации побочных эффектов, то монады использовались для выражения такого рода вычислений красивым способом. Поскольку отслеживание состояния трудно манипулировать, одно использование для монадов - это позволить вам замаскировать уродливый императив, ведущий часть вашей программы, и использовать систему типов, чтобы убедиться, что программа соединена правильно (через монадические привязки).

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

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

EDIT: Я считаю, что суть этого вопроса связана с тем, как выразить вычисления в функциональной манере. Однако следует отметить, что существуют способы определения функциональных расчетов с учетом состояния. Вернее, можно использовать функциональные методы для обоснования вычисления состояния. Например, проект Ynot делает это с помощью параметризованной монады, где факты о куче (в форме логики разделения) отслеживаются монадические привязки.

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

Ответ 2

Помните, что большинство функциональных языков допускают некоторое понятие о побочных эффектах; они могут быть нахмурены, ограничены местным использованием и т.д., но вы все равно можете их использовать. В OCaml, Haskell, F #, Scala или Clojure вы можете использовать изменяемые массивы, если вам нужно.

Итак, если вы найдете алгоритм, для которого у вас есть формулировка с использованием изменяемых массивов, и вам нужно воспроизвести его на одном из этих языков, просто используйте изменяемые массивы!

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

Например, Сито из Eratosthenes является тривиальным для реализации с изменяемыми массивами и значительно сложнее подражать (разумно эффективно) в чисто функциональном путь: см. Мелисса О'Нил для подробностей.

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

(Примеры использования совместного использования для оптимизации чисто функционального алгоритма см. Ричард Берд и Ральф Хинзе 2003 Функциональная жемчужина: проблема решена проблема вдвое.)

Ответ 3

Можно реализовать императивные черты с низкой асимптотической стоимостью, поэтому в абстрактном смысле нет существенной трудности при переводе императивного кода в чисто функциональную вселенную. На практике, конечно, есть.:-) Взгляните на документы Pippenger "Pure versus Impure Lisp" и которые приводят его.