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

Question

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

Answer 1

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

• односвязан списка с указателем в середине, из которого вы можете пойти влево или вправо (вариант Huet-х «Застежка-молния»)

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

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

Answer 2

Существует несколько подходов.

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

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

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

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

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

Answer 3

Я бы повторил вопрос musicfan: «для чего вам это нужно?» Как замечает Норман Рэмси: если вам нужен многонаправленный обход, то молнии легче; если вам нужно быстрое сращивание, пальцевые деревья хорошо работают.

Но, просто чтобы посмотреть, как это выглядит ...

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