F # PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

Estoy trabajando en las estructuras de datos puramente funcionales de Okasaki y tratando de construir implementaciones de cosas en F #. También estoy repasando los ejercicios enumerados en el libro (algunos son bastante desafiantes). Bueno, estoy atascado en el ejercicio 3.4, que pide modificar la función de combinación de WeightBiasedLeftistHeap de manera que se ejecute en una sola pasada en lugar de la implementación original de 2 pasadas.

Todavía no he podido averiguar cómo hacer esto y esperaba algunas sugerencias. Hubo otra publicación aquí en SO donde un chico lo hace en SML prácticamente insertando la función makeT. Comencé por esta ruta (en la sección 3.4. Primer intento comentada. Pero abandoné ese enfoque porque pensé que esto realmente no se estaba ejecutando en una sola pasada (todavía va hasta que llega a una hoja, luego se desenrolla y reconstruye el árbol). ¿Me equivoco al interpretar que sigue siendo una combinación de dos pasadas?

Aquí hay un enlace a mi implementación completa de WeightBiasedLeftistHeap.

Estos son mis intentos fallidos de hacer esto 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 primera pregunta es: ¿qué constituye un algoritmo de "una pasada"? Algo que naturalmente podría implementarse como un solo ciclo de arriba hacia abajo calificaría. Por el contrario, la recursividad, compilada ingenuamente, normalmente tiene dos pases, uno en el camino hacia abajo y otro en el camino de regreso. Tail recursión se puede compilar fácilmente en un bucle y, por lo general, está en lenguajes funcionales. Tail recursion modulo contras es similar, aunque menos común , optimización. Pero, incluso si su compilador no es compatible con el módulo de recursividad de cola, puede convertir fácilmente una implementación de este tipo en un bucle a mano.

Tail recurssion modulo cons es similar a la recursividad de cola ordinaria, excepto que la llamada de cola está envuelta en un constructor, que se puede asignar y completar parcialmente antes de la llamada recursiva. En este caso, querrá que las expresiones de retorno sean algo así como T (1+size(a)+size(b)+size(c),x,a,merge(b,c)). La información clave requerida aquí (como se menciona en la edición de otro subproceso SO ) es que no es necesario realizar la fusión para saber qué tan grande será el resultado y, por lo tanto, de qué lado del nuevo árbol debería continuar. Esto se debe a que el tamaño de merge(b,c) siempre será size(b)+size(c), que se puede calcular fuera de la combinación.

Tenga en cuenta que la función rank original para los montones izquierdistas ordinarios no comparte esta propiedad, por lo que no puede optimizarse de esta manera.

Básicamente, entonces, inserta las dos llamadas a makeT y también convierte las llamadas de la forma size(merge(b,c)) a size(b)+size(c).

Una vez que realiza este cambio, la función resultante es significativamente más lenta que la original, porque puede devolver la raíz del resultado antes de evaluar la combinación recursiva.

De manera similar, en un entorno concurrente que involucre bloqueos y mutación, la nueva implementación podría soportar significativamente más concurrencia adquiriendo y liberando bloqueos para cada nodo en el camino, en lugar de bloquear todo el árbol. (Por supuesto, esto solo tendría sentido para candados muy livianos).

Answer 2

No estoy exactamente seguro de haber entendido la pregunta correctamente, pero aquí está mi intento: actualmente, la operación merge realiza una llamada recursiva a merge (esa es la primera pasada) y cuando llega al final del montón (primero dos casos en match), devuelve el montón recién construido al llamador y llama a makeT un par de veces (ese es el segundo paso).

No creo que simplemente insertar mMakeT es lo que se nos pide que hagamos (si es así, simplemente agregue inline a makeT y eso se hace sin que el código sea menos legible :-)).

Sin embargo, lo que se puede hacer es modificar la función merge para usar el estilo de paso de continuación donde el "resto del trabajo" se pasa como una función a la llamada recursiva (para que no haya trabajo pendiente en la pila debe hacerse después de que se complete la primera pasada). Esto se puede hacer así:

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

No estoy completamente convencido de que esta sea la respuesta correcta: realiza una sola pasada, pero el trabajo agregado (en la continuación) significa que la pasada es dos veces más larga. Sin embargo, no veo una forma de hacerlo más simple, por lo que puede ser la respuesta correcta ...