Haskell: Flachen binären Baum

Question

Ich dachte über die Verflachung eines Binärbaums auf eine Liste, für die spätere Verarbeitung.

Ich dachte zuerst an (++), um die linken und rechten Zweige zu verbinden, aber dann dachte im schlimmsten Fall, dass O(n^2) Zeit dauern würde.

Ich dachte dann, die Liste rückwärts zu bauen, mit (:) an die Front in linearer Zeit anhängen. Allerdings dachte ich, wenn ich diese Liste an eine faltenähnliche Funktion sende, muss sie warten, bis der gesamte Baum durchlaufen wurde, bevor sie beginnen kann zu falten, und kann daher list fusion nicht verwenden.

Ich kam dann mit den following up:

data Tree a = Node a (Tree a) (Tree a) | Tip 

flatten :: Tree a -> [a] 
flatten x = (flatten' x) [] 

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

main = 
    putStrLn $ show $ flatten $ 
    (Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip)) 

Wird diese Arbeit in O(n) Zeit nehmen „Stapelspeicher“ nicht mehr als proportional zu der größten Tiefe des Baumes und kann es mit einem raubend fusioniert werden Funktion (dh Zwischenliste eliminiert)? Ist das der "richtige" Weg, um einen Baum zu plätten?

Answer 1

Ich weiß nicht viel über Fusion, aber ich denke, dass rekursive Funktionen im Allgemeinen nicht verschmolzen werden können. Aber denken Sie daran, dass Zwischenlisten, wenn Sie sich mit Listen in Haskell beschäftigen, normalerweise nicht als Ganzes auf einmal existieren - Sie werden den Anfang kennen und das Ende nicht berechnet haben, und später werden Sie den Anfang wegwerfen und wissen das Ende (in so vielen Schritten wie es Elemente der Liste gibt). Dies ist keine Fusion, dies ist eher "Stream brainedness" und bedeutet, dass die Platzanforderungen besser sind, wenn die Ausgabe inkrementell verbraucht wird.

Wie auch immer, ja, ich denke, das ist der beste Weg, um einen Baum zu plätten. Wenn die Ausgabe eines Algorithmus eine Liste ist, aber ansonsten die Liste nicht untersucht wird und eine Verkettung stattfindet, sind difference lists (DList s) normalerweise der beste Weg. Sie stellen eine Liste als eine "Prepender-Funktion" dar, die eine Traversierung beim Anhängen überflüssig macht, da das Anhängen nur eine Funktionszusammensetzung ist.

type DList a = [a] -> [a] 

fromList :: [a] -> DList a 
fromList xs = \l -> xs ++ l 

append :: DList a -> DList a -> DList a 
append xs ys = xs . ys 

toList :: DList a -> [a] 
toList xs = xs [] 

Das sind die wesentlichen Elemente der Implementierung, der Rest kann daraus abgeleitet werden. Die naive Abflachung Algorithmus in DList s ist:

flatten :: Tree a -> DList a 
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right 
flatten Tip = fromList [] 

Lassen Sie sich ein wenig Expansion tun. Beginnen Sie mit der zweiten Gleichung:

flatten Tip = fromList [] 
      = \l -> [] ++ l 
      = \l -> l 
flatten Tip l = l 

Sehen Sie, wo das hinführt? Nun ist die erste Gleichung:

flatten (Node x left right) 
    = flatten left `append` fromList [x] `append` flatten right 
    = flatten left . fromList [x] . flatten right 
    = flatten left . (\l -> [x] ++ l) . flatten right 
    = flatten left . (x:) . flatten right 
flatten (Node x) left right l 
    = (flatten left . (x:) . flatten right) l 
    = flatten left ((x:) (flatten right l)) 
    = flatten left (x : flatten right l) 

die zeigt, wie die DList Formulierung auf Ihre Funktion ist gleich!

flatten' :: Tree a -> [a] -> [a] 
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l))) 
flatten' Tip l = l 

Ich habe keinen Beweis dafür, warum DList ist besser als andere Ansätze (und es hängt letztlich davon ab, wie Sie Ihren Ausgang verbrauchen), aber DList ist der üblicher Weg, dies effizient zu tun, und das ist was hast du getan.

Answer 2

