F# Чисто функциональные данные структур, зависящие от веса верхнего слоя, пример 3.4
Вопрос
Я работаю над чисто функциональными структурами данных 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
Решение
Первый вопрос заключается в следующем:что представляет собой "однопроходный" алгоритм?Подходило бы что-то, что естественным образом могло бы быть реализовано как единый нисходящий цикл.Напротив, рекурсия - скомпилированная наивно - обычно имеет два прохода, один на пути вниз и один на пути обратно вверх. Хвостовая рекурсия может быть легко скомпилирован в цикл и обычно выполняется на функциональных языках. Конечная рекурсия по модулю 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)
.
Как только вы внесете это изменение, результирующая функция будет значительно более ленивой, чем исходная, поскольку она может возвращать корень результата до того, как оцениваем рекурсивное слияние.
Аналогично, в параллельной среде, включающей блокировки и мутации, новая реализация могла бы поддерживать значительно больший параллелизм, получая и освобождая блокировки для каждого узла на этом пути, а не блокируя все дерево.(Конечно, это имело бы смысл только для очень легких замков.)
Другие советы
Я не совсем уверен, правильно ли я понял вопрос, но вот моя попытка - в настоящее время операция merge
выполняет рекурсивный вызов merge
(это первый проход) и когда он достигает конца кучи (сначала два случая в match
), он возвращает вновь созданную кучу обратно вызывающей стороне и несколько раз вызывает makeT
(это второй проход).
Я не думаю, что просто встраивание mMakeT
- это то, что нас просят (если да, просто добавьте inline
в makeT
, и это не сделает код менее читаемым :-)).
Что можно сделать, так это изменить функцию merge
для использования стиля передачи продолжения, в котором «остальная часть работы» передается как функция рекурсивному вызову (чтобы в стеке не было незавершенной работы будет выполнено после завершения первого прохода). Это можно сделать так:
Я не совсем уверен, что это правильный ответ - он выполняет только один проход, но совокупная работа (в продолжении) означает, что проход в два раза длиннее. Однако я не вижу способа сделать это проще, так что это может быть правильный ответ ...