Elenco collegato in modo discreto in un linguaggio di programmazione puramente funzionale

Question

Come si fa a fare liste doppiamente collegate in un linguaggio puramente funzionale? Cioè, qualcosa come Haskell dove non sei in una Monade quindi non hai la mutazione. È possibile? (La lista collegata singolarmente è ovviamente abbastanza semplice).

Answer 1

In un linguaggio puramente funzionale, una lista doppiamente collegata non è così interessante. L'idea di una lista doppiamente collegata è quella di essere in grado di afferrare un nodo e andare in entrambe le direzioni, o di essere in grado di unire il centro di una lista. In un linguaggio functionaly pura probabilmente si sta meglio con una di queste strutture dati due:

• una lista concatenata con un puntatore al centro, da cui si può andare a destra oa sinistra (una variante di Huet di "Zipper")

• Un albero di dita, una struttura di dati strabiliante inventata da Ralf Hinze e Ross Paterson.

Sono un grande fan della cerniera; è utile in molte situazioni.

Answer 2

Esistono diversi approcci.

Se non si desidera modificare l'elenco doppiamente collegato una volta costruito, è possibile "allacciare" facendo affidamento sulla pigrizia.

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

Se si desidera una lista doppiamente legata mutevole è necessario riferimenti falsi in qualche modo - o utilizzare quelli veri - a la il trucco proposto da Oleg Kiseylov e implementato qui:

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

È interessante notare che il primo si basa fondamentalmente sulla pigrizia per avere successo. Alla fine hai bisogno di mutazione o pigrizia per legare il nodo.

Answer 3

Vorrei ribadire la domanda di musicfan: "A cosa ti serve esattamente?" Come osserva Norman Ramsey: se hai bisogno di attraversamenti multidirezionali, le chiusure lampo sono più facili; se hai bisogno di uno splicing veloce, gli finger tree funzionano bene.

Ma, giusto per vedere come appare ...

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

In OCaml, per circolare semplicemente lista collegata si può sempre fare qualcosa di simile:

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 

Per le liste doppiamente collegate, Immagino sia possibile fare qualcosa di simile. Ma devi fare affidamento sulla pigrizia e sui record essere strutture amichevoli quando si tratta di digitare. Elenco ciclico congiunturale ciclico rapido e sporco:

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