F # PurelyFunctionalDataStructures WeightBiasLeftistHeap ex 3.4

Question

Sto lavorando alle strutture dati puramente funzionali di Okasaki e sto cercando di creare implementazioni F # delle cose. Eseguo anche gli esercizi elencati nel libro (alcuni sono piuttosto impegnativi). Bene, sono bloccato sull'esercizio 3.4 che richiede la modifica della funzione di unione di WeightBiasLeftistHeap in modo tale che venga eseguito in un singolo passaggio rispetto all'implementazione originale a 2 passaggi.

Non sono ancora riuscito a capire come farlo e speravo in alcuni suggerimenti. C'era un altro post qui su SO dove un ragazzo lo fa in SML praticamente incorporando la funzione makeT. Ho iniziato seguendo questa strada (nella sezione commentata 3.4 Primo tentativo. Ma ho abbandonato quell'approccio perché pensavo che questo non si eseguisse davvero in un unico passaggio (va ancora fino a raggiungere una foglia, quindi si srotola e ricostruisce l'albero). Ho sbagliato a interpretarlo come se fosse ancora una fusione in due passaggi?

Ecco un link alla mia implementazione completa di WeightBiasLeftistHeap.

Ecco i miei tentativi falliti di farlo in F #:

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

La prima domanda è: cosa costituisce un algoritmo "one-pass"? Qualcosa che potrebbe naturalmente essere implementato come un unico ciclo dall'alto verso il basso si qualificherebbe. Al contrario, la ricorsione - compilata in modo ingenuo - normalmente ha due passaggi, uno verso il basso e uno verso l'alto. La ricorsione in coda può essere facilmente compilata in un ciclo e di solito è in linguaggi funzionali. Ricorsione in coda modulo cons è simile, anche se meno comune , ottimizzazione. Ma, anche se il tuo compilatore non supporta la ricorsione in coda modulo contro, puoi facilmente convertire manualmente tale implementazione in un ciclo.

La ricorsione in coda modulo contro è simile alla normale ricorsione in coda, tranne per il fatto che la chiamata di coda è racchiusa in un costruttore, che può essere allocato e parzialmente riempito prima della chiamata ricorsiva. In questo caso, vorresti che le espressioni di ritorno fossero qualcosa come T (1+size(a)+size(b)+size(c),x,a,merge(b,c)). Le informazioni chiave richieste qui (come menzionato nella modifica su altro thread SO ) è che non è necessario eseguire l'unione per sapere quanto sarà grande il risultato e quindi su quale lato del nuovo albero dovrebbe andare. Questo perché la dimensione di merge(b,c) sarà sempre size(b)+size(c), che può essere calcolata al di fuori dell'unione.

Notare che la funzione originale rank per i normali heap di sinistra non condivide questa proprietà e quindi non può essere ottimizzata in questo modo.

Essenzialmente, quindi, inline le due chiamate a makeT e anche converte le chiamate del modulo size(merge(b,c)) in size(b)+size(c).

Una volta apportata questa modifica, la funzione risultante è notevolmente più pigra dell'originale, perché può restituire la radice del risultato prima di valutare l'unione ricorsiva.

Allo stesso modo, in un ambiente simultaneo che coinvolge blocchi e mutazioni, la nuova implementazione potrebbe supportare una concorrenza significativamente maggiore acquisendo e rilasciando blocchi per ogni nodo lungo il percorso, piuttosto che bloccare l'intero albero. (Ovviamente, questo avrebbe senso solo per serrature molto leggere.)

Answer 2

Non sono esattamente sicuro di aver capito correttamente la domanda, ma ecco il mio tentativo: attualmente, l'operazione merge esegue una chiamata ricorsiva a merge (questo è il primo passaggio) e quando raggiunge la fine dell'heap (primo due casi in match), restituisce l'heap appena costruito al chiamante e chiama makeT un paio di volte (questo è il secondo passaggio).

Non penso che semplicemente inlining mMakeT sia ciò che ci viene chiesto di fare (se sì, aggiungi semplicemente inline a makeT e questo viene fatto senza rendere il codice meno leggibile :-)).

Ciò che si può fare, tuttavia, è modificare la funzione merge per utilizzare lo stile di continuazione del passaggio in cui il "resto del lavoro" viene passato come funzione alla chiamata ricorsiva (quindi non ci sono lavori in sospeso sullo stack da eseguire dopo il completamento del primo passaggio). Questo può essere fatto in questo modo:

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

Non sono del tutto convinto che questa sia la risposta giusta: esegue un solo passaggio, ma il lavoro aggregato (nel seguito) significa che il passaggio è due volte più lungo. Tuttavia, non vedo un modo per renderlo più semplice, quindi potrebbe essere la risposta giusta ...