Двусвязный список на чисто функциональном языке программирования

Question

Как можно создавать двусвязные списки на чистом функциональном языке? То есть что-то вроде Хаскелла, где вы не в монаде, поэтому у вас нет мутации. Является ли это возможным? (Единственно связанный список, очевидно, довольно прост).

Answer 1

На чисто функциональном языке список с двумя связями не так интересен. Идея двусвязного списка состоит в том, чтобы иметь возможность захватывать узел и двигаться в любом направлении, или иметь возможность склеиваться в середине списка. В чистом функциональном языке вам, вероятно, лучше использовать одну из следующих двух структур данных:

• Односвязный список с указателем посередине, из которого можно перейти влево или вправо (вариант «молнии» Хуэта)

• Дерево пальца, представляющее собой потрясающую структуру данных, изобретенную Ральфом Хинце и Россом Патерсоном.

Я большой поклонник молнии; это полезно во многих ситуациях.

Answer 2

Есть несколько подходов.

Если вы не хотите видоизменять двусвязный список после его создания, вы можете просто «связать себя узами брака», полагаясь на лень.

http://www.haskell.org/haskellwiki/Tying_the_Knot

Если вам нужен изменяемый список с двумя связями, вам нужно каким-то образом фальсифицировать ссылки - или использовать реальные - в виде хитрости, предложенной Олегом Кисейловым и реализованной здесь:

http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html

Интересно, заметьте, что первое основывается на лени, чтобы преуспеть. В конечном итоге вам нужна мутация или лень, чтобы завязать узел.

Answer 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

Answer 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