Двумерная молния

Question

Вдохновленный недавним вопросом о 2d сетках в Haskell, мне интересно, можно ли создать двумерную молнию для отслеживания позиции в списке списков. Одномерная молния в списке позволяет нам эффективно перемещаться локально в большом списке (обычный пример - текстовый редактор). Но давайте говорить, что мы имеем второе измерение, как это:

grid = 
    [[ 1, 2, 3, 4, 5] 
    ,[ 6, 7, 8, 9,10] 
    ,[11,12,13,14,15] 
    ,[16,17,18,19,20] 
    ,[21,22,23,24,25]] 

Можем ли мы создать какую-то структуру данных молнии эффективно двигаться не только влево и вправо, но вверх и вниз в сетке здесь? Если да, то что, если мы заменим список списков бесконечным списком бесконечных списков, можем ли мы по-прежнему эффективно двигаться?

Answer 1

Не вполне, no. Один из ключевых аспектов работы молнии заключается в том, что они представляют собой местоположение в структуре по пути, используемому для его достижения, плюс дополнительные фрагменты, созданные на этом пути, с конечным результатом, который вы можете возвратить по этому пути и перестроить структуру как ты иди. Характер путей, доступных через структуру данных, таким образом ограничивает застежку-молнию.

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

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

Что вы может do создает некоторое представление о 2D расстоянии в структуру данных, так что, когда вы будете следовать по пути вниз по структуре, точки «ниже» вы близки друг к другу; идея состоит в том, чтобы свести к минимуму количество обратного отсчета, необходимого в среднем, для перемещения небольшого расстояния в 2D-пространстве. В результате получается примерно такой же подход, который необходим для поиск 2D-пространства по расстоянию - поиск ближайшего соседа, эффективное геометрическое пересечение, что-то вроде этого, и может быть сделано с такой же структурой данных, а именно space partitioning для создания многомерное дерево поиска. Внедрение застежки-молнии для quadtree, kd-tree или аналогичных структур является простым, как и любое другое дерево.

Answer 2

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

Верхние ряды и левые элементы хранятся в обратном порядке, чтобы обеспечить эффективное перемещение.

Я не уверен, что это относится как к застежке-молнии, хотя, хотя мы удерживаем «местоположение» в структуре данных, это не «путь».

-- Table sel left right top bottom 
data Table a = Table a [a] [a] [[a]] [[a]] deriving Show 

left :: Table a -> Table a 
left tab@(Table _ [] _ _ _) = tab 
left (Table sel (l:ls) rs ts bs) = Table l ls (sel:rs) ts bs 

right :: Table a -> Table a 
right tab@(Table _ _ [] _ _) = tab 
right (Table sel ls (r:rs) ts bs) = Table r (sel:ls) rs ts bs 

up :: Table a -> Table a 
up tab@(Table _ _ _ [] _) = tab 
up (Table sel ls rs (t:ts) bs) = Table sel' ls' rs' ts (b:bs) 
    where 
    (ls',(sel':rs')) = splitAt (length ls) t 
    b = ls ++ (sel:rs) 

down :: Table a -> Table a 
down tab@(Table _ _ _ _ []) = tab 
down (Table sel ls rs ts (b:bs)) = Table sel' ls' rs' (t:ts) bs 
    where 
    (ls',(sel':rs')) = splitAt (length ls) b 
    t = ls ++ (sel:rs) 

tableToList :: Table a -> [[a]] 
tableToList (Table sel ls rs ts bs) = (reverse ts) ++ [ls ++ (sel:rs)] ++ bs 

listToTable :: [[a]] -> Table a 
listToTable [] = error "cannot make empty table" 
listToTable ([]:_) = error "cannot make empty table" 
listToTable ((t:tr):ts) = Table t [] tr [] ts 

Это работает даже для бесконечных списков -

selected :: Table a -> a 
selected (Table sel _ _ _ _) = sel 

a :: Table Int 
a = listToTable $ replicate 10 [1..] 

selected a     #=> 1 
selected $ down a   #=> 1 
selected $ right $ down a #=> 2