Si no puede cambiar el valor de una variable en Haskell, ¿cómo crea estructuras de datos?

Question

Según el título.

Tengo el siguiente código que crea un árbol de búsqueda binaria, pero si quiero crearlo y cambiarlo dinámicamente con la entrada del usuario, ¿cómo lo haré si no puedo cambiar el valor de una variable en haskell?!?

find :: (Ord a) => Node a -> a -> Bool 
find (Node val left right) s 
    | s == val  = True 
    | s < val  = find left s 
    | s > val  = find right s 

find Empty s = False 

data Node a = Node a (Node a) (Node a) 
       | Empty 

myTree = Node "m" (Node "a" Empty Empty) 
        (Node "z" Empty Empty) 

¡Gracias de antemano!

Answer 1

La idea detrás de estructuras de datos puramente funcionales es calcular nuevos valores en lugar de cambiarlos y pasarlos (recursivamente) en parámetros en lugar de almacenarlos globalmente.

Así que dada una función

insert :: Ord a => Node a -> a -> Node a 

su Programm podría tener este aspecto

-- Let the user enter k values that are stored in a tree structure 
addTreeItems :: Int -> Node Int -> IO (Node Int) 
addTreeItems 0 tree = return tree 
addTreeItems k tree = do 
    putStr "Enter new item: " 
    item <- readLn 
    addTreeItems (k - 1) (insert tree item) -- Recursively pass the tree 

main = do 
    tree <- addTreeItems 10 Empty 
    -- ... 

El uso de funciones de ayuda monádicos, esto podría simplificarse en cosas como

(foldl insert Empty) `liftM` (sequence $ replicate k (putStr "Enter new item: " >> readLn)) 

Si desea para actualizar los valores en una posición determinada, necesitará estructuras de datos más avanzadas, como un zipper, que sin embargo siguen siendo puramente funcionales.

Answer 2

Darío dio una buena respuesta directa. Si desea información más detallada, hay Purely Functional Data Structures de Chris Okasaki, un libro completo sobre el tema. Lo compré yo mismo, pero lamentablemente, no tengo tiempo para experimentar con las ideas.

Answer 3

Asigna un nuevo nodo de árbol y el anterior se queda. Esta técnica requiere un asignador realmente bueno, pero habilita todo tipo de dispositivos ingeniosos porque otras partes del programa todavía tienen acceso a los nodos antiguos. Este es un regalo del cielo para ciertos tipos de algoritmos especulativos u otros trucos que involucran las llamadas "estructuras de datos persistentes".

Eventualmente asignas una nueva raíz para tu árbol y ¿entonces qué? Como dice Dario, lo pasa como un parámetro a una función (en lugar de almacenarlo en una variable global).

Así

• La mutación de un campo de una estructura asignada en el montón se hace la asignación de una nueva estructura en el montón.

• La mutación de una variable global se hace pasar un parámetro a una función

A veces también tiene sentido tomar lo que habría sido una colección de variables globales en C y poner a todos en un objeto asignado en montón

---

P.S. Si realmente lo desea, puede tener variables globales variables en Haskell. Es, después de todo, el lenguaje de programación imperativo más fino del mundo (según Wadler o Peyton Jones, me olvido de quién). Pero si hace esta pregunta, realmente no quiere. Todavía.