F # PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

Ich arbeite an Okasakis rein funktionalen Datenstrukturen und versuche, F # -Implementierungen von Dingen zu erstellen. Ich gehe auch die im Buch aufgeführten Übungen durch (einige sind ziemlich herausfordernd). Nun, ich bleibe bei Übung 3.4, in der die Zusammenführungsfunktion von WeightBiasedLeftistHeap so geändert werden muss, dass sie in einem einzigen Durchgang ausgeführt wird, im Gegensatz zur ursprünglichen Implementierung mit zwei Durchgängen.

Ich konnte noch nicht herausfinden, wie das geht, und hoffte auf einige Vorschläge. Es gab einen weiteren Beitrag hier auf SO wo ein Typ es in SML macht, indem er die makeT-Funktion ziemlich genau einfügt. Ich habe diesen Weg eingeschlagen (im kommentierten Abschnitt 3.4 Erster Versuch. Aber diesen Ansatz aufgegeben, weil ich dachte, dass dies wirklich nicht in einem einzigen Durchgang ausgeführt wird (es geht immer noch bis zum Erreichen eines Blattes, dann wird der Baum abgewickelt und neu aufgebaut). Bin ich falsch darin, das immer noch als Zusammenführung mit zwei Durchgängen zu interpretieren?

Hier ist ein Link zu meiner vollständigen Implementierung von WeightBiasedLeftistHeap.

Hier sind meine fehlgeschlagenen Versuche, dies in F # zu tun:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB + 1, x, b, a)

    // excercise 3.4 first try
    //    let rec merge3_4 l r =
    //        match l,r with
    //        | l,E -> l
    //        | E,r -> r
    //        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
    //            if lx <= rx then
    //                let right = merge3_4 lb rh
    //                let weightA = weight la
    //                let weightB = weight right
    //
    //                if weightA >= weightB then
    //                    T(weightA + weightB + 1, lx, la, right)
    //                else
    //                    T(weightA + weightB + 1, lx, right, la)
    //            else
    //                let right = merge3_4 lh rb
    //                let weightA = weight ra
    //                let weightB = weight right
    //
    //                if weightA >= weightB then 
    //                    T(weightA + weightB + 1, rx, ra, right)
    //                else
    //                    T(weightA + weightB + 1, rx, right, ra)

    // excercise 3.4 second try (fail!)
    // this doesn't work, I couldn't figure out how to do this in a single pass
    let merge3_4 l r =
        let rec merge' l r value leftChild  =
            match l,r with
            | l,E -> makeT value leftChild l
            | E,r -> makeT value leftChild r
            | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
                if lx <= rx then
                    merge' lb rh lx la   //(fun h -> makeT(lx, la, h))
                else
                    merge' lh rb rx ra   //(fun h -> makeT(rx, ra, h))

        match l, r with
        | l, E -> l
        | E, r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            let lf = fun h -> makeT(lx, la, h)
            if lx <= rx then
                merge' lb rh lx la // (fun h -> makeT(lx, la, h))
            else
                merge' lh rb rx ra // (fun h -> makeT(rx, ra, h))

    let rec merge l r =
        match l,r with
        | l,E -> l
        | E,r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            if lx <= rx then
                makeT lx la (merge lb rh)
            else
                makeT rx ra (merge lh rb)

    let insert3_4 x h =
        merge3_4 (T(1,x,E,E)) h

Answer 1

Die erste Frage lautet: Was macht einen "One-Pass" -Algorithmus aus? Etwas, das natürlich als einzelne Top-Down-Schleife implementiert werden könnte, würde sich qualifizieren. Im Gegensatz dazu hat die Rekursion - naiv kompiliert - normalerweise zwei Durchgänge, einen auf dem Weg nach unten und einen auf dem Weg zurück nach oben. Schwanzrekursion kann leicht zu einer Schleife kompiliert werden und ist normalerweise in funktionalen Sprachen verfügbar. modulo cons der Schwanzrekursion ist ähnlich, wenn auch weniger verbreitet , Optimierung. Aber selbst wenn Ihr Compiler keine Modulo-Nachteile für die Schwanzrekursion unterstützt, können Sie eine solche Implementierung einfach von Hand in eine Schleife konvertieren.

Das Modulo cons der Schwanzrekursion ähnelt der normalen Schwanzrekursion, außer dass der Schwanzaufruf in einen Konstruktor eingeschlossen ist, der vor dem rekursiven Aufruf zugewiesen und teilweise ausgefüllt werden kann. In diesem Fall möchten Sie, dass die Rückgabeausdrücke so etwas wie T (1+size(a)+size(b)+size(c),x,a,merge(b,c)) sind. Die hier erforderlichen wichtigen Erkenntnisse (wie in der Bearbeitung unter anderer SO-Thread ) bedeutet, dass Sie die Zusammenführung nicht durchführen müssen, um zu wissen, wie groß das Ergebnis sein wird und auf welcher Seite des neuen Baums es sich befinden soll. Dies liegt daran, dass die Größe des merge(b,c)s immer size(b)+size(c) ist, der außerhalb der Zusammenführung berechnet werden kann.

Beachten Sie, dass die ursprüngliche rank-Funktion für normale linke Heaps diese Eigenschaft nicht teilt und daher nicht auf diese Weise optimiert werden kann.

Im Wesentlichen inline setzen Sie dann die beiden Aufrufe von makeT und konvertieren die Aufrufe des Formulars size(merge(b,c)) in size(b)+size(c).

Sobald Sie diese Änderung vorgenommen haben, ist die resultierende Funktion erheblich verzögerter als das Original, da sie den Stamm des Ergebnisses zurückgeben kann, bevor die rekursive Zusammenführung ausgewertet wird.

In ähnlicher Weise könnte die neue Implementierung in einer gleichzeitigen Umgebung mit Sperren und Mutationen eine wesentlich höhere Parallelität unterstützen, indem Sperren für jeden Knoten auf dem Weg erfasst und freigegeben werden, anstatt den gesamten Baum zu sperren. (Dies wäre natürlich nur für sehr leichte Schlösser sinnvoll.)

Answer 2

Ich bin mir nicht ganz sicher, ob ich die Frage richtig verstanden habe, aber hier ist mein Versuch - derzeit führt die merge-Operation einen rekursiven Aufruf von merge durch (das ist der erste Durchgang) und wenn das Ende des Heaps erreicht ist (erster In zwei Fällen (match) wird der neu erstellte Heap an den Aufrufer zurückgegeben und der makeT einige Male aufgerufen (dies ist der zweite Durchgang).

Ich glaube nicht, dass wir einfach mMakeT einfügen müssen (wenn ja, fügen Sie einfach inline zu makeT hinzu, und das geschieht, ohne den Code weniger lesbar zu machen :-)).

Sie können jedoch die Funktion merge so ändern, dass der Continuation-Passing-Stil verwendet wird, bei dem der "Rest der Arbeit" als Funktion an den rekursiven Aufruf übergeben wird (sodass keine Arbeit am Stapel ansteht nach Abschluss des ersten Durchgangs). Dies kann folgendermaßen geschehen:

let rec merge' l r cont =
    match l,r with
    | l,E -> cont l // Return result by calling  the continuation
    | E,r -> cont r // (same here)
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
        if lx <= rx then
            // Perform recursive call and give it 'makeT' as a continuation
            merge' lb rh (makeT lx la)
        else
            // (same here)
            merge' lh rb (makeT rx ra)

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed
let merge l r = merge' l r id

Ich bin nicht ganz davon überzeugt, dass dies die richtige Antwort ist - es wird nur ein einziger Durchgang ausgeführt, aber die aggregierte Arbeit (in der Fortsetzung) bedeutet, dass der Durchgang zweimal länger ist. Ich sehe jedoch keinen Weg, dies zu vereinfachen, daher ist es möglicherweise die richtige Antwort ...