Attraversare e filtrare un albero in haskell

Question

Sono abbastanza nuovo per Haskell (che sta ancora lavorando per capire completamente le monadi). Ho un problema in cui ho un albero come la struttura

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 

Quello che vorrei fare è essere in grado di attraversare questo e generare un nuovo albero con un filtro. Ad esempio, potrei voler cambiare tutto il DataB2 nell'albero in "foo".

Ho visto esempi di albero quando si trovano nella stessa sezione di dati e i costruttori sono simili.

Nel mondo python, vorrei solo attraversare la lista, corrispondere a qualsiasi cosa mi servisse e sostituire il valore.

In Haskell immagino di dover essere in grado di copiare il mio albero, ma come gestisci le liste sepolte nei costruttori e nei diversi tipi di dati?

Answer 1

È possibile utilizzare una programmazione generica per questo.

Una tale libreria di programmazione generica si chiama Scrap Your Boilerplate. Nella parte superiore del modulo, abilitare Scrap tuo Boilerplate scrivendo:

{-# LANGUAGE DeriveDataTypeable #-} 

modulo di importazione Data.Generics. Quindi, oltre allo Show, derivano anche le istanze Typeable e per i tipi di dati.

Ora è possibile scrivere la funzione che avete richiesto in questo modo:

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

Questo è tutto quello che dovete fare per fare questo lavoro. Ad esempio, quando si chiama toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []], la risposta è [DataA1 [],DataA2 "foo",DataA3 "yo" []].

Spero che questo aiuti!

Answer 2

Non conosco una risposta generale alla tua domanda. Il tipo di dati è abbastanza elaborato e probabilmente sceglierei di implementare una piega piuttosto che un filtro. Qui, tuttavia, ci sono alcune funzioni di filtro che possono aggiornare le stringhe in tutte e quattro le posizioni. Ho inserito il codice attraverso il compilatore, in modo che corrisponda alla tipografia, ma non l'ho eseguito.

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

Si desidera attraversare l'intera struttura dati e modificare alcuni elementi qua e là. Questo di solito è fatto da una funzione che assume la struttura dati come parametro e restituisce la nuova versione modificata della struttura.

Per ogni caso di input, questa funzione definisce il modo in cui il nuovo valore che viene restituito dovrebbe apparire come .

La funzione di base che modifica uno Tree (che è solo un elenco di valori DataA) probabilmente dovrebbe solo restituire un nuovo elenco di valori modificati. Se rimandiamo quei modifiche dei valori da una funzione modifyA, la funzione principale di modifica appare così:

-- # 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) 

Ora la funzione mutateA deve essere definito per cambiare tutti i possibili DataA valori, e meglio è accompagnato da una funzione mutateB che gestisce i valori DataB.

Queste funzioni guardano i diversi casi possibili di valori e restituiscono i appropriate nuovi valori:

-- # 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" 

In questo modo per ogni elemento nella struttura di un nuovo elemento viene calcolato, dove tutti i DataB2 valori ovunque nell'albero sono sostituiti da "pippo".

È relativamente dettagliato perché si hanno cinque casi diversi che contengono un elenco di valori che devono essere attraversati, ma che non è specifico di Haskell. In una lingua imperativa si dovrebbero avere in genere cinque cicli in sostituzione delle cinque chiamate a map.

Forse potresti semplificare la struttura dei dati per ridurre questo "overhead".Questo dipende ovviamente dal tuo caso d'uso effettivo, ma forse, ad esempio, non hai bisogno dei casi Data2 C'è una differenza tra DataA2 "abc" e DataA3 "abc" []?

Answer 4

Si consiglia di dare un'occhiata alla libreria multirec per lavorare con tipi di dati reciprocamente ricorsivi. Non l'ho usato, ma da quello che hai descritto sembra che sia finalizzato proprio al tipo di problema con cui stai lavorando. Utilizza una programmazione generica come suggerito dalle altre risposte, ma potrebbe farti risparmiare tempo per implementare tutto da solo.