F# PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

Eu estou trabalhando em Okasaki Puramente Funcional, Estruturas de Dados e tentando construir F# implementações das coisas.Eu também estou indo através de exercícios listados no livro (alguns são muito difíceis).Bem, eu estou preso no exercício 3.4 o qual as chamadas para modificar a função merge do WeightBiasedLeftistHeap de tal forma que ele seja executado em uma única passagem, como oposição ao original em 2 passos de implementação.

Eu não tenho sido capaz de descobrir como fazer isso ainda, e estava esperando para algumas sugestões.Houve outro post aqui sobre ISSO onde um cara faz isso em SML por praticamente inlining a makeT função.Eu comecei a ir esta rota (no comentou seção 3.4 Primeira tentativa.Mas abandonou essa abordagem porque eu pensava que isso não era realmente executar em uma única passagem (ele ainda vai 'até chegar a uma folha em seguida, desenrola e reconstrói a árvore).Estou errado na interpretação de que como ainda sendo uma de duas passagens em série?

Aqui está um link para o meu implementação completa de WeightBiasedLeftistHeap.

Aqui estão as minhas tentativas de fazer isso em 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

A primeira pergunta é:o que constitui uma "passagem de um" algoritmo?Algo que poderia, naturalmente, ser implementado como um único top-down ciclo seria de se qualificar.Em contraste, a recursividade--compilado ingenuamente, normalmente tem duas passagens, uma no caminho para baixo e um no caminho de volta para cima. Recursão pode ser facilmente compilados em um loop, e, geralmente, está em uma linguagem funcional. Recursão módulo contras é um semelhante, embora menos comum, a otimização.Mas, mesmo se o seu compilador não suporta recursão módulo contras, você pode facilmente converter como uma implementação em um loop com a mão.

Recursão módulo contras é semelhante ao normal com recursão, exceto que a chamada de cauda é envolto em um construtor, que pode ser atribuída, parcialmente preenchidos antes da chamada recursiva.Neste caso, você vai querer o retorno expressões para ser algo como T (1+size(a)+size(b)+size(c),x,a,merge(b,c)).Sobre a ideia-chave é necessário aqui (como mencionado na edição no outros, de MODO thread) é que você não precisa executar a impressão em série para saber quão grande é o resultado vai ser, e, portanto, de que lado da nova árvore deve ir sobre.Isso porque o tamanho do merge(b,c) sempre será size(b)+size(c), que pode ser calculado fora de série.

Observe que o original rank função para um processo de esquerda pilhas não não compartilhar esta propriedade, e, portanto, não pode ser optimizada desta forma.

Essencialmente, em seguida, você inline duas chamadas para makeT e também converter as chamadas do formulário size(merge(b,c)) para size(b)+size(c).

Depois de efectuar esta alteração, o resultado da função é significativamente mais preguiçosos do que o original, porque ele pode retornar a raiz do resultado antes de avaliação recursiva direta.

Da mesma forma, em simultâneo ambiente envolvendo bloqueios e mutação, a nova implementação poderia apoiar significativamente mais concorrência pela aquisição e liberação de bloqueios para cada nó ao longo do caminho, em vez de bloquear toda a árvore.(É claro, isto só faz sentido para muito leve travas.)

Answer 2

Não tenho certeza se entendi a pergunta corretamente, mas aqui está minha tentativa - atualmente, a operação merge realiza uma chamada recursiva para merge (que é a primeira passagem) e quando atinge o final da pilha (primeiro dois casos em match), ele retorna o heap recém-construído de volta ao chamador e chama makeT algumas vezes (essa é a segunda passagem).

Não acho que simplesmente embutir mMakeT seja o que devemos fazer (se sim, basta adicionar inline a makeT e isso é feito sem tornar o código menos legível :-)).

O que pode ser feito, entretanto, é modificar a função merge para usar o estilo de passagem de continuação onde o "resto do trabalho" é passado como uma função para a chamada recursiva (para que não haja trabalho pendente na pilha a ser feito após a conclusão da primeira passagem). Isso pode ser feito assim:

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

Não estou totalmente convencido de que esta seja a resposta certa - ele executa apenas uma única passagem, mas o trabalho agregado (na continuação) significa que a passagem é duas vezes mais longa. No entanto, não vejo uma maneira de tornar isso mais simples, então pode ser a resposta certa ...