pattern - Atravesando y filtrando un árbol en haskell

pattern matching haskell

Question

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

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 poder 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, simplemente atravesaría la lista, coincidiría con lo que fuera necesario y reemplazaría 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

Desea atravesar toda la estructura de datos y cambiar algunos elementos aquí y allá. Esto generalmente lo hace una función que toma la estructura de datos como un parámetro y devuelve la nueva versión modificada de la estructura.

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

La función básica que modifica un Tree (que es solo una lista de valores de datos) probablemente debería devolver una nueva lista de valores modificados. Si diferimos esas modificaciones de los valores a una función modifyA , la función de modificación principal 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 definirse para cambiar todos los valores posibles de DataA , y lo mejor es que esté acompañada de una función mutateB que maneja los valores de DataB .

Estas funciones miran 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"

De esta forma, para cada elemento del árbol se calcula un elemento nuevo, donde todos los valores de DataB2 en cualquier parte del árbol se reemplazan por "foo".

Es relativamente detallado porque tiene cinco casos diferentes que contienen una lista de valores que debe ser recorrida, pero eso no es específico de Haskell. En un lenguaje imperativo, normalmente tendrías cinco bucles for en lugar de las cinco llamadas al map .

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

Answer 2

Es posible que desee echar un vistazo a la biblioteca multirreglo 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.

Answer 3

No conozco una respuesta general a tu 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 4

Puede usar programación genérica para esto.

Una de esas bibliotecas genéricas de programación se llama Scrap Your Boilerplate. En la parte superior de su módulo, habilite Scrap Your Boilerplate escribiendo:

{-# LANGUAGE DeriveDataTypeable #-}

Importar el módulo Data.Generics . Luego, además de Show , también deriva las instancias Typeable y Data para sus tipos de datos.

Ahora puedes escribir la función que solicitaste 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 que esto funcione. Por ejemplo, cuando llama a toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []] , la respuesta es [DataA1 [],DataA2 "foo",DataA3 "yo" []] .

¡Espero que esto ayude!