F # PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Question

Я работаю над чисто функциональными структурами данных Окасаки и пытаюсь построить реализацию F # вещей. Я также выполняю упражнения, перечисленные в книге (некоторые довольно сложные). Что ж, я застрял в упражнении 3.4, которое вызывает изменение функции слияния WeightBiasedLeftistHeap таким образом, чтобы она выполнялась за один проход, в отличие от исходной реализации с двумя проходами.

Я пока не смог понять, как это сделать, и надеялся на некоторые предложения. На SO была еще одна запись , где парень делает это в SML, в значительной степени вставляя функцию makeT. Я начал идти по этому пути (в прокомментированном разделе 3.4 «Первая попытка». Но отказался от этого подхода, потому что думал, что он действительно не выполняется за один проход (он все еще идет «до достижения листа, затем раскручивает и восстанавливает дерево). Я ошибаюсь, интерпретируя это как слияние в два прохода?

Вот ссылка на мою полную реализацию WeightBiasedLeftistHeap.

Вот мои неудачные попытки сделать это в 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

Первый вопрос: что представляет собой «однопроходный» алгоритм? Кое-что, что может быть естественным образом реализовано в виде единого нисходящего цикла, подойдет. Напротив, рекурсия - составленная наивно - обычно имеет два прохода, один на пути вниз и один на пути назад. Хвостовая рекурсия может быть легко скомпилирована в цикл, как правило, на функциональных языках. Хвостовая рекурсия по модулю минусов - аналогичная, хотя и менее распространенная, оптимизация. Но даже если ваш компилятор не поддерживает функции хвостовой рекурсии по модулю, вы можете легко преобразовать такую ​​реализацию в цикл вручную.

Минус хвостовой рекурсии по модулю аналогичен обычной хвостовой рекурсии, за исключением того, что хвостовой вызов заключен в конструкторе, который может быть выделен и частично заполнен перед рекурсивным вызовом. В этом случае вы хотели бы, чтобы возвращаемые выражения были чем-то вроде T (1+size(a)+size(b)+size(c),x,a,merge(b,c)). Ключевое понимание, требуемое здесь (как упомянуто в редактировании в другом SO-потоке ), заключается в том, что вам не нужно выполнять слияние, чтобы знать, насколько большим будет результат, и, следовательно, с какой нового дерева это должно продолжаться. Это связано с тем, что размер merge(b,c) всегда будет size(b)+size(c), который можно рассчитать вне слияния.

Обратите внимание, что исходная функция rank для обычных левых куч " не разделяет это свойство и поэтому не может быть оптимизирована таким образом.

По сути, вы встраиваете два вызова в линию T , а также конвертируете вызовы вида size(merge(b,c)) в size(b)+size(c).

Как только вы сделаете это изменение, результирующая функция будет значительно медленнее, чем оригинал, потому что она может вернуть корень результата до оценки рекурсивного слияния.

Аналогичным образом, в параллельной среде, включающей блокировки и мутации, новая реализация может поддерживать значительно больший параллелизм, получая и снимая блокировки для каждого узла на этом пути, а не блокируя все дерево. (Конечно, это имеет смысл только для очень легких замков.)

Answer 2

Я не совсем уверен, правильно ли я понял вопрос, но вот моя попытка - в настоящее время операция merge выполняет рекурсивный вызов merge (это первый проход) и когда она достигает конца куча (первые два случая в match), она возвращает вновь созданную кучу обратно вызывающей стороне и вызывает makeT пару раз (это второй проход).

Я не думаю, что простое встраивание mMakeT - это то, что мы просим сделать (если да, просто добавьте inline к makeT, и это делается без того, чтобы сделать код менее читабельным: -)).

Что можно сделать, однако, это изменить функцию merge для использования стиля продолжения-прохождения, когда «остальная часть работы» передается как функция рекурсивному вызову (так что работа над отложенной работой не ведется) стек, который должен быть сделан после первого прохода). Это можно сделать так:

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

Я не совсем уверен, что это правильный ответ - он выполняет только один проход, но агрегированная работа (в продолжении) означает, что проход в два раза длиннее. Однако я не вижу способа сделать это проще, поэтому это может быть правильный ответ ...