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

Question

На Деревьях Splay Страница Википедии сказано (в разделе "Преимущества"):

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

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

Answer 1

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

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

Answer 2

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

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

//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

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

Answer 3

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