danh sách chức năng thuần túy "True" kép liên kết và chia sẻ của các nút

Question

Recently tôi được giới thiệu đến this OCaml code mà trong Haskell có thể được viết như sau:

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" 

mà tôi mặc dù đã không một danh sách gấp đôi liên kết thích hợp triển khai, vì nó tạo lưu trữ mới trên truyền tải. OTOH có 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 

Chúng ta có thể nói rằng nó là chỉ này đang đó là đúng dl-list?

Chúng tôi có thể dựa vào mã này để giới thiệu chia sẻ thực sự các nút của danh sách dl không, do đó không có bộ nhớ mới nào được tạo trên truyền tải?

Sản phẩm biến có cùng tên trong Haskell luôn đề cập đến cùng "điều" hoặc có thể tách các lần xuất hiện của biến cùng tên tham khảo bản sao riêng của điều tương tự? (chỉnh sửa để thêm nhấn mạnh).

Answer 1

Tôi khuyên rằng sau này là triển khai "đúng", có.

Tôi không có sự thật để sao lưu nó, nhưng có vẻ như với tôi, với sự hiểu biết của tôi về việc thực hiện GHC, rằng sau này nên làm việc như thế nào bạn mong đợi một danh sách liên kết đôi để làm việc.

Answer 2

Bạn có thể hình dung cách bố trí bộ nhớ của cấu trúc dữ liệu của bạn trông như thế nào bằng cách sử dụng gói có tên là vacuum-cairo. Cài đặt từ hackage với cabal install vacuum-cairo sau đó bạn sẽ có thể để xác minh sự khác biệt trong hai cấu trúc bởi một cái gì đó như thế này trong GHCi:

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

Ở đó bạn có thể thấy các nút được chia sẻ bằng cách sử dụng DList nơi như DL là hai danh sách với một yếu tố ở giữa (Như đã chỉ ra, đây là loại Dây kéo).

Lưu ý: Đây là GHC cụ thể, việc triển khai khác có thể đại diện cho dữ liệu trong bộ nhớ khác nhau, nhưng điều này sẽ là điển hình.