lista funcional pura "Verdadero" doblemente enlazada y recursos compartidos de nodos

Question

Recently me presentaron a this OCaml code que, en Haskell se puede escribir como:

data DL a = DL [a] a [a] 

create [] = error "empty list" 
create (x:xs) = DL [] x xs 

next (DL pr x (h:tl)) = DL (x:pr) h tl 
next _ = error "end of dlist" 

prev (DL (p:pr) x tl) = DL pr p (x:tl) 
prev _ = error "start of dlist" 

la que yo estaba, aunque no una lista doblemente enlazada adecuada implementación, ya que crea un nuevo almacenamiento en el cruce. Otoh hay this Haskell code:

data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) } 

create = go Leaf 
    where go _ []  = Leaf 
     go prev (x:xs) = current 
      where current = Node prev x next 
        next = go current xs 

Podemos decir que es solamente el código eso es cierto dl-lista?

¿Podemos confiar en este código para introducir el intercambio real de los nodos de la lista dl, de modo que no se cree un nuevo almacenamiento en el recorrido?

¿Está el mismo nombre variable en Haskell haciendo siempre referencia a la misma "cosa" o podría separar las ocurrencias del mismo nombre variable de referencia a copia separada de la misma cosa? (editado para agregar énfasis).

Answer 1

Sugeriría que la última es la implementación "correcta", sí.

No tengo datos para respaldarlo, pero me parece, dado mi conocimiento de la implementación de GHC, que este último debería funcionar como se esperaría que funcionara una lista de doble enlace.

Answer 2

Puede visualizar cómo se ve el diseño de la memoria de su estructura de datos utilizando un paquete llamado vacuum-cairo. Instala desde hackage con cabal install vacuum-cairo, entonces debería ser capaz de verificar la diferencia de las dos estructuras por algo como esto en GHCi:

> import System.Vacuum.Cairo 
> view $ create [1..5] 

Allí se puede ver los nodos son compartidos con el DList donde como DL es dos listas con un elemento intermedio (como se señaló, esto es una especie de Cremallera).

Nota: Esto es específico de GHC, una implementación diferente podría representar los datos en la memoria de manera diferente, pero esto sería típico.