flatten' ist Tail rekursiv, so sollte es keinen Stapelplatz nehmen. Es wird jedoch auf der linken Seite des Baumes gehen und einen Haufen Dinger in den Haufen spucken.Wenn Sie es auf Ihrem Beispiel Baum aufrufen, und reduzieren sie auf WHNF, sollten Sie etwas, das wie folgt aussieht:

: 
/\ 
1 flatten' Tip : 
      /\ 
       2 flatten' (Node 4) [] 
         / \ 
         (Node 3) Tip 
         /  \ 
         Tip  Tip 

Der Algorithmus ist O(N), aber es hat die Tip s sowie die Node s zu untersuchen .

Dies scheint der effizienteste Weg zu sein, um Ihren Baum in Ordnung zu bringen. Das Modul Data.Tree hat eine flatten Funktion here, die fast dasselbe tut, außer dass es eine Vorbestellung bevorzugt.

Update:

In einem Diagramm Reduzierungs-Engine, die flatten in main eine grafische Darstellung wie folgt erzeugen:

   @ 
      /\ 
      @ [] 
      /\ 
     / \ 
     / \ 
     flatten' Node 2 
       / \ 
      / \ 
      /  \ 
      Node 1 Node 4 
     / \ / \ 
      Tip Tip/ \ 
       /  \ 
       Node 3  Tip 
       / \ 
       Tip Tip 

Um dies zu WHNF zu reduzieren, wird die Graphreduktions Motor entrollen die Wirbelsäule, schieben Sie die [] und die Node 2 auf den Stapel. Es wird dann rufen Sie die flatten'-Funktion, die die Grafik wird dieses umschreiben:

    @ 
       /\ 
      / \ 
      / \ 
      @  : 
      /\ /\ 
     / \ 2 \ 
     / \  \ 
     flatten' Node 1 \ 
       / \  \ 
       Tip Tip @ 
         /\ 
         @ [] 
         /\ 
        / \ 
        / \ 
        flatten' Node 4 
          / \ 
         / \ 
         /  \ 
         Node 3  Tip 
        / \ 
         Tip Tip 

Und wird die beiden Argumente vom Stapel Pop. Der Wurzelknoten befindet sich immer noch nicht in WHNF, daher wird die Graph-Verkleinerungs-Engine den Rücken abrollen und die 2:... und die Node 1 auf den Stapel schieben. Es wird dann rufen Sie die flatten'-Funktion, die die Grafik wird dieses umschreiben:

    @ 
       /\ 
      / \ 
      / \ 
      @  : 
      /\ /\ 
     / \ 1 \ 
     / \  \ 
     flatten' Tip  @ 
         /\ 
        / \ 
        / : 
        @ /\ 
        /\ 2 \ 
       /Tip  @ 
       /  /\ 
       flatten'  @ [] 
          /\ 
         / \ 
         / \ 
         flatten' Node 4 
           / \ 
          / \ 
          /  \ 
          Node 3  Tip 
         / \ 
          Tip Tip 

Und wird die beiden Argumente vom Stapel Pop. Der Wurzelknoten ist immer noch nicht in WHNF, so wird die Grafik-Reduktions-Engine die Wirbelsäule ausrollen, die 1:... und die Tip auf den Stapel schieben. Es wird dann rufen Sie die flatten'-Funktion, die die Grafik wird dieses umschreiben:

    : 
       /\ 
       1 \ 
        \ 
        @ 
        /\ 
       / \ 
       / : 
       @ /\ 
       /\ 2 \ 
      /Tip  @ 
      /  /\ 
      flatten'  @ [] 
         /\ 
        / \ 
        / \ 
        flatten' Node 4 
          / \ 
         / \ 
         /  \ 
         Node 3  Tip 
        / \ 
         Tip Tip 

Und wird die beiden Argumente vom Stapel Pop. Wir befinden uns jetzt in WHNF, nachdem wir maximal zwei Stack-Einträge verbraucht haben (unter der Annahme, dass die Tree-Knoten keine Thunks waren, die zusätzlichen Stack-Speicherplatz zum Auswerten benötigten).

Also, flatten'ist Tail-rekursiv. Es ersetzt sich selbst, ohne zusätzliche verschachtelte Redexes auswerten zu müssen. Die zweite flatten' bleibt ein Thunk im Heap, nicht der Stapel.