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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

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

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

up :: Table a -> Table a
up [email protected](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 [email protected](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

Ответ 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 /info/16835198/birecursively-defining-a-doubly-infinite-list-of-lists/25740179#25740179
  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

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

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