Lazy vs Eager evaluación y la construcción de listas de doble enlace

Question

No puedo dormir! :)

He escrito un programa pequeño que construye una lista de enlaces dobles en Haskell. La propiedad del lenguaje básico para hacerla fue la evaluación perezosa (vea el grupo de código a continuación). Y mi pregunta es ¿puedo hacer lo mismo en un puro lenguaje funcional con evaluación ansioso o no? En cualquier caso, ¿qué propiedades ansioso lenguaje funcional deben tener para poder construir dicha estructura (impureza?)?

import Data.List 

data DLList a = DLNull | 
    DLNode { prev :: DLList a 
      , x :: a 
      , next :: DLList a 
      } 
    deriving (Show) 

walkDLList :: (DLList a -> DLList a) -> DLList a -> [a] 
walkDLList _ DLNull = [] 
walkDLList f n@(DLNode _ x _) = x : walkDLList f (f n) 

-- Returns first and last items. 
makeDLList :: [a] -> (DLList a, DLList a) 
makeDLList xs = let (first, last) = step DLNull xs in (first, last) 
    where 
    step prev [] = (DLNull, prev) 
         -- Here I use laziness. 'next' is not built yet, it's a thunk. 
    step prev (x : xs) = let this = DLNode prev x next 
          (next, last) = step this xs 
         in (this, last) 

testList :: [Int] -> IO() 
testList l = let 
    (first, last) = makeDLList l 
    byNext = walkDLList next first 
    byPrev = walkDLList prev last 
    in do 
    putStrLn $ "Testing: " ++ show l 
    print byNext 
    print byPrev 

main = do 
    testList [] 
    testList [1, 2, 3, 4] 

Answer 1

Mientras una lengua tiene algo así como cierres, etc. lambdas siempre se puede simular la pereza. Se podría reescribir ese código, incluso en Java (sin mutar las variables, etc), sólo tiene que envolver cada operación "perezosa" en algo así como

interface Thunk<A> { 
    A eval(); 
} 

Por supuesto, esto sería terrible, pero es posible.

Answer 2

En el subconjunto de Prolog sin retrotracción, que se puede ver como explícitamente establecido una vez con un lenguaje funcional puro, puede compilar fácilmente las listas de doble enlace. Es la transparencia referencial que lo hace difícil en Haskell, ya que prohíbe la configuración explícita del Prolog , explícitamente variables aún no establecidas, y en su lugar obliga a Haskell a lograr el mismo efecto en la forma distorsionada de "atar" el nudo". Creo.

Además, en realidad no hay mucha diferencia entre recursividad vigilado de Haskell en evaluación perezosa vs listas abiertas de Prolog construidas en contras de módulo-cola recursividad moda. IMO. Aquí hay, por ejemplo, un ejemplo de lazy lists in Prolog. El almacenamiento compartido memorizado se utiliza como mediador de acceso universal, por lo que los resultados de los cálculos previos se pueden organizar para almacenarlos en caché.

Ahora que lo pienso, puede usar C de forma restrictiva como un lenguaje funcional puro y entusiasta, si nunca restablece ninguna variable ni ningún puntero una vez que está configurado. Aún tiene punteros nulos, al igual que Prolog tiene variables, por lo que también lo es, explícitamente establecido una vez. Y, por supuesto, puedes crear listas doblemente vinculadas con él.

Así que la única pregunta que queda es, ¿te admitirá dichas reglajes vez idiomas como pura?

Answer 3

Una lista doblemente enlazada se puede implementar de una manera puramente funcional en un lenguaje entusiasta como zipper en una lista de enlace único. Ver, por ejemplo, Rosetta Code > Doubly-linked list > OCaml > Functional.