Zipper bidimensionale

Question

Ispirato alla recente domanda sulle griglie 2D in Haskell, mi chiedo se sarebbe possibile creare una cerniera bidimensionale per tenere traccia di una posizione in un elenco di elenchi. Una cerniera unidimensionale in un elenco ci consente di spostarci in modo efficiente localmente in un elenco di grandi dimensioni (l'esempio comune è un editor di testo). Ma supponiamo di avere una seconda dimensione del genere:

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]] 

Possiamo creare una sorta di struttura dati cerniera a muoversi in modo efficiente non solo a destra ea sinistra, ma su e giù nella griglia qui? In tal caso, cosa succede se sostituiamo la lista delle liste con una lista infinita di liste infinite, possiamo ancora ottenere movimento efficiente?

Answer 1

Non piuttosto, n. Uno degli aspetti chiave di come funzionano le cerniere è che rappresentano una posizione in una struttura da un percorso utilizzato per raggiungerla, oltre ai frammenti extra creati lungo la strada, con il risultato finale che è possibile tornare indietro lungo quel percorso e ricostruire la struttura come tu vai. La natura dei percorsi disponibili attraverso la struttura dati limita quindi la cerniera.

Poiché le posizioni sono identificate dai percorsi, ogni percorso distinto rappresenta una posizione diversa, quindi qualsiasi struttura dati con più percorsi allo stesso valore non può essere utilizzata con una chiusura lampo - ad esempio, considerare un elenco ciclico o qualsiasi altra struttura con percorsi di looping.

Il movimento arbitrario nello spazio 2D non si adatta perfettamente ai requisiti precedenti, quindi è possibile dedurre che una cerniera 2D sarebbe necessariamente limitata. Forse dovresti iniziare dall'origine, percorrere un sentiero attraverso la struttura, e quindi tornare indietro lungo quel percorso per raggiungere altri punti, ad esempio. Ciò implica anche che per qualsiasi punto della struttura, ci sono altri punti che possono essere raggiunti solo tramite l'origine.

Che cosa può può creare una nozione di distanza 2D nella struttura di dati, in modo che quando si segue un percorso verso il basso attraverso la struttura, i punti "sotto" si sono vicini l'uno all'altro; l'idea è di ridurre al minimo la quantità di backtracking necessaria in media per spostare una breve distanza nello spazio 2D. Questo finisce per essere approssimativamente lo stesso approccio necessario per ricerca spazio 2D per distanza - ricerca del vicino più vicino, intersezione geometrica efficiente, quel genere di cose - e può essere fatto con lo stesso tipo di struttura dati, ovvero space partitioning per creare un albero di ricerca con dimensioni più elevate. Implementare una cerniera per un quadtree, un kd-tree o strutture simili è semplice, proprio come qualsiasi altro albero.

Answer 2

Bene, è possibile utilizzare qualcosa di semplice come il seguente codice. Rappresentiamo una tabella in base alle righe superiori dell'elemento selezionato, le righe in basso dell'elemento selezionato, più gli elementi a sinistra di quello selezionato e gli elementi a destra di quello selezionato.

Le righe superiori e gli elementi di sinistra vengono memorizzati in ordine inverso per consentire uno spostamento efficiente.

Non sono sicuro se questo si qualifica come una cerniera, perché anche se abbiamo una "posizione" nella struttura dati, non è un "percorso".

-- 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 

funziona questo anche per liste infinite -

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