F# PurelyFunctionalDataStructures WeightBiasedLeftistHeap ex 3.4

Я работаю над чисто функциональными структурами данных Окасаки и пытаюсь построить реализацию 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
Источник

2 ответа

Решение

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

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

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

По сути, вы встраиваете два вызова в makeT, а также конвертируете вызовы формы size(merge(b,c)) в size(b)+size(c),

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

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

Источник

Я не совсем уверен, правильно ли я понял вопрос, но вот моя попытка - в настоящее время 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

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

Источник
Другие вопросы по тегам