Я читал главу в LYAH, которая не имела для меня никакого смысла. Я понимаю, что молнии могут произвольно пересекать древовидную структуру, но мне нужно кое-что прояснить. Кроме того, могут ли молнии быть обобщены на любую структуру данных?
ds.data-structures
functional-programming
tree
n_ary_crazy
источник
источник
Ответы:
В целом, молния - это структура данных с дырой в ней. Молнии используются для обхода / манипулирования структурами данных, а отверстие соответствует текущему фокусу обхода. Обычно имеется также элемент рассматриваемой структуры данных, так что у него есть (список) молния и список или (дерево) молния и дерево. Молния позволяет программисту эффективно перемещаться по структуре данных, даже заменяя элемент в фокусе. Пара молнии и элемент в фокусе удовлетворяют ограничению, согласно которому размещение элемента в фокусе в отверстии дает исходную структуру данных.
Молния может быть обобщена на произвольные индуктивные типы данных. Эта концепция может быть определена с помощью индексации по типу (см. Типы с индексацией по типу ). Они также связаны с идеей производной структуры данных и были изучены с точки зрения теории категорий .
источник
Застежка-молния - это, как правило, пара вещей: это структура с отверстием, фокус , показывающий , где в структуре вы находитесь, вместе с дорожкой , записывающая, как вы попали в этот фокус. (Этот путь - след Хлебных крошек ЛЯХА.)
Путь - это то, как вы на самом деле применяете изменения к структуре: «идти вниз, идти налево, увеличивать значение». Многократно применяя «идти вверх» (
go_upв статье Хуэта ) на этом этапе, вы можете пересмотреть свои шаги и в итоге получить новую, мутированную копию оригинальной структуры.Они действительно могут быть обобщены на другие структуры:
источник