¿Cómo codigo un árbol de objetos en Haskell con punteros a padres e hijos?

Question

Tengo el siguiente problema: Tengo un árbol de objetos de diferentes clases donde una acción en la clase secundaria invalida el elemento primario. En lenguajes imperativos, es trivial de hacer. Por ejemplo, en Java:

public class A { 
    private List<B> m_children = new LinkedList<B>(); 
    private boolean m_valid = true; 

    public void invalidate() { 
     m_valid = false; 
    } 

    public void addChild(B child) { 
     m_children.add(child); 
     child.m_parent = this; 
    } 
} 

public class B { 
    public A m_parent = null; 
    private int m_data = 0; 

    public void setData(int data) { 
     m_data = 0; 
     m_parent.invalidate(); 
    } 
} 

public class Main { 
    public static void main(String[] args) { 
     A a = new A(); 
     B b = new B(); 
     b.setData(0); //invalidates A 
    } 
} 

¿Cómo hago lo anterior en Haskell? No puedo entender esto, ya que una vez que construyo un objeto en Haskell, no puede ser cambiado.

Me agradecería mucho si se publica el código Haskell correspondiente.

EDIT: el problema que estoy tratando de resolver es el siguiente:

He una aplicación que edita documentos. Un documento es una jerarquía de objetos. Cuando se modifican las propiedades de los objetos secundarios, el documento debe establecerse en un estado no válido, para que el usuario sepa que el documento debe validarse.

Answer 1

No tengo mucha experiencia con Haskell, pero hasta donde sé, no es posible tener círculos en el gráfico de referencia en lenguajes funcionales puros. Eso significa que:

1. Usted no puede tener un 2 vías listas, los niños en los árboles que apuntan a sus padres, etc. *
2. En general no es suficiente para cambiar un solo nodo. Cualquier nodo que se modifique requiere cambios en cada nodo, comenzando desde la "raíz" de las estructuras de datos hasta el nodo que desea cambiar.

La conclusión es que no trataría de tomar un algoritmo Java (o cualquier otro lenguaje imperativo) e intentar convertirlo a Haskell. En su lugar, intente encontrar un algoritmo más funcional (y tal vez incluso una estructura de datos diferente) para resolver el problema.

EDIT:

Desde su aclaración no es del todo claro si necesita o no para invalidar sólo el padre directa del objeto que ha cambiado o todas sus antepasados ​​en la jerarquía, pero que en realidad no importa tanto. Ya que invalidar un objeto básicamente significa cambiarlo y eso no es posible, básicamente tiene que crear un duplicado modificado de ese objeto, y luego tiene que hacer que su padre lo señale, por lo que debe crear un nuevo objeto para eso también. . Esto continúa hasta llegar a la raíz. Si tiene alguna recursividad para atravesar el árbol para "modificar" su objeto, puede volver a crear la ruta desde ese objeto hasta la raíz al salir de la recursión.

Espero que tenga sentido. : s

* Como se señala en los comentarios de jberryman y en otras respuestas, es posible crear gráficos de referencia circulares en Haskell utilizando evaluación diferida.

Answer 2

Para responder la pregunta en su título: Sí, puede crear nodos que tengan enlaces a sus padres y sus hijos. Ejemplo:

--    parent  children 
data Tree = Node (Maybe Tree) [Tree] 
root = Node Nothing [a,b] -- I can "forward reference" a and b because haskell is lazy 
a = Node (Just root) [] 
b = Node (Just root) [] 

La pregunta es si esto es útil para su caso de uso en particular (muchas veces no lo es).

Ahora la pregunta en su cuerpo: tiene razón, no puede cambiar un valor después de haber sido creado.Entonces, una vez que tenga un árbol válido, siempre tendrá un árbol válido siempre que la variable que hace referencia a ese árbol esté dentro del alcance.

Realmente no describiste el problema que estás tratando de resolver, así que no puedo decirte cómo modelar funcionalmente lo que estás tratando de hacer, pero estoy seguro de que hay una manera de no mutar el árbol .

Answer 3

Examine el uso de la instancia Functor del tipo Maybe.

Por ejemplo, tal vez su problema es algo como esto: desea insertar un elemento en un árbol binario, pero solo si no está presente. Se podría hacer eso con algo como:

data Tree a = Node a (Tree a) (Tree a) 
      | Tip 

maybeInsert :: a -> Tree a -> Maybe (Tree a) 
maybeInsert a Tip = Just $ Node a Tip Tip 
maybeInsert a (Node a' l r) 
    | a == a' = Nothing 
    | a < a' = fmap (\l'-> Node a' l' r) (maybeInsert a l) 
    | a > a' = fmap (\r'-> Node a' l r') (maybeInsert a r) 

