"真正的"纯功能双链表和节点共享

Question

最近我被介绍了这个OCaml代码,它在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有这个Haskell代码:

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的包来可视化数据结构的内存布局.从hackage安装cabal install vacuum-cairo然后您应该能够通过GHCi中的类似内容验证两个结构的差异:

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

在那里你可以看到使用DList共享节点,其中DL是两个列表,其间有一个元素(如上所述,这是一种Zipper).

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

Answer 2

我建议后者是“正确”的实现，是的。

我没有事实来支持这一点，但在我看来，鉴于我对 GHC 实现的理解，后者应该按照您期望的双链表的方式工作。