Doppelt verknüpfte Liste in einer rein funktionalen Programmiersprache

Question

Wie geht man doppelt verknüpfte Listen in einer reinen funktionalen Sprache? Das heißt, etwas wie Haskell, wo Sie nicht in einer Monade sind, so dass Sie keine Mutation haben. Ist es möglich? (Einfach verknüpfte Liste ist offensichtlich ziemlich einfach).

Answer 1

In einer reinen funktionalen Sprache ist eine doppelt verkettete Liste nicht so interessant. Die Idee einer doppelt verknüpften Liste besteht darin, in der Lage zu sein, einen Knoten zu greifen und in irgendeine Richtung zu gehen oder in der Mitte einer Liste zu spleißen. In einer reinen functionaly Sprache sind Sie wahrscheinlich besser dran mit einem dieser beiden Datenstrukturen:

• Eine einfach verkettete Liste mit einem Zeiger in der Mitte, von dem aus Ihnen entweder nach links oder nach rechts (eine Variante von Huet gehen können "Zipper")

• Ein Fingerbaum, der eine atemberaubende Datenstruktur von Ralf Hinze und Ross Paterson ist.

Ich bin ein großer Fan des Reißverschlusses; Es ist in vielen Situationen nützlich.

Answer 2

Es gibt eine Reihe von Ansätzen.

Wenn Sie die doppelt verkettete Liste nicht mutieren möchten, nachdem Sie sie erstellt haben, können Sie einfach "den Knoten knüpfen", indem Sie sich auf Faulheit verlassen.

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

Wenn Sie eine veränderbare doppelt verknüpfte Liste wollen, müssen Sie auf gefälschte Referenzen irgendwie - oder echte verwenden - zu dem Trick vorgeschlagen von Oleg Kiseylov und hier umgesetzt:

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

Interessanterweise beachten Sie, dass ersteres beruht auf Faulheit, um erfolgreich zu sein. Sie brauchen schließlich Mutation oder Faulheit, um den Knoten zu binden.

Answer 3

Ich würde musicfan Frage wiederholen: "Was genau brauchen Sie das für?" Wie Norman Ramsey bemerkt: Wenn Sie multidirektionale Traversierung benötigen, dann sind Zipper einfacher; Wenn Sie schnelles Spleißen benötigen, arbeiten Fingerbäume gut.

Aber, nur um zu sehen, wie es aussieht ...

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, für die Zirkular einfach Liste verknüpft Sie immer so etwas tun kann:

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 

Für doppelt verkettete Listen, Ich stelle mir vor, dass es möglich ist, etwas Ähnliches zu tun. Aber man muss sich auf Faulheit verlassen und auf Platten, die beim Tippen freundlich sind. Schnelle und schmutzige zyklische doppelt verkettete Liste:

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