Atravesando y filtrando un árbol en haskell

Question

Soy bastante nuevo para Haskell (todavía estoy trabajando en la comprensión total de las mónadas). Tengo un problema en el que tengo un árbol como la estructura

type Tree = [DataA] 

data DataA = DataA1 [DataB] 
      | DataA2 String 
      | DataA3 String [DataA] 
       deriving Show 

data DataB = DataB1 [DataA] 
      | DataB2 String 
      | DataB3 String [DataB] 
       deriving Show 

Lo que me gustaría hacer es ser capaz de atravesar esto y generar un nuevo árbol con un filtro. Por ejemplo, puedo querer cambiar todos los DataB2 en el árbol a "foo".

He visto ejemplos de árbol cuando están en la misma sección de datos, y los constructores son similares.

En el mundo de Python, me gustaría recorrer la lista, coincidir con lo que sea necesario y reemplazar el valor.

En Haskell supongo que necesito poder copiar mi árbol, pero ¿cómo manejas las listas ocultas en constructores y diferentes tipos de datos?

Answer 1

Puede utilizar la programación genérica para esto.

Una biblioteca de programación genérica de este tipo se llama Scrap Your Boilerplate. En la parte superior de su módulo, permitirá que la basura Su plancha de caldera por escrito:

{-# LANGUAGE DeriveDataTypeable #-} 

módulo de importación Data.Generics. Luego, además de Show, también obtenga Typeable y Data instancias para sus tipos de datos.

Ahora se puede escribir la función que pidió así:

toFoo :: Data a => a -> a 
toFoo = everywhere (mkT step) 
    where 
    step (DataA2 _) = DataA2 "foo" 
    step x   = x 

Eso es todo lo que necesita hacer para hacer este trabajo. Por ejemplo, cuando llama al toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []], la respuesta es [DataA1 [],DataA2 "foo",DataA3 "yo" []].

Espero que esto ayude!

Answer 2

No conozco una respuesta general a su pregunta. El tipo de datos es bastante artificial, y probablemente elegiría implementar un pliegue en lugar de un filtro. Aquí, sin embargo, hay algunas funciones de filtro que pueden actualizar cadenas en las cuatro posiciones. He puesto el código a través del compilador, por lo que se tipea, pero no lo he ejecutado.

type SFilter = String -> String 

-- to filter a tree, say how A2, A3, B2, and B3 should be changed 

type Filter tree = SFilter -> SFilter -> SFilter -> SFilter -> (tree -> tree) 

afilter :: Filter DataA 
bfilter :: Filter DataB 
tfilter :: Filter Tree 

tfilter a2 a3 b2 b3 = map (afilter a2 a3 b2 b3) 
afilter a2 a3 b2 b3 = fil 
    where fil (DataA1 bs) = DataA1 $ map (bfilter a2 a3 b2 b3) bs 
     fil (DataA2 s) = DataA2 (a2 s) 
     fil (DataA3 s as) = DataA3 (a3 s) (map fil as) 

bfilter a2 a3 b2 b3 = fil 
    where fil (DataB1 as) = DataB1 $ map (afilter a2 a3 b2 b3) as 
     fil (DataB2 s) = DataB2 (b2 s) 
     fil (DataB3 s bs) = DataB3 (b3 s) (map fil bs) 

Answer 3

Quiere recorrer toda la estructura de datos y cambiar algunos elementos aquí y allá. Esto generalmente se realiza mediante una función que toma la estructura de datos como parámetro y devuelve la nueva versión modificada de la estructura.

Para cada caso de entrada, esta función define cómo se verá el nuevo valor que se devuelve como .

La función básica que modifica una Tree (que es sólo una lista de valores DataA) probablemente sólo debe devolver una nueva lista de valores modificados. Si nos remitimos aquellos modificaciones de los valores a una función modifyA, la función principal modificación se ve así:

-- # function to change a |Tree| 
mutate :: Tree -> Tree 
mutate as = map mutateA as 
    -- # (The |map| function applies the |mutateA| function to every 
    -- # element of |as|, creating a list of all the return values) 

Ahora la función mutateA necesita ser definida para cambiar todas las posibles DataA valores y mejor es acompañado por una función mutateB que maneja los valores DataB.

Estas funciones se ven en los diferentes casos posibles de valores y devuelven los nuevos valores apropiados:

-- # function to change |DataA| items 
mutateA :: DataA -> DataA 
    -- # A |DataA1| is a |DataA1| with modified values 
mutateA (DataA1 bs) = DataA1 (map mutateB bs) 
    -- # A |DataA3| is a |DataA3| with modified values 
mutateA (DataA3 s as) = DataA3 s (map mutateA as) 
    -- # In the remaining case(s) the value stays the same 
mutateA d    = d 

-- # function to change |DataB| items 
mutateB :: DataB -> DataB 
mutateB (DataB1 as) = DataB1 (map mutateA as) 
mutateB (DataB3 s bs) = DataB3 s (map mutateB bs) 
    -- # Here comes a real change 
mutateB (DataB2 _) = DataB2 "foo" 

esta manera para cada elemento en el árbol de un nuevo elemento se calcula, en el que todos los DataB2 valores en cualquier parte en el árbol son reemplazados por "foo".

Es relativamente prolijo porque tiene cinco casos diferentes que contienen una lista de valores que debe recorrer, pero que no es específico de Haskell. En un idioma imperativo, normalmente tendría cinco bucles for en lugar de las cinco llamadas al map.

Tal vez podría simplificar su estructura de datos para reducir esta "sobrecarga".Este , por supuesto, depende de su caso de uso real, pero tal vez, por ejemplo, usted no necesita los casos Data2: ¿Hay una diferencia entre DataA2 "abc" y DataA3 "abc" []?

Answer 4

Es posible que desee echar un vistazo a la biblioteca multirec para trabajar con tipos de datos mutuamente recursivos. No lo he usado, pero por lo que has descrito, parece que está dirigido precisamente al tipo de problema con el que estás trabajando. Utiliza programación genérica como las otras respuestas aquí sugeridas, pero puede ahorrarle tiempo de implementarlo usted mismo.