Структура данных, подобная Zipper, с более чем одним курсором

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

Позвольте мне объяснить с примерами:

  • Кто-то из канала #haskell сказал мне, что молнии используются в редакторе yi для представления положение курсора. Это здорово, но что, если вы хотите иметь два курсоры. Например, если вы хотите представить выбор, вам нужно знать начало и конец выбора.
  • В примере Minotaur на wikibooks они используют Zipper для представления позиции Minotaur внутри лабиринта. Если бы я хотел добавить врага в лабиринт, представление их позиции с помощью молнии сделало бы такой же смысл.
  • Последняя актуальна из моего мини-проекта, где все началось: в рамках обучения Haskell я пытаюсь визуализировать древовидную структуру с использованием cairo и gth2hs. Это прошло хорошо, но теперь я хотел бы выбрать один или несколько узлов и иметь возможность, например, перемещайте их. Поскольку может быть больше одного из выбранных узлов, я не могу просто использовать как указано в текстовых книгах.

Существует тривиальное (наивное?) решение, подобное тому, которое они использовали в ранних версиях XMonad, которое включает в себя конечные карты, как описано здесь.

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

Ответы

Ответ 2

См. этот документ. Кажется, я кое-что помню, что вторая производная имеет две дыры, которая, вероятно, вы хотите.