Чисто функциональный алгоритм восходящего дерева

Question

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

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

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

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

Answer 1

Вы можете наслаждаться чтением

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry

Answer 2

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

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

Zipper - это стандартная библиотека в Clojure (см. Заголовок Zippers - Функциональное редактирование дерева ).

И есть оригинальная статья Huet с реализацией в OCaml.

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

Тем не менее, похоже, что Молния делает большую часть того, что можно пожелать. Если есть другие варианты в O (log n) или ниже, я бы хотел их услышать.

Answer 3

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

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

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

primes :: [Integer]
primes = sieve [2..]
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]