F # PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

Je travaille sur les structures de données de Okasaki Purement fonctionnels et essayer de construire F implémentations # de choses. Je vais aussi à travers les exercices énumérés dans le livre (certains sont assez difficile). Eh bien, je suis bloqué sur l'exercice 3.4 qui appelle à modifier la fonction de fusion de la WeightBiasedLeftistHeap telle qu'elle exécute en une seule passe, par opposition à la mise en œuvre passe 2 d'origine.

Je n'ai pas été en mesure de savoir comment faire encore et espérait quelques suggestions. Il y avait une autre ici sur le SO après où un gars qu'il fait dans PMG par à peu près inline la fonction mAKET. J'ai commencé aller dans cette voie (dans la section 3.4 a commenté premier essai. Mais abandonné cette approche parce que je pensais que ce vraiment ne procédait pas en un seul passage (il va encore « jusqu'à atteindre une feuille puis dénouements et reconstruit l'arbre). Ai-je tort dans l'interprétation que comme étant encore deux passe fusion?

Voici une un lien vers ma mise en œuvre complète de WeightBiasedLeftistHeap.

Voici mes tentatives infructueuses de le faire en 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 première question est: ce qui constitue un algorithme "one-pass"? Quelque chose qui pourrait naturellement être mis en œuvre comme une boucle descendante unique serait admissible. En revanche, récursivité - compilé naïvement - a normalement deux passes, l'un sur le chemin vers le bas et un sur le dos de chemin. récursion Queue peuvent être facilement compilés dans une boucle, et est habituellement dans les langages fonctionnels. Tail récursion modulo contre est un semblable, quoique moins fréquente , l'optimisation. Mais, même si votre compilateur ne supporte pas les inconvénients de la queue modulo récursive, vous pouvez facilement convertir une telle mise en œuvre en boucle à la main.

cons de récursion Tail modulo est similaire à la récursion arrière ordinaire, sauf que l'appel de queue est enveloppé dans un constructeur, qui peut être allouée et partiellement rempli avant l'appel récursif. Dans ce cas, vous voulez que les expressions de retour à quelque chose comme T (1+size(a)+size(b)+size(c),x,a,merge(b,c)). L'idée clé nécessaire ici (comme mentionné dans l'édition du autre thread SO ) est que vous n'avez pas besoin d'effectuer la fusion pour savoir la taille du résultat, il va être, et donc de quel côté du nouvel arbre il devrait continuer. En effet, la taille de merge(b,c) sera toujours size(b)+size(c), qui peut être calculée en dehors de la fusion.

Notez que la fonction rank original pour des tas gauchistes ordinaires ne pas partager cette propriété, et ne peut donc pas être optimisé de cette façon.

Pour l'essentiel, alors, vous en ligne les deux appels à MAKET et aussi convertir les appels de la forme size(merge(b,c)) à size(b)+size(c).

Une fois que vous effectuez cette modification, la fonction résultante est nettement plus paresseux que l'original, car il peut retourner la racine du résultat avant évaluer la fusion récursive.

De même, dans un environnement impliquant en même temps serrures et mutation, la nouvelle mise en œuvre pourrait soutenir beaucoup plus en concurrence l'acquisition et la libération des verrous pour chaque nœud le long du chemin, plutôt que de bloquer l'arbre entier. (Bien sûr, cela serait logique pour les serrures très légers.)

Answer 2

Je ne suis pas sûr si je comprends bien la question, mais voici ma tentative - actuellement, les exécute des opérations de merge un appel récursif à merge (qui est la première passe) et quand il arrive à la fin du tas (premier deux cas en match), il retourne le dos du tas nouvellement construit à l'appelant et appelle makeT deux ou trois fois (c'est la deuxième passe).

Je ne pense pas que le simple fait inline mMakeT est ce que l'on nous demande de le faire. (Si oui, il suffit d'ajouter inline à makeT et qui est fait sans le code moins lisible: -))

Que peut-on faire, cependant, est de modifier la fonction merge à l'utilisation de passage de style de continuation où le « reste du travail » est passé en fonction à l'appel récursif (donc il n'y a pas en attente de travail sur la pile à faire après la première finalise passe). Cela peut se faire comme ceci:

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

Je ne suis pas pleinement convaincu que c'est la bonne réponse - il réalise juste un seul passage, mais le travail agrégé (dans la suite) signifie que le passage est deux fois plus longue. Cependant, je ne vois pas un moyen de faire de ce simple, il peut donc être la bonne réponse ...