Ответ 1
Прежде всего, как вы можете или не знаете, некоторые языки, в том числе Haskell, реализуют совместное использование, что облегчает некоторые проблемы, о которых вы можете подумать.
В то время как Эндрю дает ответы на вопросы о полноте Тьюринга, на самом деле он не отвечает на вопрос о том, какие алгоритмы трудно реализовать на функциональных языках. Вместо того, чтобы спрашивать, какие алгоритмы трудно реализовать на функциональных языках, люди обычно спрашивают, какие структуры данных трудно реализовать на функциональных языках.
Простой ответ на этот вопрос: все, что связано с указателями.
Нет функционального эквивалента указателям при переходе на уровень машины, есть карта, и вы можете безопасно скомпилировать определенные структуры данных до массивов или вещей, реализованных в качестве указателей, но на высоком уровне вы можете просто " t выражать вещи, используя структуры данных на основе указателей так же легко, как вы можете в императивных языках.
Чтобы обойти это, было сделано несколько вещей:
- Так как указатели составляют основу хэш-таблицы, а так как хэш-таблицы действительно просто реализуют карту, эффективные функциональные карты изучены всесторонне. На самом деле у Криса Окасаки есть книга ( "Чисто функциональные структуры данных" ), в которой представлены многие, многие способы реализации функциональных карт, двое и т.д.
- Поскольку указатели могут использоваться для представления узлов внутри обхода некоторой более крупной структуры данных, в этой области также есть работа. Продукт представляет собой застежку-молнию, эффективную структуру, которая лаконично представляет функциональный эквивалент техники "указатель внутри более глубокой структуры".
- Так как указатели могут использоваться для реализации побочных эффектов, то монады использовались для выражения такого рода вычислений красивым способом. Поскольку отслеживание состояния трудно манипулировать, одно использование для монадов - это позволить вам замаскировать уродливый императив, ведущий часть вашей программы, и использовать систему типов, чтобы убедиться, что программа соединена правильно (через монадические привязки).
Хотя я хотел бы сказать, что любой алгоритм можно легко перевести с императивного на функциональный, это просто не так. Однако я уверен, что проблема заключается не в самих алгоритмах, а в структурах данных, которыми они управляют, основываясь на императивном понятии состояния. Вы можете найти длинный список функциональных структур данных в этом сообщении.
Откидной стороной всего этого является то, что, если вы начнете использовать более чисто функциональный стиль, большая часть сложности вашей программы снизится, и многие потребности в сильно императивных структурах данных исчезнут (например, очень частое использование указатели на императивных языках - это реализация неприятных шаблонов проектирования, которые обычно переводят на умное использование полиморфизма и typeclases на функциональном уровне).
EDIT: Я считаю, что суть этого вопроса связана с тем, как выразить вычисления в функциональной манере. Однако следует отметить, что существуют способы определения функциональных расчетов с учетом состояния. Вернее, можно использовать функциональные методы для обоснования вычисления состояния. Например, проект Ynot делает это с помощью параметризованной монады, где факты о куче (в форме логики разделения) отслеживаются монадические привязки.
Кстати, даже в ML я не понимаю, почему динамическое программирование так сложно. Похоже, что проблемы динамического программирования, которые обычно создают сборники некоторой последовательности для вычисления окончательного ответа, могут накапливать сконструированные значения через аргументы функции, возможно, требуя продолжения в некоторых обстоятельствах. Используя хвостовую рекурсию, нет причин, чтобы это было не так красиво и эффективно, как на императивных языках. Теперь, конечно, вы можете столкнуться с аргументом, что если эти значения являются списками (например), настоятельно мы можем реализовать их как массивы, но для этого см. Содержимое собственно сообщения: -)