«Истинный» чистый функциональный двусвязный список и разделение узлов

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

Можем ли мы сказать, что только этот код true dl-list?

Можем ли мы полагаться на этот код, чтобы ввести истинное совместное использование узлов dl-списка, чтобы при обходе не создавалось новое хранилище?

Является ли переменная с тем же именем в Haskell всегда ссылающейся на одна и та же "вещь" , или отдельные экземпляры переменной с тем же именем могут относиться к отдельной копии одной и той же вещи? (отредактировано для добавления акцента).

Answer 1

Вы можете визуализировать, как выглядит структура памяти вашей структуры данных, используя пакет под названием вакуум-Каир.Установите из hackage с помощью cabal install vacuum-cairo, тогда вы сможете проверить разницу в двух структурах примерно так в GHCi:

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

Там вы можете видеть, что узлы используются совместно, используя DList, где как DLЭто два списка с элементом между ними (Как уже указывалось, это своего рода Zipper).

Примечание: Это специфично для GHC, другая реализация может представлять данные в памяти по-разному, но это будет типично.

Answer 2

Я бы предположил, что последняя является «правильной» реализацией, да.

У меня нет фактов, подтверждающих это, но мне кажется, учитывая мое понимание реализации GHC, что последний должен работать так, как вы ожидаете, что будет работать двойной список. *