Почему постоянные склеивающие деревья особенно полезны в функциональном программировании?

Question

На Раскидистые Деревья Страница в Википедии об этом говорится (в разделе "Преимущества").:

Возможность создания постоянной версии структуры данных splay trees, которая обеспечивает доступ как к предыдущей, так и к новой версиям после обновления. Это может быть полезно в функциональном программировании, и требует амортизированного O (log n) места для каждого обновления.

Почему это так?Как именно функциональное программирование использует устойчивые раскидистые деревья?

Answer 1

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

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

//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem

//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed

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

Answer 2

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

Короче говоря, вы, вероятно, можете прочитать эту фразу как «Создание постоянных деревьев Splay может быть полезным при программировании только с неизменными структурами данных», которые граничат с тавтологическим.

Answer 3

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