Как делать двойные ссылки на чистом функциональном языке? То есть, что-то вроде Haskell, где вы не в Монаде, поэтому у вас нет мутации. Является ли это возможным? (Одиночный список, очевидно, довольно прост).
Дважды связанный список на чисто функциональном языке программирования
Ответ 1
В чистом функциональном языке список с двойной связью не интересен. Идея двусвязного списка состоит в том, чтобы иметь возможность захватить node и идти в любом направлении, или иметь возможность сращиваться в середине списка. На чистом функциональном языке вы, вероятно, лучше с одной из этих двух структур данных:
-
Отдельно связанный список с указателем посередине, из которого вы можете идти либо влево, либо вправо (вариант Huet "Zipper" )
-
Дерево пальцев, которое представляет собой продуманную структуру данных, изобретенную Ральфом Хинзе и Росс Патерсон.
Я большой поклонник молнии; он полезен во многих ситуациях.
Ответ 2
Существует несколько подходов.
Если вы не хотите мутировать двусвязный список, как только вы его построили, вы можете просто "связать узел", опираясь на ленивость.
http://www.haskell.org/haskellwiki/Tying_the_Knot
Если вам нужен изменчивый двусвязный список, вам нужно как-то подделать ссылки - или использовать настоящие - a la the trick, предложенные Олегом Кисейловым и реализованные здесь:
http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html
Интересно отметить, что первое полагается на лозунги, чтобы добиться успеха. Вам в конечном итоге нужна мутация или лень, чтобы связать узел.
Ответ 3
Я бы повторил музыкальный вопрос: "для чего вам это нужно?" Как замечает Норман Рэмси: если вам нужен многонаправленный обход, то молнии легче; если вам нужно быстрое сращивание, пальцевые деревья хорошо работают.
Но просто посмотреть, как это выглядит...
import Control.Arrow
import Data.List
data LNode a = LNode { here :: a, prev :: LList a, next :: LList a }
type LList a = Maybe (LNode a)
toList :: LList a -> [a]
toList = unfoldr $ fmap $ here &&& next
fromList :: [a] -> LList a
fromList l = head nodes where
nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes
append :: LList a -> LList a -> LList a
append = join Nothing where
join k (Just a) b = a' where
a' = Just $ a { prev = k, next = join a' (next a) b }
join k _ (Just b) = b' where
b' = Just $ b { prev = k, next = join b' Nothing (next b) }
join _ _ _ = Nothing
Ответ 4
В OCaml для кругового простого списка вы всегда можете сделать что-то вроде этого:
type t = { a : t Lazy.t }
let cycle n =
let rec start = {a = lazy (aux n) }
and aux = function
| 0 -> start
| n -> { a = lazy (aux (n-1))}
in start
Для двусвязных списков я представляю себе возможность сделать что-то подобное. Но вы должны полагаться на лень и на записи, являющиеся дружественными структурами, когда дело доходит до ввода. Быстрый и грязный циклический дублированный список:
type 'a t = { data : 'a; before : 'a t Lazy.t; after : 'a t Lazy.t }
let of_list l =
match l with [] -> assert false | hd::tl ->
let rec start = { data = hd; before = last; after = next }
and couple = lazy (aux (lazy start) hd)
and next = lazy (Lazy.force (fst (Lazy.force couple)))
and last = lazy (Lazy.force (snd (Lazy.force couple)))
and aux before = function
| [] -> (lazy start), before
| hd::tl -> let rec current = lazy { data = hd; before = before; after = after }
and couple = lazy (aux current tl)
and after = lazy (Lazy.force (fst (Lazy.force couple)))
and last = lazy (Lazy.force (snd (Lazy.force couple))) in
current, last
in start