"True" pure functional doubly-linked list and Sharing of nodes

Question

Recently I was introduced to this OCaml code which in Haskell can be written as:

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"

which I though was not a proper doubly-linked list implementation, as it creates new storage on traversal. OTOH there's 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

Can we say that it is only this code that's true dl-list?

Can we rely on this code to introduce true sharing of nodes of the dl-list, so that no new storage is created on traversal?

Is the same-named variable in Haskell always referring to the same "thing" or might separate occurrences of the same-named variable refer to separate copy of the same thing? (edited to add emphasis).

Answer 1

You can visualise how the memory layout of your data structure looks using a package called vacuum-cairo. Install from hackage with cabal install vacuum-cairo then you should be able to verify the difference in the two structures by something like this in GHCi:

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

There you can see the nodes are shared using the DList where as DL is two lists with an element in between (As pointed out, this is kind of Zipper).

Note: This is GHC specific, a different implementation might represent the data in memory differently, but this would be typical.

Answer 2

I would suggest that the latter is the "correct" implementation, yes.

I do not have facts with which to back that up, but it would seem to me, given my understanding of the GHC implementation, that the latter should work how you'd expect a double-linked list to work.