haskell - "True"纯功能双向链表和节点共享

Question

Recently我被介绍给 this OCaml code在 Haskell 中可以写成:

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"

我认为这不是一个合适的双向链表实现，因为它会在遍历时创建新的存储。 OTOH 有 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

我们可以说只有这段代码才是真正的 dl-list 吗？

我们是否可以依靠这段代码来引入真正的 dl-list 节点共享，从而在遍历时不创建新的存储？

Haskell 中的同名变量是否总是指代相同的“事物”，或者可能单独出现的同名变量引用同一事物的单独副本？ (编辑以增加重点)。

Answer 1

您可以使用名为 Vacuum-cairo 的包来可视化数据结构的内存布局。使用 cabal install vacuum-cairo 从 hackage 安装那么您应该能够通过 GHCi 中的类似方法来验证这两种结构的差异:

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

在那里你可以看到节点是使用 DList 共享的，其中 DL 是两个列表，中间有一个元素(正如所指出的，这是一种 Zipper)。

注意:这是特定于 GHC 的，不同的实现可能会以不同的方式表示内存中的数据，但这很典型。