Чистый функциональный восходящий древовидный алгоритм
Пошел на этот вопрос во время лекции по Лямбдасу, которая использовала Фибоначчи в качестве возможного варианта использования.
Вы можете сделать рекурсивную лямбду следующим образом:
import java.util.function.Function;
public class Fib {
static Function<Integer, Integer> fib;
public static void main(String[] args) {
fib = (n) -> { return n > 1 ? fib.apply(n-1) + fib.apply(n-2) : n; };
for(int i = 0; i < 10; i++){
System.out.println("fib(" + i + ") = " + fib.apply(i));
}
}
}
Что вы нужно иметь в виду?
- Lambdas оцениваются при выполнении -> они могут быть рекурсивными
- Использование лямбда-переменной внутри другой лямбды требует инициализации переменной - > перед определением рекурсивной лямбда вы должны определить ее с помощью foo-value
- , используя локальную лямбда-переменную внутри lambda, чтобы переменная была окончательной, поэтому ее нельзя переопределить -> использовать класс / объект переменная для лямбда, поскольку она инициализируется значением по умолчанию
4 ответа
Самым многообещающим, что я видел до сих пор (который, по общему признанию, не очень длинный ...), является структура данных Zipper : в основном она имеет отдельную структуру, обратную путь от узла к корню и вносит локальные изменения в эту отдельную структуру.
Он может выполнять несколько локальных изменений, большинство из которых является постоянным по времени, и записывать их обратно в дерево (восстанавливая путь к корню, которые являются единственными узлами, которые необходимо изменить) за один раз.
Zipper - это стандартная библиотека в Clojure (см. Заголовок Zippers - Functional Tree Editing ).
И есть оригинальная статья Хуэта с реализацией в OCaml.
Отказ от ответственности: я занимаюсь программированием в течение долгого времени, но начал функциональное программирование только пару недель назад и никогда даже не слышал о проблеме функционального редактирования деревьев до прошлой недели, так что вполне могут быть другие решения Я не в курсе.
Тем не менее, похоже, что застежка-молния делает большую часть того, чего можно было бы пожелать. Если есть другие альтернативы в O (log n) или ниже, я бы хотел их услышать.
Я недавно записал алгоритм, который делает точно, что Вы описали - https://medium.com/hibob-engineering/from-list-to-immutable-hierarchy-tree-with-scala-c9e16a63cb89
, Он работает в 2 фазах:
- Сортируют список узлов их глубиной в иерархии
- конструкции дерево от восходящего
Некоторые протесты:
-
Никакая мутация Узла, результатом является Неизменное дерево
-
, сложность является O (n)
-
, Игнорирует циклическую ссылку во входящем списке
Вам понравится читать
http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry
Это зависит от вашего функционального языка программирования. Например, в Haskell, который является Lazy функциональным языком программирования, результаты вычисляются в последний момент; когда они действительно необходимы.
В вашем примере предполагается, что, поскольку ваша функция создает новое дерево, все дерево должно быть обработано, тогда как на самом деле функция просто передается следующей функции и выполняется только при необходимости.
Хорошим примером ленивого вычисления является сито эрастотенов в Haskell, которое создает простые числа, удаляя кратные текущего числа в списке чисел. Обратите внимание, что список чисел бесконечен. Взято из здесь
primes :: [Integer]
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]