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

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

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), память, используемая сетью структуры молнии, никогда не освобождается. С другой стороны, он должен быть достаточно узким для того, чтобы "ячейки" могли быть общими, независимо от того, какой путь мы выберем, - это такая топология, которую мы хотели бы видеть в двухмерном списке списков.

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

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://stackru.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, нет смысла делать их ленивыми в Хаскеле, так как они все равно не позволят им выйти за рамки возможного.

Решетка строится рекурсивно, расширяя границы предоставленного входа 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

Интерфейс, вероятно, можно сделать еще проще, если Maybes. На свой страх и риск, естественно.

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