data structures - pseudocodigo - Lista doblemente enlazada en un lenguaje de programación puramente funcional

operaciones con listas doblemente enlazadas

Question

¿Cómo hace uno para hacer listas doblemente vinculadas 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 OCaml, para la lista circular simplemente vinculada siempre puedes hacer algo como eso:

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

Para listas doblemente vinculadas, 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 cíclica doble y sucia doblemente 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

Answer 2

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 funcional puro, probablemente esté mejor con una de estas dos estructuras de datos:

• Una lista vinculada por separado con un puntero en el centro, desde el que puede ir a la izquierda oa la derecha (una variante de Huet''s "Zipper")

• 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 3

Hay una serie de enfoques.

Si no quieres mutar la lista doblemente vinculada una vez que la hayas construido, puedes "atar el nudo" confiando en la pereza.

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

Si quieres una lista mutable con doble enlace, necesitas falsificar referencias de alguna manera, o usar las reales, de la misma manera que lo hizo 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 4

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, solo 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