Así que la función devolverá Nothing si encontramos el elemento que ya está presente, o volver Just el nuevo árbol con el elemento insertado.

Esperemos que sea relevante para lo que sea que estés tratando de hacer.

Answer 4

La modificación de un árbol que podría requerir excursiones frecuentes hasta la raíz y la parte posterior parece ser el trabajo perfecto para una variante de la estructura de datos Zipper con "cicatrices", en la terminología del documento original de Huet; las muestras de código del documento también sugieren un nombre de "memorización de cremallera". Por supuesto, con cierto cuidado, también se podría usar una cremallera normal, pero la versión aumentada podría ser más conveniente y/o eficiente de usar.

La idea básica es la misma que la de una cremallera normal, que ya permite subir y bajar un árbol de una manera puramente funcional (sin punteros atrás explícitos), pero se siguió una operación de "subir" mediante una operación "descender" se convierte en no operativa, dejando el foco en el nodo original (mientras que con la cremallera normal lo movería al hermano más a la izquierda del nodo original).

Aquí hay un enlace al artículo: Gérard Huet, Functional Pearl: The Zipper. Son solo seis páginas, pero las ideas contenidas en ellas son de gran utilidad para cualquier programador funcional.

Answer 5

Aquí hay un código de cremallera que muestra la fácil modificación de los datos apuntados por un cursor, así como una propiedad "global" del árbol. Construimos un árbol, movemos el cursor al nodo que inicialmente contiene un 1, lo cambiamos a un 3 y quedamos con un cursor apuntando a ese nodo en un árbol totalmente actualizado.

import Data.Maybe (fromJust) 
import Data.Tree 
import Data.Tree.Zipper 

type NodeData = Either Bool Int 
type TreePath a = [TreePos Full a -> TreePos Full a] 

firstChild' = fromJust . firstChild 
parent'  = fromJust . parent 
prev'  = fromJust . prev 
next'  = fromJust . next 

-- Determine the path from the root of the tree to the cursor. 
pathToMe :: TreePos Full NodeData -> TreePath NodeData 
pathToMe t | isRoot t = [] 
      | isFirst t = firstChild' : pathToMe (parent' t) 
      | otherwise = next' : pathToMe (prev' t) 

-- Mark a tree as invalid, but leave the cursor in the same place. 
invalidate :: TreePos Full NodeData -> TreePos Full NodeData 
invalidate t = foldr ($) (setLabel (Left False) (root t)) (pathToMe t) 

-- Set a node's internal data. 
setData :: Int -> TreePos Full NodeData -> TreePos Full NodeData 
setData = (invalidate .) . setLabel . Right 

main = let tree1 = Node (Left True) [Node (Right 1) [], Node (Right 2) []] 
      Just cursor = firstChild (fromTree tree1) 
      tree2 = setData 3 cursor 
     in do putStrLn (drawTree (fmap show tree1)) 
      putStrLn (drawTree (fmap show (toTree tree2))) 
      putStrLn $ "Cursor at "++show (label tree2) 

Salida:

Left True 
| 
+- Right 1 
| 
`- Right 2 

Left False 
| 
+- Right 3 
| 
`- Right 2 

Cursor at Right 3 

Answer 6

No se pudo pereza tener cuidado de asegurarse de que la validación no sucede muy a menudo? De esta forma, no necesita almacenar el campo m_valid.

Por ejemplo, si solo valida al guardar, puede editar los objetos a su gusto, sin revalidar todo el tiempo; solo cuando el usuario presiona el botón "Guardar" se calcula el valor de validateDoc. Como no estoy seguro de cuál es su noción de los medios válidos y para qué los necesita, podría ser totalmente de la marca.

no probados & código incompleto:

data Document = Document { subDocs :: [SubDoc] } 
data SubDoc = SubDoc { content :: String } 

addSubDoc :: SubDoc -> (Document -> Document) 
addSubDoc = error "not yet implemented: addSubDoc" 

modifySubDoc :: Int -> (SubDoc -> SubDoc) -> (Document -> Document) 
modifySubDoc = error "not yet implemented: modifySubDoc" 


validateDoc :: Document -> Bool 
validateDoc = all validateSubDoc . subDocs 

validateSubDoc :: SubDoc -> Bool 
validateSubDoc = not . null . contents 

Asumo la validez general del documento depende sólo de los subdocumentos (simulado aquí, haciendo que éstos contienen una cadena no vacía).

Por cierto, creo que se olvidó de a.addChild(b); en main.