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

Question

Вдохновленный недавним вопросом о двумерных сетках в 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

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

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

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

Что вы можете сделать, это встроить некоторое представление о двухмерном расстоянии в данныеструктура, так что по мере того, как вы будете следовать по пути вниз по структуре, точки «под» вы будете рядом друг с другом;идея состоит в том, чтобы минимизировать количество возвратов, необходимых в среднем для перемещения на небольшое расстояние в 2D-пространстве.В итоге получается примерно такой же подход, который необходим для поиска в двумерном пространстве по расстоянию - поиск ближайшего соседа, эффективное геометрическое пересечение и тому подобное - и может быть реализован с такой же структурой данных, а именно разделение пространства для создания многомерного дерева поиска.Реализация молнии для 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

Answer 3

Я искал что-то похожее: способ дешево и легко ориентироваться (который включает в себя переход «назад») вдвойне бесконечный список списков.Вот мой взгляд на это.

Если я внимательно прочитаю ответы других, то, что я здесь представляю, это не действительно молния: пока навигация амортизируется O (1), памятьиспользуется zipper структура сеть никогда не освобождается.С другой стороны, он должен быть достаточно узким для того, чтобы «ячейки» могли быть общими, независимо от того, какой путь мы выберем, - это такая топология, которую мы хотели бы видеть в двумерном списке списков.

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

data FakeZip2D a = Z2 { z2Val   :: a
                      , goUp    :: !( Maybe (FakeZip2D a) )
                      , goDown  ::    Maybe (FakeZip2D a)
                      , goLeft  :: !( Maybe (FakeZip2D a) )
                      , goRight ::    Maybe (FakeZip2D a)
                      }

fromList2 :: [[a]] -> Maybe (FakeZip2D a)
fromList2 xss = head (head zss) where
  extended =       [ repeat Nothing ] ++
    map (\z -> [Nothing] ++ z ++ repeat Nothing) zss ++
                   [ repeat Nothing ]
  zss = zipWith4' row xss extended (drop 1 extended) (drop 2 extended)
  row xs prev cur next = Just <$> zipWith5' Z2 xs (tail prev) (tail next)
                                                  cur         (drop 2 cur)

  -- totally inspired by https://stackoverflow.com/a/54096748/12274
  zipWith4' f (a:as) (b:bs) ~(c:cs) ~(d:ds) =
    f a b c d : zipWith4' f as bs cs ds
  zipWith5' f (a:as) (b:bs) ~(c:cs) (d:ds) ~(e:es) =
    f a b c d e : zipWith5' f as bs cs ds es

Структура данных должна быть самоочевидной.Вверх и влево можно позволить себе быть строгим, потому что мы строим из односвязных списков.AFAIK, нет смысла делать их ленивыми в Haskell, так как они все равно не позволят чему-либо выйти за рамки.

Решетка построена рекурсивно, расширяя границы предоставленного ввода с помощью Nothing.Достаточно ленивые варианты zipWith, в которых я нуждался, вдохновлены ответами на другую серию моих вопросов по теме.

Вот он в действии:

demo :: IO ()
demo = do
  let multList2 = [[ i*j | j <- [0..] ] | i <- [0..] ]
      multZ2 = fromList2 multList2

  let rows = iterate (>>= goDown) multZ2
      cols = map (iterate (>>= goRight)) rows

  putStrLn "Multiplication table"
  mapM_ (print . map z2Val) $ take 5 $ map (catMaybes . take 5) cols

  putStrLn "List of squares"
  let goDiag = goRight >=> goDown
  print $ map z2Val $ take 25 $ catMaybes $ iterate (>>= goDiag) multZ2

  putStrLn "Convoluted list of squares"
  let goDiag' = goDown >=> goRight >=> goUp >=> goLeft >=> goDiag
  print $ map z2Val $ take 25 $ catMaybes $ iterate (>>= goDiag') multZ2

Интерфейс, вероятно, можно сделать еще проще в использовании, опустив Maybe s.Естественно, на свой страх и риск.

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