Могу ли я всегда преобразовывать изменяемые алгоритмы в одинарное присваивание и при этом оставаться эффективным?

Контекст

Контекст этого вопроса заключается в том, что я хочу поиграть с Программирование экспрессии генов (GEP), формой эволюционного алгоритма , используя Erlang . GEP использует строковый DSL, называемый « нотация Карвы ». Нотация Карва легко переводится в деревья синтаксического анализа выражений, но алгоритм перевода предполагает реализацию, имеющую изменяемые объекты: неполные подвыражения создаются на ранней стадии процесса перевода, а их собственные подвыражения заполняются позже. -on со значениями, которые не были известны на момент их создания.

Назначение нотации Карвы состоит в том, что она гарантирует создание синтаксически правильных выражений без каких-либо дорогостоящих методов кодирования или исправлений генетического кода. Проблема в том, что с языком программирования с одним назначением, таким как Erlang, я должен воссоздавать дерево выражений постоянно по мере заполнения каждого подвыражения. Для этого требуется недорогое - O (n)? - операция обновления и преобразует ее в операцию, которая завершится за экспоненциальное время (если я не ошибаюсь). Если я не могу найти эффективный функциональный алгоритм для преобразования K-выражений в деревья выражений, то одна из неотразимых функций GEP будет потеряна.

Вопрос

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

8
задан Andrew Matthews 30 July 2011 в 12:08
поделиться