Wie entfernt 'Abholzung' 'Bäume' aus einem Programm?

Ich denke, ich verstehe, wie die Entwaldung eine Liste gleichzeitig verbraucht und produziert (von einer Fold- und einer Unfold- Funktion - siehe diese gute Antwort auf CodeReview hier ), aber als ich das mit dem Wikipedia-Eintrag über die Technik verglich, von der es sprach, "Entfernen" Bäume 'aus einem Programm.

Ich verstehe, wie ein Programm in einen syntaktischen Analysebaum zerlegt werden kann (stimmt das?), Aber was bedeutet diese Verwendung der Entwaldung für eine Art Vereinfachung von Programmen (oder?)? Und wie würde ich das mit meinem Code machen?

Yatima2975 scheint Ihre ersten beiden Fragen beantwortet zu haben, ich werde versuchen, die dritte zu beantworten. Um dies zu tun, werde ich einen unrealistisch einfachen Fall behandeln, aber ich bin sicher, dass Sie sich etwas Realistischeres vorstellen können.

$n$

type Tree = Leaf | Node Tree Tree

$n$

full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

Und die Tiefe eines Baumes wird von berechnet

depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

$\mathrm{depth}\ (\mathrm{full}\ n)$$n$$\mathrm{full}$$\mathrm{depth}$$\mathrm{depth}\ (\mathrm{full}\ n)$$\mathrm{full\_depth}$

full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

Dies vermeidet die Speicherzuordnung des gesamten Baums und die Notwendigkeit, einen Musterabgleich durchzuführen, was die Leistung erheblich verbessert. Darüber hinaus, wenn Sie die Optimierung hinzufügen

max t t --> t

Dann haben Sie eine exponentielle Zeitprozedur in eine lineare ... Es wäre cool, wenn es eine zusätzliche Optimierung gäbe, die erkennt, dass die Identität für ganze Zahlen ist, aber ich bin mir nicht sicher, ob dies der Optimierung wird in der Praxis eingesetzt.$\mathrm{full\_depth}$

Der einzige Mainstream-Compiler, der die automatische Entwaldung durchführt, ist GHC. Wenn ich mich recht entsinne, wird dies nur beim Erstellen von integrierten Funktionen durchgeführt (aus technischen Gründen).

Erstens sind Listen eine Art Bäume. Wenn wir eine Liste als verknüpfte Liste darstellen , handelt es sich nur um einen Baum, dessen Knoten entweder 1 oder 0 Nachkommen haben.

Durchsuchen von Bäumen ist nur eine Verwendung von Bäumen als Datenstruktur. Bäume haben viele verschiedene Anwendungen in der Informatik, einschließlich Sortieren, Implementieren von Karten, assoziativen Arrays usw.

Im Allgemeinen sind Listen, Bäume usw. rekursive Datenstrukturen: Jeder Knoten enthält einige Informationen und eine weitere Instanz derselben Datenstruktur. Das Falten ist eine Operation über alle derartigen Strukturen, die Knoten rekursiv in Werte "von unten nach oben" umwandelt. Das Entfalten ist der umgekehrte Vorgang, es wandelt Werte in Knoten "von oben nach unten" um.

Für eine gegebene Datenstruktur können wir ihre Falt- und Entfaltungsfunktionen mechanisch konstruieren.

Nehmen wir als Beispiel Listen. (Ich werde Haskell für die Beispiele verwenden, da es geschrieben ist und seine Syntax sehr klar ist.) Liste ist entweder ein Ende oder ein Wert und ein "Ende".

data List a = Nil | Cons a (List a)

Stellen wir uns jetzt vor, wir falten eine Liste. Bei jedem Schritt muss der aktuelle Knoten gefaltet werden, und die rekursiven Unterknoten wurden bereits gefaltet. Wir können diesen Zustand als darstellen

data ListF a r = NilF | ConsF a r

wobei rder Zwischenwert konstruiert , indem die Unterliste zu falten. Dies ermöglicht es uns, eine Faltungsfunktion über Listen auszudrücken:

foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil            = f NilF
foldList f (Cons x xs)    = f (ConsF x (foldList f xs))

Wir konvertieren Listin, ListFindem wir ihre Unterliste rekursiv umklappen und dann eine in definierte Funktion verwenden ListF. Wenn Sie darüber nachdenken, ist dies nur eine weitere Darstellung von Standard foldr:

foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
  where
    g NilF          = z
    g (ConsF x r)   = f x r

Wir können unfoldListauf die gleiche Weise konstruieren :

unfoldList :: (r -> ListF a r) -> r -> List a
unfoldList f r = case f r of
                  NilF        -> Nil
                  ConsF x r'  -> Cons x (unfoldList f r')

Wieder ist es nur eine andere Darstellung von unfoldr:

unfoldr :: (r -> Maybe (a, r)) -> r -> [a]

(Beachten Sie, dass Maybe (a, r)isomorph zu ist ListF a r.)

Und wir können auch eine Entwaldungsfunktion konstruieren:

deforest :: (ListF a r -> r) -> (s -> ListF a s) -> s -> r
deforest f u s = f (map (deforest f u) (u s))
  where
    map h NilF        = NilF
    map h (ConsF x r) = ConsF x (h r)

Es lässt einfach das Zwischenprodukt weg Listund verschmilzt die Falt- und Entfaltungsfunktionen miteinander.

Das gleiche Verfahren kann auf jede rekursive Datenstruktur angewendet werden. Beispiel: Ein Baum, dessen Knoten 0, 1, 2 oder Nachkommen mit Werten auf 1- oder 0-Verzweigungsknoten haben können:

data Tree a = Bin (Tree a) (Tree a) | Un a (Tree a) | Leaf a

data TreeF a r = BinF r r | UnF a r | LeafF a

treeFold :: (TreeF a r -> r) -> Tree a -> r
treeFold f (Leaf x)       = f (LeafF x)
treeFold f (Un x r)       = f (UnF x (treeFold f r))
treeFold f (Bin r1 r2)    = f (BinF (treeFold f r1) (treeFold f r2))

treeUnfold :: (r -> TreeF a r) -> r -> Tree a
treeUnfold f r = case f r of
                  LeafF x         -> Leaf x
                  UnF x r         -> Un x (treeUnfold f r)
                  BinF r1 r2      -> Bin (treeUnfold f r1) (treeUnfold f r2)

Natürlich können wir deforestTreegenauso mechanisch wie bisher erstellen .

(Normalerweise würden wir treeFoldbequemer ausdrücken als:

treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r

)

Ich werde die Details weglassen, ich hoffe, das Muster ist offensichtlich.

Siehe auch:

• Katamorphismus
• Anamorphismus
• Hylomorphismus

Es ist etwas verwirrend, aber die Entwaldung wird (zur Kompilierungszeit) angewendet, um Zwischenbäume zu entfernen, die (zur Laufzeit) erstellt würden. Bei der Abholzung von Wäldern werden keine Teile des abstrakten Syntaxbaums gehackt (das ist die Eliminierung toter Zweige :-)

Eine andere Sache , die Sie weg geworfen haben kann , ist , dass die Listen sind Bäume, nur sehr unausgewogen diejenigen!