haskell - Cremallera bidimensional

data-structures functional-programming

Question

Inspirado por la reciente pregunta sobre las cuadrículas 2d en Haskell, me pregunto si sería posible crear una cremallera bidimensional para mantener un registro de una posición en una lista de listas. Una cremallera unidimensional en una lista nos permite movernos de manera realmente eficiente en una lista grande (el ejemplo común es un editor de texto). Pero digamos que tenemos una segunda dimensión como esta:

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

¿Podemos crear algún tipo de estructura de datos de cremallera para mover de manera eficiente no solo a la izquierda y a la derecha sino también arriba y abajo en la cuadrícula aquí? Si es así, ¿qué pasa si reemplazamos la lista de listas con una lista infinita de listas infinitas, podemos obtener un movimiento eficiente?

Answer 1

Bueno, puedes usar algo simple como el siguiente código. Representamos una tabla por las filas superiores del elemento seleccionado, las filas inferiores del elemento seleccionado, más los elementos a la izquierda del seleccionado, y los elementos a la derecha del seleccionado.

Las filas superiores y los elementos de la izquierda se almacenan en orden inverso para permitir un movimiento eficiente.

No estoy seguro si esto califica como una cremallera, porque aunque tenemos una "ubicación" en la estructura de datos, no es una "ruta".

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

Esto incluso funciona para listas infinitas.

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 2

No del todo , no. Uno de los aspectos clave de cómo funcionan las cremalleras es que representan una ubicación en una estructura por una ruta utilizada para alcanzarla, además de fragmentos adicionales creados en el camino, con el resultado final que puede retroceder a lo largo de esa ruta y reconstruir la estructura como anda tu. La naturaleza de las rutas disponibles a través de la estructura de datos restringe la cremallera.

Debido a que las ubicaciones se identifican mediante rutas, cada ruta distinta representa una ubicación diferente, por lo que cualquier estructura de datos con múltiples rutas al mismo valor no se puede usar con una cremallera; por ejemplo, considere una lista cíclica o cualquier otra estructura con bucle caminos.

El movimiento arbitrario en el espacio 2D no cumple con los requisitos anteriores, por lo que podemos deducir que una cremallera 2D sería necesariamente algo limitada. Tal vez comenzarías desde el origen, caminarías un camino a través de la estructura y luego retrocederías un poco a lo largo de ese camino para llegar a otros puntos, por ejemplo. Esto también implica que para cualquier punto de la estructura, hay otros puntos que solo se pueden alcanzar a través del origen.

Lo que puede hacer es crear una noción de distancia 2D en la estructura de datos, de modo que al seguir un camino a través de la estructura, los puntos "debajo" estén cerca uno del otro; la idea es minimizar la cantidad de retroceso necesario en promedio para moverse una distancia corta en el espacio 2D. Esto termina siendo más o menos el mismo enfoque necesario para buscar en el espacio 2D por distancia (búsquedas cercanas a los vecinos, intersección geométrica eficiente, ese tipo de cosas) y se puede hacer con el mismo tipo de estructura de datos, es decir , partición del espacio para crear una Árbol de búsqueda tridimensional. Implementar una cremallera para un quadtree , un kd-tree o estructuras similares es sencillo, como cualquier otro árbol.