Lista doblemente enlazada en un lenguaje de programación puramente funcional

Question

¿Cómo se hace para hacer listas doblemente enlazadas en un lenguaje funcional puro? Es decir, algo así como Haskell en el que no estás en una mónada por lo que no tienes una mutación. ¿Es posible? (La lista enlazada con Singly es obviamente bastante fácil).

Answer 1

En un lenguaje funcional puro, una lista doblemente vinculada no es tan interesante. La idea de una lista doblemente vinculada es poder tomar un nodo e ir en cualquier dirección, o para poder empalmar en el medio de una lista. En un lenguaje functionaly pura que probablemente está mejor con una de estas estructuras de dos datos:

• Una lista enlazada con un puntero en el centro, desde donde se puede ir por la izquierda o hacia la derecha (una variante de Huet de "Cremallera")

• Un árbol de dedo, que es una estructura de datos alucinante inventada por Ralf Hinze y Ross Paterson.

Soy un gran admirador de la cremallera; es útil en muchas situaciones.

Answer 2

Hay una serie de enfoques.

Si no quiere mutar la lista de doble enlace una vez que la ha construido, puede 'atar el nudo' confiando en la pereza.

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

Si desea una lista doblemente enlazada mutable que necesita para referencias falsas de alguna manera - o utilizar los reales - al estilo del truco propuesto por Oleg Kiseylov e implementado aquí:

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

Curiosamente, tenga en cuenta que el primero se basa fundamentalmente en la pereza para tener éxito. En última instancia, necesitas mutación o pereza para hacer el nudo.

Answer 3

Reitero la pregunta de musicfan: "¿para qué necesitas esto exactamente?" Como señala Norman Ramsey: si necesita un recorrido multidireccional, entonces las cremalleras son más fáciles; si necesita un empalme rápido, los árboles con los dedos funcionan bien.

Pero, sólo para ver cómo se ve ...

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

En OCaml, para circular simplemente lista enlazada siempre se puede hacer algo así:

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 

Por lista doblemente enlazada, Me imagino que es posible hacer algo similar. Pero debes confiar en la pereza y en que los registros sean estructuras amigables cuando se trata de tipear. Lista doblemente cíclica cíclica rápida y sucia:

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