cómo implementar listas doblemente vinculadas

Question

¿Es posible tener una lista doblemente vinculada en Haskell, y cuál es la solución ideal para implementarlas? Estoy implementando un gráfico de escena donde cada widget tiene un padre y un hijo, y es beneficioso mirar hacia arriba y hacia abajo en el gráfico.

Answer 1

No es realmente práctico tener una lista doblemente vinculada en Haskell, porque tienes que construirla de una vez.

Por ejemplo, imagina que tienes una lista [1, 2, 3, 4, 5] que deseas vincular doblemente. Ahora, imaginemos cómo se representa la lista:

data DoubleList a 
    = LeftEnd a (DoubleList a) 
    | Middle a (DoubleList a) (DoubleList a) 
    | RightEnd a (DoubleList a) 

(I utilizar dos constructores diferentes para los dos extremos de la simplicidad)

Para construir la lista anterior, usted tiene que construir primero el primer elemento:

let e1 = LeftEnd 1 ... 

Pero para construir el primer elemento, ya que tener el segundo elemento:

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 ... 

Y para el segundo elemento, es necesario el tercero, etc:

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 e3 
    e3 = Middle 3 e2 e4 
    e4 = Middle 4 e3 e5 
    e5 = RightEnd 5 e4 

Esto es posible hacerlo en Haskell, debido a la evaluación perezosa; esta estrategia se llama "atar el nudo" (Y no tienes que ponerlo literalmente en un solo bloque let; puedes dividir la construcción en funciones)

Pero, en otras palabras, para hacer un doble- lista enlazada, necesita construirla de una vez, y si alguna vez desea cambiar alguna parte de ella, debe usar una Zipper o simplemente hacer una copia completa de la misma cada vez.

Yo recomendaría utilizar en su lugar Data.Sequence, que es una implementación de almacenamiento secuencial optimizada basada en árbol de huellas digitales. Admite una inserción, eliminación e iteración muy rápidas y sigue siendo una estructura de datos puramente funcional.

De lo contrario, es posible que desee utilizar Cremalleras, pero úselas para Árboles en lugar de Listas. Puede encontrar más información sobre cremalleras en el Haskell Wiki. Las cremalleras encajarían muy bien en esta situación, ya que ofrecen la funcionalidad exacta que buscas: si visitas un árbol con una cremallera, obtienes acceso a los "padres" de la parte del árbol que estás visitando, pero el árbol en sí no tiene que contener las referencias principales.

Answer 2

Dado que no tiene (normalmente) objetos de estilo OO en Haskell, es extraño pensar que los datos son conscientes de sí mismos. Es importante tener en cuenta que, en general, no se utiliza la agregación en los tipos de datos Haskell, lo que favorece la composición.

Es posible que desee ver en XMonad para ver si su diseño coincide con sus necesidades (el código es sorprendentemente legible).

También es posible que desee reestructurar su diseño para que nunca tenga que mirar por encima de usted (por ejemplo, al pasar "devoluciones de llamada" a los niños).

Es posible que también desee ver si puede escribir una cremallera para todo el gráfico.