F# Чисто функциональные данные структур, зависящие от веса верхнего слоя, пример 3.4

Question

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

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

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

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

По сути, тогда вы вставляете два вызова в makeT а также преобразуйте вызовы формы size(merge(b,c)) Для size(b)+size(c).

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

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

Answer 2

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

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

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

родовое слово

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