Traversieren und Filtern eines Baumes in Haskell

Question

Ich bin ziemlich neu in Haskell (ich arbeite immer noch daran, Monaden vollständig zu verstehen). Ich habe ein Problem, bei dem ich eine baumartige Struktur habe

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

Ich möchte diesen Baum durchlaufen und einen neuen Baum mit einem Filter erstellen. Ich möchte zum Beispiel alle DataB2 im Baum in "foo" ändern.

Ich habe Beispiele für Bäume gesehen, die sich im selben Datenbereich befinden, und die Konstruktoren sind ähnlich.

In der Python-Welt würde ich einfach die Liste durchlaufen, den gewünschten Wert finden und ihn ersetzen.

In Haskell nehme ich an, dass ich in der Lage sein muss, meinen Baum zu kopieren, aber wie gehen Sie mit Listen um, die in Konstruktoren und verschiedenen Datentypen vergraben sind?

Answer 1

Hierfür können Sie eine generische Programmierung verwenden.

Eine solche generische Programmierbibliothek heißt Scrap Your Boilerplate. Ganz oben in Ihrem Modul aktivieren Sie Scrap Your Boilerplate, indem Sie schreiben:

{-# LANGUAGE DeriveDataTypeable #-}

Modul importieren Data.Generics . Dann außerdem Show auch ableiten Typeable y Data Instanzen für Ihre Datentypen.

Jetzt können Sie die gewünschte Funktion wie folgt schreiben:

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

Das ist alles, was Sie tun müssen, damit das funktioniert. Zum Beispiel, wenn Sie aufrufen toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []] lautet die Antwort [DataA1 [],DataA2 "foo",DataA3 "yo" []] .

Ich hoffe, das hilft!

Answer 2

Eine allgemeine Antwort auf Ihre Frage weiß ich nicht. Der Datentyp ist ziemlich ausgeklügelt, und ich würde wahrscheinlich eher eine Falte als einen Filter implementieren. Hier sind jedoch einige Filterfunktionen, die Zeichenketten in allen vier Positionen aktualisieren können. Ich habe den Code durch den Compiler laufen lassen, so dass er typgeprüft ist, aber ich habe ihn nicht ausgeführt.

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

Sie möchten die gesamte Datenstruktur durchlaufen und einige Elemente hier und da ändern. Dies geschieht in der Regel durch eine Funktion, die die Datenstruktur als Parameter nimmt und die neue, geänderte Version der Struktur zurückgibt.

Für jeden Fall der Eingabe definiert diese Funktion, wie der neue Wert, der zurückgegeben wird, aussehen soll aussehen soll.

Die Grundfunktion, die eine Tree (das ist nur eine Liste von DataA Werte) sollte wahrscheinlich einfach eine neue Liste mit geänderten Werten zurückgeben. Wenn wir diese Änderungen an den Werten auf eine modifyA Funktion, die wichtigste Änderung Funktion sieht wie folgt aus:

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

Jetzt ist die mutateA Funktion muss definiert werden, um alle möglichen DataA Werte, und am besten begleitet von einem mutateB Funktion, die die DataB Werte.

Diese Funktionen untersuchen die verschiedenen möglichen Fälle von Werten und geben die entsprechenden neuen Werte zurück:

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

Auf diese Weise wird für jedes Element im Baum ein neues Element berechnet, wobei alle DataB2 Werte an beliebiger Stelle im Baum werden durch "foo" ersetzt.

Es ist relativ ausführlich, weil Sie fünf verschiedene Fälle haben, die eine Liste enthalten von Werten enthält, die durchlaufen werden muss, aber das ist nicht spezifisch für Haskell. In einer imperativen Sprache würde man normalerweise fünf for-Schleifen anstelle der fünf Aufrufe an map .

Vielleicht könnten Sie Ihre Datenstruktur vereinfachen, um diesen "Overhead" zu verringern. Diese hängt natürlich von Ihrem tatsächlichen Anwendungsfall ab, aber vielleicht brauchen Sie zum Beispiel nicht die Data2 Fälle: Gibt es einen Unterschied zwischen DataA2 "abc" y DataA3 "abc" [] ?

Answer 4

Vielleicht möchten Sie einen Blick auf die multirec Bibliothek für die Arbeit mit sich gegenseitig rekursiven Datentypen. Ich habe sie nicht verwendet, aber nach dem, was Sie beschrieben haben, klingt es so, als ob sie genau auf die Art von Problem ausgerichtet ist, mit dem Sie arbeiten. Sie verwendet generische Programmierung, wie die anderen Antworten hier vorgeschlagen haben, könnte Ihnen aber die Zeit ersparen, alles selbst zu implementieren.